2841. Maximum Sum of Almost Unique Subarray
배열과 m, k가 주어질 때 배열의 subarray 중에서 길이가 k이고 중복되지 않는 수가 최소 m개인 개수를 구하는 문제. 딱 보니 간단한 슬라이딩 윈도우 문제이다. 배열의 처음부터 끝까지 죽 돌면서 길이가 k이고 중복되지 않는 수가 m개가 되도록 체크해주면 된다. 중복되는 수 체크는 map (dict)로 간단하게 할 수 있고 right는 개수 증가, …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
240 239 97. Interleaving String
s1과 s2 스트링을 자른 다음 교대로 이어 붙여서 s3 스트링을 만들수 있는지 판단하는 문제. 예시는: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 전형적인 DP 문제이다. 현재까지 고른 s1의 인덱스, s2의 인덱스, 마지막으로 고른 스트링 (s1 / s2) 해서 죽 돌려보았다. DP[i][j][k] = i: s1 …
238 199. Binary Tree Right Side View
이진 트리가 주어질 때 오른쪽에서 볼 때 보이는 노드들을 출력하는 문제. DFS로 조금 지저분하게 풀었는데 BFS가 더 깔끔할거 같긴 하다. DFS는 오른쪽 노드로 간 경로와 왼쪽 노드로 간 경로를 비교한 다음 오른쪽에서 본 것처럼 덮어 씌우는 방식으로 구현하였다. (문제 설명 그대로 오른쪽에서 보는 방식이다. 이런 문제 풀때 그닥 좋지는 않지만 직관적인 …
237 2360. Longest Cycle in a Graph
그래프가 주어질 때 가장 길이가 긴 사이클의 길이를 구하는 문제. 문제 자체는 쉽다. 사이클 중에 가장 긴 길이를 구하면 되는데 직접 구현은 살짝 복잡하긴 하다. 먼저 노드에서 나가는 엣지는 최대 1개이므로 그냥 바로 다음 노드로 건너가면 된다. 다음 노드로 갈 때 level 변수에 1씩 증가하다가 이미 방문한 노드가 있다면 현재 노드와 방문했던 노드의 l…
236 2321. Maximum Score Of Spliced Array
배열 2개가 주어지고, 배열의 일부 구간을 다른 배열과 swap 가능할 때 두 배열의 합 중 최대가 가장 큰 값을 구하는 문제. 딱 보니 DP라서 처음에는 top-down으로 풀었다. 해당 최댓값은 배열 하나에만 계산되므로 배열 2개를 서로 바꿔서 한번 더 돌려주면 된다. 정답이 나오긴 하는데 2792 ms로 하위 5%의 성능.. 결국 bottom-up 으…
235 2172. Maximum AND Sum of Array
슬롯이 있고 숫자를 한 슬롯에 최대 2개까지 집어넣을 수 있다. 이때 슬롯의 번호와 숫자를 AND 연산한 합 중에 최대를 구하는 문제. 비트마스크 DP 이다. 처음에는 슬롯에 2개씩 들어가므로 슬롯의 크기를 2배로 해서 돌려봤는데 시간 초과... 결국 비트마스크를 2개 써서 통과. dp[i][slot1][slot2] = slot1, slot2에 숫자가 있을…
234 1575. Count All Possible Routes
도시의 위치와 사용할 수 있는 연료가 주어질 때 start에서 finish로 갈 수 있는 경우의 수를 구하는 문제. 딱 보니 dp 로 간단하게 풀린다. 현재 도시 위치 + 남은 연료로 해서 돌려주면 된다.
233 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
자신과 상하좌우 4개 비트를 반전시킬 수 있을 때 모든 비트를 0으로 만드는 최소 횟수를 구하는 문제. 딱 보니 배열 크기도 작고 최소 횟수이므로 BFS로 돌려주면 된다. 하나 까다로운 것은 2차원 리스트를 큐나 방문 set에 넣고 빼고 하는 것인데.. set에 넣기 위해 tuple로 바꾸고...수정하기 위해 리스트로도 바꾸고... 좀 복잡하게 구현하긴 하…
232 943. Find the Shortest Superstring
모든 단어를 substring으로 갖는 가장 짧은 문자열을 구하는 문제. 처음에는 어려운데 비트마스크 DP를 쓰면 된다. 단어들을 뒤로 이어붙인다고 생각하고, 붙인 단어는 visited 처리를 비트마스크로 할 수 있다. 이러면 꽤 풀만한 문제가 된다. suffix 함수는 단어를 뒤로 붙일 때 앞 단어의 중복되는 부분을 제거한 suffix 만 추출하는 함수이…
231 1392. Longest Happy Prefix
접두사와 접미사가 같은 가장 긴 접두사를 출력하는 문제. 딱 보니 그 유명한 KMP 이다. KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 그대로 사용하면 된다. KMP 는 로이형의 유튜브를 참고하면 이해하기 쉽다.