Algorithm/LeetCode
-
1005. Maximize Sum Of Array After K NegationsAlgorithm/LeetCode 2020. 6. 4. 14:05
출처: leetcode.com/problems/maximize-sum-of-array-after-k-negations/ 분류: Greedy, Easy 접근방식 k번 동안 배열에서 숫자를 하나 선택해 양수 음수 값을 바꿔야 합니다. k번 반복 이후 배열의 합이 가장 큰 경우를 찾는 문제입니다. 배열에서 음수가 있으면 모두 양수로 바꿔주고 음수를 모두 바꾸고도 k가 남아있다면 가장 최소인 숫자를 찾아서 그녀석을 한 번만 바꿔주면 됩니다. 방법 자체는 어렵지 않은데 생각해야 할 경우들이 조금 있어서 많이 틀렸습니다. 😭 해결방법 우선 음수를 모두 바꿔주기 위해 오름차순으로 정렬 후 0번부터 다음 인덱스가 양수일 때까지 양수로 바꿔주고 인덱스를 증가시킵니다. 양수일 때가지 찾았는데, k가 아직 홀수번 남았다면 ..
-
1029. Two City SchedulingAlgorithm/LeetCode 2020. 6. 4. 13:17
출처: leetcode.com/problems/two-city-scheduling/ 분류: Greedy, Easy 접근방식 각 cost에는 A와 B에 보낼 수 있는 비용이 들어있습니다. 2N개의 비용이 적힌 costs에서 각각 N개씩 공평하게 A와 B에 나눌 때 최소비용을 찾는 문제입니다. costs가 [[10,20],[30,200],[400,50],[30,20]] 이렇게 주어져 있다면, A에 2개 B에 2개를 [ 10, 30, 50, 20 ]로 뽑아줄 때 가장 최소비용이 됩니다. 하지만 무작정 둘 중 최소를 찾아서 분배한다고 해서 최소비용을 보장할 수가 없습니다. costs 중에서 어떤 cost를 우선적으로 분배해줘야 할까요? 바로 둘의 차이가 큰 cost를 먼저 분배해줘야 나중에 더 작은 비용을 분배..
-
1046. Last Stone WeightAlgorithm/LeetCode 2020. 5. 31. 11:15
출처: leetcode.com/problems/last-stone-weight/ 분류: Greedy, Easy 접근방식 무게가 가장 큰 돌과 그 다음으로 큰 돌을 부시면서 1개의 돌이 남을 때까지 반복하는 문제 입니다. 두 돌의 무게가 같다면 그대로 없어지고 한쪽이 더 크다면 그 나머지가 다시 남은 돌이 됩니다. 문제는 두 돌을 골라서 부실 때마다 돌의 우선순위가 바뀐다는 점입니다. 즉, 매 스탭마다 가장 큰 돌이 바뀔 수 있다는 점이죠. 이 점을 잘 체크하면 되는 문제입니다. 해결방법 단순하게 매 스탭마다 max를 2번 뽑아서 제거해주는 방법을 사용할 수도 있겠으나, swift 기준으로 max의 시간복잡도가 O(n) 이고 max의 인덱스를 찾는데 O(n), 이를 제거하는데 O(n) 의 시간이 소요됩니다..
-
1217. Play with ChipsAlgorithm/LeetCode 2020. 5. 28. 13:40
출처: leetcode.com/problems/play-with-chips/ 분류: Greedy, Easy 접근방식 문제 자체를 이해하기가 어려웠던 문제였습니다. 간단히 요약하면, chips 에는 chip이 있는 index 가 적혀있습니다. 즉, chips = [2,2,2,3,3] 이렇게 주어져 있다면, 아래와 같은 모습으로 생각할 수 있습니다. 칩이 있는 인덱스 1 2 3 칩의 개수 0 3 2 이 칩들은 좌우로 2칸을 움직일 때는 비용이 없고 1칸을 움직일 때는 1의 비용이 듭니다. 여기서 이 칩을 한 곳으로 모으는 방법은 2가지 방법이 있습니다. 2에 있는 칩3개를 3으로 옮기는 방법 --> 비용 2 3에 있는 칩 2개를 2로 옮기는 방법 --> 비용 3 당연히 3을 2로 옮기는게 좋겠죠?? 다음으로..
-
1221. Split a String in Balanced StringsAlgorithm/LeetCode 2020. 5. 23. 21:34
출처: https://leetcode.com/problems/split-a-string-in-balanced-strings/ Split a String in Balanced Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 분류: Greedy, Easy 접근방식 "L", "R"로 이루어진 문자열에서 짝이 맞는 문자열의 개수가 얼마나 되는지 찾는 문제입니다. 저는 처음에 L 과 R 의 개수를 저장하는 변수를 만들고 카운트 해주면서 둘이 같아지면 ba..