2149. Rearrange Array Elements by Sign
배열이 있을 때 양수 음수가 번갈아 나오게 하면서 양수 음수의 순서를 유지한 채로 재정렬하는 문제. 너무 쉽다... 일단 처음 풀이는 양수와 음수 배열을 각각 선언 후 하나씩 빼서 최종 배열을 만들었는데 O(2n). 이것보다 더 줄일 수 있다. 일종의 투 포인터로 양수와 음수가 나올 때마다 정답 배열에 끼워넣는 방식으로 넣어주면 된다. O(n)
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
250 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이면 뒤로 이어 붙일 수 있다. 이런식으로 모든 원소에 대해 길다면 이어 붙이는 식으로 이어…
244 279. Perfect Squares
1부터 10000까지의 수가 주어질 때 더해서 만들 수 있는 최소 제곱수의 개수를 구하는 문제. 딱 보니 전형적인 DP 문제이다. (medium 난이도는 대부분이 DP 같다...) dp[i] = 최소 제곱수의 개수로 정의하고 j를 제곱수라고 했을 때 시간 복잡도는 i에 대해 한번, j에 대해 한번 돌게 되므로 O (n ^ 1.5) 가 된다. (제곱수는 n …
243 983. Minimum Cost For Tickets
1일권, 7일권, 30일권 티켓 가격이 주어지고 각 티켓을 사용해 주어진 날짜를 모두 여행할 수 있는 최소한의 비용을 구하는 문제. 간단한 DP 문제이다. dp[i] = i일부터 여행할 수 있는 최소 비용으로 두면 현재 날짜부터 1일권, 7일권, 30일권을 썼을 때 비용 중 가장 작은 것으로 계속 더해 나가면 된다.
242 799. Champagne Tower
샴페인 잔이 피라미드 형식으로 쌓여있고 맨 위의 잔에 샴페인을 부었을 때 특정 행, 열에 샴페인이 얼마나 차있는지 출력하는 문제. 처음에 테스트로 직접 한번씩 부었는데 당연히 시간초과가 난다. 수학적으로 가능한가 싶었는데 그냥 돌려주면 된다. 단 한번씩 붓는게 아니고 처음에 전부 부어주었다고 가정하면 된다. 넘치는 양을 다음 잔에 부어주면서 죽 돌려주면 된…
241 139. Word Break
스트링과 단어 리스트가 주어질 때 단어들을 이어붙여 스트링을 만들수 있는지 판단하는 문제. 간단한 DP 문제이다. 현재까지 인덱스를 dp로 저장해두고 단어를 이어붙일 수 있다면 계속 이어붙여주면 된다. 점화식을 세우자면 이런 느낌이 된다. s의 길이를 N, 단어의 개수 M, 각 단어 길이를 W라 하면 시간복잡도는 O(N M W)가 된다. 단어를 비교할 때 …