1653. Minimum Deletions to Make String Balanced
a 또는 b를 최소한으로 지워서 문자열을 /a*b*/ 형태로 만드는 횟수를 구하는 문제. 기준점을 두고 그리디하게 왼쪽의 b를 지우고 오른쪽의 a를 지웠을 때 횟수의 합 중 최소를 구하면 된다. 마지막에 1 빼주는건 현재 위치가 중복으로 들어가서 그냥 빼주었다. (현재 위치도 카운트에 집어넣었기 때문) 또한, 배열을 안쓰고 count 변수 2개로도 풀 수 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
271 270 1395. Count Number of Teams
연속으로 작아지거나 커지는 3 크기의 부분 배열을 구하는 문제. 브루트 포스는 O(n^3)으로 불가. 약간 스마트한 브루트 포스로 풀린다. O(n^2) 배열의 크기가 3이므로 중간을 기준으로 왼쪽은 더 작은 값, 오른쪽은 더 큰 값을 고르면 된다. 비슷하게 중간을 기준으로 왼쪽은 더 큰 값, 오른쪽은 더 작은 값을 갖는 배열의 개수를 구해서 더하면 정답이 …
269 2045. Second Minimum Time to Reach Destination
신호등이 있는 그래프가 주어질 때 1부터 n으로 가는 경로 중에서 두번째로 짧은 경로를 구하는 문제. 일단 신호등이 change 마다 바뀌는데 다시 보면 시간이 change의 짝수 배이면 초록불, change의 홀수 배이면 빨간불이다. 이제 두번째로 짧은 경로를 구해야 하는데 마지막 도시에 두번째로 도착한 시간이 두번째로 짧은 경로가 된다. (가까운 순으로…
268 218. The Skyline Problem
빌딩이 주어질 때 스카이라인을 출력하는 문제. 상당히 빡센 문제이다. heap (pq)를 쓴다는 것을 알고 봐도 쉽지 않음. 일단 왼쪽부터 오른쪽으로 하나씩 스캔하는 방식으로 진행하면서 현재까지 겹쳐있는 빌딩의 높이를 관리해주면 풀 수 있다. 스캔은 빌딩 시작과 끝을 기준으로 해야 하므로 주어진 빌딩 배열을 분해해주자. 그리고 현재까지 빌딩 높이 관리는 가…
267 2551. Put Marbles in Bags
가방 안의 돌들을 k 그룹으로 묶을 때 최소 합과 최대 합의 차이를 구하는 문제. 처음에는 DP 느낌이지만 수가 너무 많다. 정답은 그리디로 가면 된다. 뭔가 정렬 느낌이긴 했는데 잘 안돼서 에디토리얼 참고함. 사진은 에디토리얼에서 가져옴 일단 시작 돌과 마지막 돌은 무조건 포함해야 하니 제외하자. 그러면 k-1번 가방의 돌들을 나누는 문제가 된다. 여기서…
266 514. Freedom Trail
ring와 입력해야 할 key가 주어질 때 최소 횟수로 ring을 돌려서 key를 만드는 횟수를 구하는 문제 간단한 DP로 풀 수 있다. 현재 위치 기준으로 왼쪽, 오른쪽으로 돌려가며 찾을 수 있다. 시간 복잡도는 O(R^2 K) left, right로 돌릴 때의 문자열을 찾을 때 전처리를 통해 미리 구해놓으면 더 빨리 구할 수 있다. 또는, 에디토리얼 보…
265 1289. Minimum Falling Path Sum II
행끼리 인접하지 않은 열의 수를 더해서 최소가 되도록 맨 아래까지 가는 합을 구하는 문제. O(n^3) 풀이는 매우 쉬운 DP. O(n^2) 풀이를 생각해보자. 그리디하게 생각해보면 된다. 다음 row로 넘어갈 때 col이 같지만 않으면 된다. 즉, col이 어떤 곳이라도 찍을 수 있다는 것. 이를 잘 이용하면 전체 스캔할 필요 없이 최솟값인 곳과 두번째 …
264 912. Sort an Array
정렬 구현 문제 뭐 별거 없고 그냥 정렬을 구현하면 된다. nlogn 정렬들 중 아무거나 구현하면 되는데 제일 간단하면서 안정적인 merge sort를 구현하였다. 퀵 소트, 힙 소트 등 기억이 잘 안나네 ㅋㅋ
263 287. Find the Duplicate Number
배열에서 중복된 수를 찾는 문제. 단 배열의 조작은 불가능하고, 공간복잡도는 O(1)이어야 한다. 제약 조건이 없다면 매우 쉬운 문제... 하지만 제약 조건과 follow up을 전부 만족하려면 특별한 알고리즘이 필요하다. 일단 해당 문제를 링크드 리스트로 볼 수 있는데 nums의 값을 인덱스로 해서 다음 리스트로 넘어가는 링크드 리스트로 가정하면 링크드 …
262 57. Insert Interval
구간들이 주어질 때 새로운 구간을 추가하는 문제. 구간들은 겹칠 경우 머지되어야 한다. 약간 그리디 느낌? 겹치지 않은 경우는 그냥 결과 배열에 넣으면 되고 겹치는 경우는 left는 겹치는 구간들의 최소, right는 겹치는 구간들의 최대로 해서 추가하면 된다. 좀 지저분하게 짜긴 했지만 결과도 맞게 나오고 O(n)이라 별 상관 없다.