763. Partition Labels
문자열을 각 문자들이 최대 한 덩어리에만 있도록 나눠야 한다. 최대한 많이 나눌 때의 덩어리 개수를 구하는 문제. 잘 생각해보면 한 덩어리에만 있어야 한다는 것은 다음 덩어리에는 해당 문자가 나타나서는 안 된다는 것이다. 다음 문자가 어디 있는지 map을 통해 위치를 저장해두고 현재 덩어리의 모든 문자가 뒤에 나타나지 않으면 한 덩어리로 묶을 수 있다. 위…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
204 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) 으로 구할 수 있다.…
201 1249. Minimum Remove to Make Valid Parentheses
올바른 괄호 문자열이 되도록 최소한의 문자를 제거하는 문제. 최소한을 제거해야 하므로 제거할 필요가 없는 애들은 놔둬야 한다. 즉, 올바른 괄호면 제거하지 않고 올바르지 않은 괄호만 골라서 지우면 된다. 간단한 카운터를 하나 두고 (가 나오면 ++, )가 나오면 --로 해서 올바른지 판단할 수 있다. 이렇게 하면 열지 않았는데 닫는 괄호를 제거해줄 수 있고…
200 301. Remove Invalid Parentheses
괄호가 맞도록 최소한의 문자를 제거해서 올바른 괄호 문자열을 출력하는 문제. 처음엔 간단한 완전탐색 dfs를 했는데 시간이 너무 오래 걸림. (심지어 초반 코드는 시간 초과라 최적화를 조금 했지만 9s 넘게 걸렸다) => 최소한의 문자를 제거하는 것이므로 BFS 방식으로 변경 현재 상태를 level이란 set으로 두자. level에서 가능한 문자열이 있으면…
199 20. Valid Parentheses
괄호들이 올바른지 판단하는 문제 매우 간단한 스택 문제이다. 스택에 여는 괄호를 넣고 닫힌 괄호가 나오면 스택에서 빼면서 체크하면 된다. 마지막에 스택이 비어있는지도 체크한다.
198 61. Rotate List
링크드 리스트를 k번 회전시키는 문제. 그냥 말 그대로 k번 회전시키면 된다. k가 크므로 먼저 리스트의 길이를 구해서 mod 연산으로 줄여줘야 하고, 회전 후 맨 뒤로 이동해서 연결을 끊어준 후 끊어진 tail과 head를 연결하면 된다.
197 138. Copy List with Random Pointer
랜덤 포인터가 있는 링크드 리스트를 그대로 복사하는 문제 죽 돌면서 복사하면 된다. 랜덤 포인터의 경우 map으로 random 노드를 관리해주면 된다.
196 1883. Minimum Skips to Arrive at Meeting On Time
주어진 시간 안에 도착까지 갈 수 있는 최소의 스킵 수를 구하는 문제. 스킵을 하지 않으면 다음 도로는 대기 후 정시에 출발 가능하고 스킵을 하면 바로 출발할 수 있다. 처음에 짠 최소 스킵 횟수를 반환하는 단순한 4차원 DP로는 시간 초과... (idx, 스킵한 시간, 남은 시간, 스킵한 횟수), 살짝 비틀어서 생각해보면 dp[i][j]: i 인덱스까지 …
195 699. Falling Squares
위에서 블록이 차례대로 떨어질 때 현재 가장 높은 블록을 순서대로 출력하는 문제. 인풋 크기가 작으므로 n^2 풀이로 풀린다! heights 맵을 만들어 해당 구간의 높이를 저장해두면서 다른 블록이 떨어질 때 겹치는 구간이 있는지 보고 있다면 그만큼 높이를 더해서 추가하는 방식으로 동작한다. 참고로 세그먼트 트리나 이분 탐색 등으로 nlogn 풀이도 가능하…