Min IT's Devlog

풀이 일자: 22.10.10 난이도: [Medium] 분류: [String, Greedy] 문제 내용 palindromic한 문자열이 주어지면 이를 1개의 문자를 바꿔서 깨트리면 되는데 모든 경우의 수 중 사전적으로 가장 앞에 나오는 문자열을 반환하는 문제이다. 문제 해결 흐름 1. 특수 케이스를 생각해보자. → 문제에서 제시한 특수케이스는 한 글자를 바꾸더라도 palindromic함을 유지하는 경우인데 그 경우는 오직 문자열의 길이가 1일때만 가능하겠다. 2. 사전적으로 가장 작은 것을 내놓으면 된다면 Greedy하게 처리할 수 있지 않을까? → 앞에서부터 check를 해가면서 'a'가 아닌 문자를 'a'로 바꾸기만 하면 되는게 아닐까? 3. 예외 케이스가 있나? → 예를 들어 'aba'인 경우 'a'..

풀이 일자: 22.09.09 난이도: [Medium] 분류: [Greedy, Sorting] 문제 내용 주어진 character 집합에서 상대적으로 ATK, DEF가 다른 character보다 낮은 경우 Weak라고 하며 Weak character의 수를 찾는 문제. 문제 해결 흐름 1. 다른 ATK, DEF보다 낮은 player의 수를 찾아야 하니까 뭔가 극단적인 값을 이용하면 되지 않을까? → Greedy하게 현재 주어진 배열에서 ATK와 DEF가 상대적으로 가장 높은 값을 가지고 시작하자. 2. 가장 높은 값을 가지고 시작하되 좀 더 쉽게 만드는 방법이 있을까? → 배열이 ATK 내림차순, DEF 오름차순으로 정렬하면 비교하는데 크게 문제가 없겠다. class Solution: def numberO..

