103. Binary Tree Zigzag Level Order Traversal
이진 트리가 주어질 때 레벨 별로 지그재그 하면서 출력하는 문제 레벨별로 맵을 만들고 순서에 맞게 집어넣으면 된다. 일반 bfs 탐색을 약간 변형하면 됨
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
310 309 433. Minimum Genetic Mutation
ACGT로만 이루어진 gene이 둘 주어질 때 startGene 에서 endGene으로 mutate가 가능하면 최소 횟수를 출력하는 문제. mutate는 bank에 있는 문자열로만 가능하다. bank 개수 제한이 아주 여유로워서 DFS, BFS 다 가능하다. 일단 간단하게 DFS 백트래킹으로 구현했다. bank로 mutate가 가능한지 판단해서 이동하는 방…
308 215. Kth Largest Element in an Array
배열에서 정렬 없이 k 번째 큰 수를 찾는 문제 정렬하면 쉽지만 안하고 풀어야 한다. quick sort를 응용한 quick select 알고리즘을 쓰면 된다. quick sort와 비슷하게 피벗을 잡고 피벗 기준으로 왼쪽은 더 큰 값들, 오른쪽에는 더 작은 값들을 몰아 넣는다. 여기서 포인트는 quick select는 정렬이 필요가 없으므로 왼쪽, 오른쪽…
307 71. Simplify Path
unix path가 주어질 때 간단화 하는 문제. 즉, 여러 슬래시나 .. 같은 디렉토리 변경 등을 다 처리후 최소화된 경로로 만드는 문제. 스택을 쓰면 되는 간단한 문제. 먼저 슬래시 기준으로 split을 해준다. 일반적인 ., .. 같은 디렉토리 명렁어가 아닌 경우 스택에 넣어주고, ..의 경우에는 스택에서 빼주면 된다. 비어있는 문자열은 연속된 슬래시…
306 131. Palindrome Partitioning
문자열이 주어질 때 적당히 잘라서 모든 substring이 팰린드롬이 되게 배열을 반환하는 문제. 백트래킹으로 하면 간단하다. 애초에 모든 substring 경우의 수를 반환해야 해서 다 탐색할 수밖에 없다. 다만 그냥 하면 중복되는 substring 체크가 많기 때문에 dp를 섞어주면 빠르게 뽑을 수 있다. 시간 복잡도는 O(2^N * N) 공간 복잡도는…
305 128. Longest Consecutive Sequence
배열이 주어질 때 가장 긴 원소들의 연속 증가 길이를 구하는 문제 (순서는 상관 없음) O(n log n) 풀이는 정렬하면 되니까 쉽다. **O(n)**은 약간 생각해야 함. 일단 O(n)이니까 hashmap 방식으로 가야하고 hashmap으로 구현하려면 각 원소들을 한 번씩만 순회해야 한다. 원소들을 set에 넣어두고 set의 처음 지점인 원소부터 쭉 올…
304 1514. Path with Maximum Probability
간선에 확률이 있는 그래프가 주어진다. 시작점에서 끝점으로 갈 때 확률의 최대를 구하는 문제. 그냥 다익스트라를 돌려주면 된다. 일반 다익스트라가 합이 최소가 되게 한다면 여기서는 곱이 최대가 되게 뽑아주면 된다.
303 592. Fraction Addition and Subtraction
분수들의 식이 주어질 때 계산하는 문제 스트링 파싱 후 계산하면 된다. 초등학교 때 배운 분수의 덧셈 그대로 구현하면 되는데 분모는 최소공배수로 맞추고 분자끼리 더한 후 최대공약수로 분자와 분모를 각각 나눠주면 된다. 정규표현식으로 파싱이 깔끔하게 되는거 같은데 난 무식하게... 하나씩 파싱했다 ㅋㅋ
302 476. Number Complement
수가 주어질 때 complement를 구하는 문제. 1이 0이 되고 0이 1이 되려면?? XOR를 쓰면 된다. 자릿수를 올라가면서 1과 XOR를 하면 1은 0이 되고 0은 1이 된다.
301 664. Strange Printer
한 문자를 죽 이어 붙이거나 특정 범위의 문자열을 교체하는 2가지 연산을 할 때 최소한의 연산으로 문자열을 만드는 횟수를 찾는 문제. 약간 분할 정복, 완전탐색 느낌이 나는데 쉽지 않다. 일단 양옆이 같은 문자인 경우 중간을 바꿔치기 했다고 생각할 수 있다. 그 외의 경우는 이어 붙여야 한다. 따라서 문제를 나눠볼 수 있는데 맨 앞과 같은 문자가 중간에 나…