1202. Smallest String With Swaps
문자열과 스왑이 가능한 인덱스가 주어질 때 스왑을 해서 문자열을 사전 순으로 최소가 되게 만드는 문제. 조금만 생각해보면 Disjoint-set 으로 풀 수 있다. 스왑을 하는 인덱스가 연결이 되어 있다면 얼마든지 스왑을 통해 연결된 인덱스의 최소로 바꿀 수 있다는 점을 이용한 것이다. 예를 들어 [0, 1], [1, 2]가 스왑이 가능하면 여러 번 스왑으…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 79
217 216 284. Peeking Iterator
일반 이터레이터를 사용해서 peek 연산이 가능한 이터레이터를 만드는 문제. 임시 변수 하나를 두면 쉽게 풀린다. peek 할 경우 peeked 변수에 값을 집어넣고, 이미 변수에 값이 있다면 그대로 리턴하면 된다. next 할 때는 peeked 변수에 값이 있으면 그대로 리턴하면 되고 값이 없으면 next를 호출해서 가져오면 된다. hasnext도 비슷하…
214 1396. Design Underground System
checkin, checkout을 통해 두 도시간의 평균 시간을 구하는 문제 그냥 간단하다. checkin 할 때는 map으로 id가 들어온 시각을 저장한 후 checkout 할때 해당 구간에 대해 걸린 시간과 카운트를 누적해서 더해주면 평균을 쉽게 구할 수 있다.
213 535. Encode and Decode TinyURL
tinyurl 같은 것을 구현하는 문제. ... medium 치고 너무 쉬운데... 그냥 daily 라서 풀어보았다. 단순히 입력받는 것을 리턴해도 통과가 된다... 하지만 아무 의미가 없으니 간단하게 짜보자. 간단하게 하는 방법으로 id 카운터 값을 놓고 1씩 증가하면서 shorturl을 생성할 수 있다. map으로 관리해주면 매우 간단하게 가능하다.
211 173. Binary Search Tree Iterator
BST에서 크기 순으로 동작하는 이터레이터를 만드는 문제. 메소드는 next(), hasNext() 두개를 구현하면 된다. 초기화 때 inorder으로 전부 돌아서 배열에 넣은 다음 하나씩 출력하는 방법이 간단하지만 메모리는 O(n)이긴 하다. 스택을 쓰면 O(h)로 메모리를 줄일 수 있다. 하지만 결과에서의 실행 시간은 배열에 전부 집어넣은 방식이 더 빠…
210 230. Kth Smallest Element in a BST
BST가 주어질 때 K번째 작은 원소를 구하는 문제 BST를 탐색하면서 K번째 작은 원소가 나오면 리턴하면 된다. BST 탐색 방법 중 inorder 탐색을 하면(왼쪽 서브트리, 자신, 오른쪽 서브트리) 크기 순으로 탐색할 수 있고 이를 배열에 넣은 다음에 배열에서 k-1 인덱스의 원소를 뽑아내면 된다. 중간에 k번 탐색을 했다면 바로 리턴하는 식으로 가지…
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을 통해 위치를 저장해두고 현재 덩어리의 모든 문자가 뒤에 나타나지 않으면 한 덩어리로 묶을 수 있다. 위…
201 1249. Minimum Remove to Make Valid Parentheses
올바른 괄호 문자열이 되도록 최소한의 문자를 제거하는 문제. 최소한을 제거해야 하므로 제거할 필요가 없는 애들은 놔둬야 한다. 즉, 올바른 괄호면 제거하지 않고 올바르지 않은 괄호만 골라서 지우면 된다. 간단한 카운터를 하나 두고 (가 나오면 ++, )가 나오면 --로 해서 올바른지 판단할 수 있다. 이렇게 하면 열지 않았는데 닫는 괄호를 제거해줄 수 있고…