778. Swim in Rising Water
2차원 배열에 수가 있고 써있는 수만큼의 시간이 지나야 다음 노드로 이동할 수 있다. n-1, n-1에 도착 가능한 최소 시간을 구하는 문제. 단순 완전 탐색 BFS로 하니 시간 안에 통과는 되지만 매우 느리다. 좀 더 생각을 해보면 시간은 최소 0, 최대 n^2 이므로 이분 탐색으로 가능한 최소 시간을 구한다면 n^2 log(n^2) 으로 구할 수 있다.…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
hard 69
202 200 301. Remove Invalid Parentheses
괄호가 맞도록 최소한의 문자를 제거해서 올바른 괄호 문자열을 출력하는 문제. 처음엔 간단한 완전탐색 dfs를 했는데 시간이 너무 오래 걸림. (심지어 초반 코드는 시간 초과라 최적화를 조금 했지만 9s 넘게 걸렸다) => 최소한의 문자를 제거하는 것이므로 BFS 방식으로 변경 현재 상태를 level이란 set으로 두자. level에서 가능한 문자열이 있으면…
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 풀이도 가능하…
194 1542. Find Longest Awesome Substring
swap을 해서 팰린드롬이 될 수 있으면 awesome이라고 할 때, 주어진 문자열의 substring 중 가장 긴 awesome 부분 문자열의 길이를 구하는 문제. 일단 swap해서 팰린드롬이 되려면 문자의 수가 전부 짝수이거나 하나만 홀수이어야 한다. 그러면 각 문자가 나온 수를 카운트 해줘야 하는데... 이건 XOR 연산으로 해주면 된다. 각 문자의 …
193 2009. Minimum Number of Operations to Make Array Continuous
배열의 전체 원소들이 연속되게 만들 수 있게 원소의 수를 바꾸는 최소 횟수를 구하는 문제. 먼저 순서가 상관이 없으므로 정렬을 하고 시작하자. 그러면 뭔가 보이는데, 만약 결과 배열의 시작을 a 로 잡았다면 결과 배열은 [a, a+1, a+2 ... a + n-1] 이 된다. 여기서 힌트를 얻어 주어진 배열에서 임의의 원소를 시작으로 잡는 결과 배열을 얻을…
192 1411. Number of Ways to Paint N × 3 Grid
3개의 색을 사용해서 n x 3 크기의 그리드를 인접한 색이 같지 않도록 색칠하는 경우의 수를 구하는 문제. 딱 보니 DP이다. 색의 조합이 한정되어 있으므로 이를 배열로 넣어주고 DP를 돌리면 된다. 위 DP풀이는 O(n)이라 충분히 통과하지만 (정확히는 색의 조합 k, n * k * k) O(log n)으로도 가능한데... 행렬의 곱셈을 이용하면 된다!
191 214. Shortest Palindrome
주어진 문자열이 팰린드롬이 되도록 문자열을 앞에 붙이는 문제. 처음에는 단순 while 루프를 돌았지만 예외가 발생함. 결국 KMP로 해결 KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 이용하면 팰린드롬을 구할 수 있다. 주어진 문자열에 뒤집은 문자열을 붙였을 때 prefix와 suffix가 같다는 것은 팰린드롬이…
190 834. Sum of Distances in Tree
트리가 주어질 때 각 노드에서 다른 노드까지의 거리의 합을 모두 구하는 문제. 단순 N^2은 시간 초과이므로 한 번(N)에 구해야 한다. 잘 생각해보면 각 노드의 자식 노드의 개수를 이용하면 된다. 먼저 0번 노드부터 다른 노드까지의 거리를 구해준 다음, 각 노드에서 거리를 구할 땐 자식 노드의 개수를 이용하면 된다. 거리를 계산할 기준 노드를 child로…
189 1857. Largest Color Value in a Directed Graph
노드에 색이 칠해져 있는 방향 그래프가 주어진다. 그래프의 path 중 가장 많이 나온 색깔의 개수를 구하는 문제. 사이클이 있다면 -1을 출력. 처음엔 dfs로 구현해서 제출했는데 엣지 케이스 처리가 까다롭다. (사이클 탐지, visited 체크 등) 결국 위상 정렬로 다시 제출. 그리디적인 방법을 생각해보면 가장 색깔이 많이 나오려면 경로의 제일 처음부…