173. Binary Search Tree Iterator
BST에서 크기 순으로 동작하는 이터레이터를 만드는 문제. 메소드는 next(), hasNext() 두개를 구현하면 된다. 초기화 때 inorder으로 전부 돌아서 배열에 넣은 다음 하나씩 출력하는 방법이 간단하지만 메모리는 O(n)이긴 하다. 스택을 쓰면 O(h)로 메모리를 줄일 수 있다. 하지만 결과에서의 실행 시간은 배열에 전부 집어넣은 방식이 더 빠…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
211 210 230. Kth Smallest Element in a BST
BST가 주어질 때 K번째 작은 원소를 구하는 문제 BST를 탐색하면서 K번째 작은 원소가 나오면 리턴하면 된다. BST 탐색 방법 중 inorder 탐색을 하면(왼쪽 서브트리, 자신, 오른쪽 서브트리) 크기 순으로 탐색할 수 있고 이를 배열에 넣은 다음에 배열에서 k-1 인덱스의 원소를 뽑아내면 된다. 중간에 k번 탐색을 했다면 바로 리턴하는 식으로 가지…
209 857. Minimum Cost to Hire K Workers
노동자의 품질과 최소 임금이 주어질 때 K 명의 노동자를 뽑아야 한다. K명의 노동자가 받는 임금과 품질의 비율은 모두 같아야 한다. 이때 K 명을 뽑을 수 있는 최소 임금을 구하는 문제. 처음부터 드는 생각은 가성비가 좋은 노동자를 뽑아보는 것이다. 즉, wage / quality 를 한 값이 작은 순서로 K명을 뽑아주면 가성비가 좋은 K 명을 뽑을 수 …
208 403. Frog Jump
처음엔 1칸을 뛸 수 있고 k칸 뛴 다음엔 k-1, k, k+1 칸을 뛸 수 있을 때 끝까지 점프할 수 있는지 확인하는 문제. 그냥 DP. N 크기도 작아서 대충 돌려주면 된다. 하드 중에서 아주 쉬운 문제. DP[i, k]: i 인덱스에서 k칸 뛸 때의 가능 여부 위처럼 점화식 세우고 k-1,k,k+1 에 대해 돌려주면 된다. 위치가 아니라 인덱스로 저장…
207 600. Non-negative Integers without Consecutive Ones
n 이하의 수 중에서 2진법으로 했을 때 1이 연속으로 나오지 않는 수의 개수를 구하는 문제. DP로 풀 수 있다. 특정 자리 수에서 1이 연속으로 나오지 않는 수의 개수는 DP로 구하고 n보다 작은지 판단은 1이 나왔을 때 0으로 시작하는 나머지 수들을 더해주면 된다. 아래 디스커션이 이해하기 좋다.
206 991. Broken Calculator
startValue 와 target이 주어질 때 startValue를 target으로 만드는 최소 연산 횟수를 구하는 문제. 연산은 2를 곱하는 것과 1을 빼는 것이 있다. 문제를 그대로 풀면 꽤 tricky 한데 반대로 생각해보면 쉽게 풀린다. 즉, target을 startValue로 만드는 최소 횟수를 구하면 된다. 대신 연산은 2을 나누는 것과 1을 …
205 1663. Smallest String With A Given Numeric Value
1: a, 2: b... 26: z 라고 할 때 k를 나타낼 수 있는 n 길이의 사전순으로 가장 작은 문자열을 출력하는 문제. 문자열의 값은 각 자리의 알파벳 수를 더하는 것이다. 딱 보니 큰 알파벳을 뒤부터 채워나가면 된다. z부터 넣다가 안되면 일반 알파벳, 나머지는 a로 채우면 사전순으로 가장 작게 만들 수 있다. 즉 그리디.
204 763. Partition Labels
문자열을 각 문자들이 최대 한 덩어리에만 있도록 나눠야 한다. 최대한 많이 나눌 때의 덩어리 개수를 구하는 문제. 잘 생각해보면 한 덩어리에만 있어야 한다는 것은 다음 덩어리에는 해당 문자가 나타나서는 안 된다는 것이다. 다음 문자가 어디 있는지 map을 통해 위치를 저장해두고 현재 덩어리의 모든 문자가 뒤에 나타나지 않으면 한 덩어리로 묶을 수 있다. 위…
203 895. Maximum Frequency Stack
많이 나온 원소부터 pop이 되는 스택을 구현하는 것이다. 하드 치고는 꽤 쉬운 문제. 문제 그대로 많이 나온 원소부터 pop이 되도록 구현하면 되는데 원소가 나온 카운트에 대한 맵을 하나 두고 스택도 카운트 별로 만들어 둔다. 예제에서 push, pop 쿼리가 최대 2만개 까지라고 했으므로 20001개의 스택을 만들어 두었다. push의 경우 원소의 개수…
202 778. Swim in Rising Water
2차원 배열에 수가 있고 써있는 수만큼의 시간이 지나야 다음 노드로 이동할 수 있다. n-1, n-1에 도착 가능한 최소 시간을 구하는 문제. 단순 완전 탐색 BFS로 하니 시간 안에 통과는 되지만 매우 느리다. 좀 더 생각을 해보면 시간은 최소 0, 최대 n^2 이므로 이분 탐색으로 가능한 최소 시간을 구한다면 n^2 log(n^2) 으로 구할 수 있다.…