풀이 일자: 22.09.05 난이도: [Medium] 분류: [BFS/ Tree] 문제 내용 주어진 n-ary tree를 가지고 각 level의 노드값들의 리스트들을 하나로 묶어서 리턴하는 문제이다. 문제 해결 흐름 1. 문제에서 level별 순회값을 리턴하라고 어떻게 풀어야 하는지 제시해주었다. → 대놓고 BFS쓰라는 거구나. 그래도 일단 익숙한 DFS로 풀어보았다. """ # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution: def levelOrder(self, root: 'Node') -> List[L..

풀이 일자: 22.09.04 난이도: [Hard] 분류: [Hash Table/ DFS/ BFS/Binary Tree] 문제 내용 root(0,0)부터 아래로 내려가면서 왼쪽 노드는 +1 -1 오른쪽 노드는 +1 +1을 좌표에 더하여 y좌표가 같은 것끼리 묶어서 값을 리턴하는 문제였다. 문제 해결 흐름 1. 일단 이것도 트리 순회를 하면서 값을 정리하는 것이므로 트리 순회 알고리즘이 필요하겠다. → 간편한 DFS 방식을 사용해볼까? 2. 트리의 크기를 최대 최소로 알아볼까? → 현재 가질 수 있는 맨 아래 최대 최소 좌표는 (9,-9) ~ (9,9)이다. 그 이유는 최대 1000개의 노드가 있으므로 2^n으로 등비수열의 합을 게산해보면 0 ~ 9 level까지 가능하다는 것을 확인할 수 있기 때문이다. ..

풀이 일자: 22.09.03 난이도: [Medium] 분류: [Backtracking/BFS] 문제 내용 자릿수에 관한 정보 n과 인접한 수와의 차이를 나타내는 k를 받아서 해당 조건에 맞는 수의 List를 반환하는 문제였다. 즉 n = 3, k = 7이라 했을 때, 세자리수이고 인접한 각 자리수의 차이가 7인 수의 List를 반환해야 하므로 [181, 292, 707, 818, 929]가 이에 해당한다. 문제 해결 흐름 1. 받는 k에 따라 0~9까지의 수의 다음에 나올 수 있는 수를 미리 저장해두어야겠다. → k=0일때를 제외하고 0~9까지의 수 n 다음에 나올 수 있는 수가 (n+k, n-k)이므로 해당 정보를 딕셔너리(해쉬)로 저장하자. k가 0일때는 n 다음에 n이 나와야 한다. 2. 이제 나올..

풀이 일자: 22.09.02 난이도: [Easy] 문제 내용 주어진 트리에서 각 level별 val의 평균값의 list를 반환하는 문제 문제 해결 흐름 1. 트리에서 각 level별 node의 평균값을 return해야 한다. → 트리 순환 방법중 DFS와 BFS가 있는데 이 문제의 경우에는 둘의 방식의 차이일뿐 어떤 것을 써도 괜찮을 것 같다. 일단 구현하기 쉬운 DFS를 이용해서 풀어보자. 2. DFS로 풀어본다고 했는데 어떤 방식으로 구현하면 좋을까? → 어제의 문제의 풀이를 참고하여 deque를 이용하여 DFS를 구현하고 두번째 요소에 level을 표시하여 각 level별로 sum과 원소의 개수를 저장해두자. # Definition for a binary tree node. # class TreeN..

풀이 일자: 22.09.01 난이도: [Medium] 분류: [Binary Tree/DFS] 문제 내용 주어진 Tree를 가지고 level이 올라가면서 지나온 경로의 node값보다 현재 node값이 큰 node의 갯수를 세는 문제였다. 한마디로 아래로 내려가면서 오름차순을 지키는 값을 가지는 노드 수를 물어보는 문제였다. 문제 해결 흐름 1. 일단 Tree이고 요소의 값을 확인을 해야하니까 Tree순회가 필요하겠는데.. DFS와 BFS중 어떤 것이 좋을까? → 아래로 내려가면서 루트로부터 자신의 경로 이전까지의 수보다 큰지를 확인해야하니까 DFS가 이 문제에 적합하겠네! 2. 현재의 값이 경로에 있는 수들과의 대소 비교가 필요하겠다 → 해당 경로에서 큰 수를 보관을 해서 계속해서 파라미터로 넘겨주는 것이..

풀이 일자: 22.08.18 난이도: [Medium] 문제 내용 주어진 integer array를 가지고 해당 array의 length를 반 이하로 줄일 때 최소한의 빼야하는 숫자의 개수에 대한 문제였다. arr = [3,3,3,3,5,5,5,2,2,7] → 이런식으로 주어졌을 때 3과 7을 뺀다면 남는 array는 [5,5,5,2,2]가 되게 되면서 기존의 1/2가 되게 된다. 문제 해결 흐름 1. 우선 중복되는 수를 몇 개씩 있는지 check를 해야겠다. → Dictionary를 이용하여 각각 몇개씩 있는지 세자. 2. 어떤 원소를 빼야 하는지가 아니라 최소한 빼야하는 원소의 개수에 대한 문제이니까 갯수에 대한 정보만 있으면 되겠네! → Dictionary의 value값만을 가져와서 list로 저장해..

풀이 일자: 22.08.17 난이도: [Easy] 문제 내용 여러 단어가 담겨있는 words 배열의 각각의 단어의 Unique한 조합이 몇 개인지 구하는 문제였다. "gin" -> "--...-." "zen" -> "--...-." → 이런식으로 다른 문자더라도 같은 모스부호 조합이 나올 수 있다. 문제 해결 흐름 1. 우선 각 alphabet마다의 모스부호의 규칙이 따로 없기 때문에 해당 정보를 미리 저장해두어야겠다. → 배열 형식으로 저장한다. 2. Unique한 조합을 찾기 때문에 미리 이전에 나왔던 모스부호 조합에 대한 정보를 저장해두어야겠다. → 만약 나오지 않았다면 갯수를 +1하면서 해당 정보를 저장한다. 3. 앞서 배열정보로 저장해둔 각 문자별 모스부호의 접근 방식은 어떻게 하면 좋을까? →..

풀이 일자: 22.08.16 난이도: [Easy] 문제 내용 주어진 문자열 s안에서 1번만 나온 문자의 가장 첫번째 index를 반환하는 문제 문제 해결 흐름 1. 1번만 나오는 문자를 체크하기 위해서는 문자의 개수를 세야겠다. → 중복은 하나로 처리해야하고 탐색도 해야하기 때문에 Dictionary(Hash)를 사용하면 좋겠다. 2. 가장 첫번째 index를 반환하려면 순서에 대한 정보를 가지고 있어야겠다. → 새로운 문자가 들어올때마다 append로 넣고 동일한 문자가 들어오면 remove로 없앨 수 있도록 list를 사용하자. 3. 첫번째 index를 찾자 → str.find()를 이용하여 찾고 만약에 candidate가 비었다면 다 중복이 있다는 이야기임으로 -1을 리턴하자. class Solut..