짱아의 개발 기록장

앞서 풀었던 3Sum문제와 거의 동일하지만 조금 더 쉽다고 할 수 있다. 3Sum은 각각의 요소들을 직접 출력해야 했지만 이 문제는 그냥 가장 가까운 값의 합만 출력하면 되기 때문! [메인 로직] 풀이는 거의 동일하지만, int diff라는 변수를 INT_MAX로 초기화하고 차이(abs(sum-target))가 더 작은 값들을 발견하면 계속적으로 갱신해주면 된다. 단! diff에 abs(sum-target)값을 넣어주면 나중에 정확히 sum을 구하기 어렵기 때문에 그냥 sum-target을 저장한다. 123456789101112131415161718192021222324252627class Solution {public: int threeSumClosest(vector& nums, int target) ..

Two Pointers 문제이다. [메인 로직] i, low, high값을 잡아서 3개의 값을 더해준 sum과 0을 비교해서 작을 때, 클 때, 같을 때 조건을 통해 구현해주면 된다. 앞에서 sort를 했기 때문에 0보다 작으면 -> low++ 0보다 크면 -> high-- 0과 같으면 바로 ans에 넣어주고 혹여나, 중복되는 vector를 ans에 넣을 수 없기 때문에 ex) [-1, 0, 1] == [-1, 0, 1] low와 high를 같은 값이 아닐때 까지 while문으로 처리해주어야 한다!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 4..

처음 queue를 사용해서 문제를 풀었을 때는, 시간이 faster than 13.36%가 나와서,,,, 큰일났다 싶었다. 따라서, 다른 분들의 풀이를 참고해서 큐를 사용하지 않고 그냥 dfs로도 풀어보았다. 1. runtime -> faster than 13.36%, memory -> less than 62.96% 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: vector levelOrderBottom(TreeNode* root) { queue q; q.push(root); vector ans; stack st; while(!q.empty(..

예전에 백준에서 비슷한 문제였던 전화번호 목록?을 풀었던 기억이 있어서 비교적 쉽게 접근할 수 있었다. [메인 아이디어] 일단, 문자열 배열을 정렬하면 어떤식으로 정렬이 되는 지를 알아야 하는게 우선이다! 문자열 배열 ["flower", "flow", "flo", "fl", "snack", "sna", "s"]를 정렬하면, ["fl", "flo", "flow", "flower", "s", "sna", "snack"] 과 같이 정렬이 된다. 즉, 접두사가 일치하는 문자열 끼리 정렬이 되고 그 후에 알파벳 순서로 정렬된다. 위의 특성을 잘 활용하면 문제를 빠르게 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..

정말 간단한 dfs로 트리의 높이를 구하는 문제였다. 머리를 깨워주기 위해..ㅎㅎ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int height = 1; void countMaxHeight(TreeNode* node, int h){ if(node==NULL){ height = max(height, h); return; } countMaxHeight(node->left, h+1); countMaxHeight(node->right, h+1); } int maxDepth(TreeNode* root) { if(root==NULL) return 0; countMaxHeight(root->left, 1); ..

사실 문제 유형은 DP(Dynamic Programming)으로 분류되어 있었지만, 그냥 구현? 문제로 풀었다. 아이디어는 문제의 Discuss 탭에 있는 외국인 분의 코드를 보고 얻었다...ㅎ [메인 로직] 최대 합을 저장하는 변수 ans, 매 번 큰 값을 비교하여 저장하는 변수 sum을 두고 탐색하는 식으로 구현했다. 예를 들어, [-1, 2, 3]의 배열이 있는 경우 idx = 1 => -1+2 2+3 > 3 이기 때문에 계속 더해주는 것이 이득이다. 따라서, sum = 5가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution..

앞서 풀었던 Combination Sum 과 매우 유사한 문제이다. 하지만, 이 문제는 중복허용이 되지 않는 다는 것! [메인 로직] ex) 10, 1, 2, 7, 6, 1, 5 / target = 8이라면 먼저 오름차순 정렬해준다. 1, 1, 2, 5, 6, 7, 10 으로 정렬된 상태에서 idx = 0부터 target = 8인 조합을 찾아나가면 [1, 2, 5]를 완성할 수 있다. 하지만 idx = 1도 '1'이기 때문에 중복된 결과를 만들게 된다. 따라서, 중복된 값을 만들지 않기 위해!! for문 탐색할 때, if(i>start && candidates[i]==candidates[i-1])이라면 continue를 해서 중복을 막았다. 12345678910111213141516171819202122..

backtracking문제를 너무 오랜만에 풀어서 약간 푸는 데 생각보다? 오래걸렸다. [문제 설명] Input: candidates = [2,3,6,7], target = 7 다음과 같이 배열이 주어지면 그 안에서 합이 target이 될 수 있는 조합을 찾는 문제이다. 위와 같은 input이라면, Output: [[2,2,3],[7]] 이러한 결과가 나올 수 있다. 주의할 점은!! [2, 2, 3] = [2, 3, 2] = [3, 2, 2] 모두 같은 값으로 취급한다는 것! [메인 로직] dfs함수의 인자값으로 지금까지의 값의 합 / 지금까지의 값들을 넣는 벡터 / candidates벡터 / target값 / 다음에 탐색을 시작할 idx값을 넣어주었다. 만약, 다음에 탐색을 시작할 idx값을 넣어주지 ..