301. Remove Invalid Parentheses
괄호가 맞도록 최소한의 문자를 제거해서 올바른 괄호 문자열을 출력하는 문제. 처음엔 간단한 완전탐색 dfs를 했는데 시간이 너무 오래 걸림. (심지어 초반 코드는 시간 초과라 최적화를 조금 했지만 9s 넘게 걸렸다) => 최소한의 문자를 제거하는 것이므로 BFS 방식으로 변경 현재 상태를 level이란 set으로 두자. level에서 가능한 문자열이 있으면…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
200 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 풀이도 가능하…
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가 같다는 것은 팰린드롬이…