2402. Meeting Rooms III
미팅룸이 n개 있고 미팅 시간이 주어졌을 때 가장 미팅이 많이 한 룸을 구하는 문제. 미팅이 가능한 방이 여러개 있을 경우 가장 작은 번호의 방이 선택되며 현재 가능한 방이 없다면 가장 빠른 방을 사용한다. 그리디 방식으로 가능하다. 일종의 스케줄링 + 구현 문제라고 봐도 될 듯. 문제에 나온 그대로 작은 방부터 탐색하면서 미팅이 가능하면 미팅을 하면 된다…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
254 253 1642. Furthest Building You Can Reach
벽돌의 개수와 사다리의 개수가 주어질 때 빌딩 사이를 가장 멀리 이동할 수 있는 거리를 구하는 문제. 빌딩의 높이가 같거나 낮으면 그냥 이동할 수 있으며, 벽돌은 빌딩 사이의 높이 차이만큼 사용되고 사다리는 높이와 상관없이 한개씩 사용된다. 그리디로 해결할 수 있다. DP로 해봤는데 bricks의 공간?이 너무 넓어서 메모리 초과가 난다... 빌딩 사이의 …
252 1481. Least Number of Unique Integers after K Removals
배열의 수들을 k개 삭제했을 때 unique한 수의 최소 개수를 구하는 문제. 그리디로 풀면 된다. 갯수가 적은 수부터 삭제하면 unique한 수를 최소한으로 줄일 수 있다. map으로 개수를 세고 개수를 기준으로 정렬한 뒤 앞에서부터 제거하면 된다. 에디토리얼 보니 O(n)으로도 되는데 정렬하지 않고 나온 개수를 다시 맵에 넣는 방식으로 하면 O(n)이 …
251 2971. Find Polygon With the Largest Perimeter
주어진 배열의 값의 길이의 선으로 만들 수 있는 도형의 최대 둘레를 구하는 문제. 문제에 답이 있는데 즉, 다른 모든 변의 길이의 합보다 큰 변이 없어야 한다. 정렬한 후 둘레를 하나씩 더해보면서 변의 길이보다 큰지 체크해주면 된다.
250 2149. Rearrange Array Elements by Sign
배열이 있을 때 양수 음수가 번갈아 나오게 하면서 양수 음수의 순서를 유지한 채로 재정렬하는 문제. 너무 쉽다... 일단 처음 풀이는 양수와 음수 배열을 각각 선언 후 하나씩 빼서 최종 배열을 만들었는데 O(2n). 이것보다 더 줄일 수 있다. 일종의 투 포인터로 양수와 음수가 나올 때마다 정답 배열에 끼워넣는 방식으로 넣어주면 된다. O(n)
249 2108. Find First Palindromic String in the Array
문자열의 배열 중에서 첫 번째 팰린드롬을 구하는 문제 말도 안되게 쉬워서 이걸 글을 써야 하나 싶지만... Daily 문제이기도 하고 지금까지 계속 썼기 때문에 일단 작성한다. 그냥 돌면서 팰린드롬인지 체크하면 된다.
248 169. Majority Element
배열에서 n / 2번 이상 나온 원소를 찾는 문제. (과반수 이상 나온 원소) 시간 O(n), 공간 O(n)이상의 솔루션은 매우 쉽다 (sorting, hashmap, 등등) 하지만 follow up 문제인 시간 O(n), 공간 O(1)은 꽤 어려운데... 이거는 Boyer-Moore Voting Algorithm을 써야 한다. 위대한 ChatGPT의 도움…
247 1463. Cherry Pickup II
로봇이 첫 번째 행의 첫 번째 열과 마지막 열에 2개 있고 아래로 3 방향으로 내려가면서 최대로 체리를 얻을 수 있는 개수를 구하는 문제. 일단 간단한 DP 문제이긴 한데 궁금증이 하나 있다. 두 로봇이 같은 셀로 들어가는게 좋은 경우가 있을까? 결론은 없다. 만약 두 로봇이 같은 셀로 들어갔다고 해도 다음 경로를 정할 때는 다른 셀로 들어가야 할텐데 굳이…
246 647. Palindromic Substrings
문자열이 주어질 때 palindrome인 substring의 개수를 구하는 문제. 처음 보면 좀 어려워 보이는데 팰린드롬 체크를 좌 우로 한 칸씩 늘려가면서 체크하는 방식으로 생각하면 쉽게 풀린다. 즉, s[left : right] 가 팰린드롬일 때 s[left - 1] == s[right + 1]이면 s[left - 1 : right + 1]도 팰린드롬이…
245 368. Largest Divisible Subset
리스트가 주어질 때 모든 subset이 각각의 배수가 되도록 하는 최대 길이의 subset을 구하는 문제. 일단 순서가 중요하지 않으므로 정렬을 먼저 하자. 그러면 뭔가 보이는데 두 인덱스를 i, j (i < j) 라 했을 때 nums[j] % nums[i] == 0이면 뒤로 이어 붙일 수 있다. 이런식으로 모든 원소에 대해 길다면 이어 붙이는 식으로 이어…