짱아의 개발 기록장

dfs중에서도 hard난이도에 해당되는 문제이다. Tree문제인데, BST의 두 노드가 바뀐 상태로 입력이 주어져질 때, structure을 바꾸지 않고 recovery하면 된다. 솔직히 InorderTraversal 후 모든 두 개의 값을 reverse해주고 오름차순으로 정렬되는 지 BruteForce로 일일히 확인하는 그런 방법 밖에 생각이 나지 않아서.... 다른 외국 유투버의 풀이방법을 참고했다. 간단한 로직은 다음 사진으로 첨부했다. 사진 그대로 1) 역전되는 곳이 1pair 생긴다면, 첫 번째 값을 first로, 두 번째 값을 second로 간주했다. 2) 역전되는 곳이 2pair 생긴다면, 첫 번째 pair의 첫 번째 값을 first로, 두 번째 pair의 두 번째 값을 second로 간주했..

dfs와 트리를 결합한 문제이다. Binary Search Tree의 특징에 대해 잘 이해하고 Tree의 Traversal이 어떻게 이루어지는 지 잘 이해하고 있으면 쉽게 풀이할 수 있다. [메인 로직] root->left, root->val, root->right순으로 dfs를 진행했다. 즉, Inorder Traversal을 통해 문제를 해결했다. 여기서 핵심은, BST의 경우 Inorder Traversal을 했을 때에 모든 값들이 오름 차순 정렬이 되어 있어야 한다는 것이다! root->val값들을 모두 vector에 저장해놓은 후, v[v.size()-1]의 값과 비교하여 이 값보다 작다면 무조건 false를 반환하도록 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

오랜만에 dfs문제를 풀고 싶어서 LeetCode에서 dfs태그로 들어갔다. 재밌는 문제가 많아보였지만 역시 첫 번째 문제부터 들어갔다. 간단하게 dfs 재귀 방식으로 풀 수 있었다. [메인 로직] vector에 2~9까지의 idx에 각각 해당되는 문자를 넣어주었고 dfs로 digits에 해당되는 문자를 하나씩 탐색했다. 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 42 43 44 class Solution { public: vector ans; vector phone[11]; void dfs(string digits, int idx, string..

생각보다 이런 유형의 문제들이 여러 기업들의 코딩테스트에 많이 출제된다. 거의 대부분 이런 문제들은 투포인터로 푸는 것이 시간복잡도를 줄일 수 있는 현명한 방법이다. 물론, Brute Force로 풀 수 있겠지만... O(n^2)이면 크기에 따라 Time Limit이 찍힐 수도 있다. LeetCode의 경우 C++기준으로 Time Limit이 뜬다. 투포인터 시간복잡도 : O(n) 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 // Two-pointer class Solution { public: int maxArea(vector& height) { // 어차피 짧은 높이에 의해 넓이가 결정되기 때문에 // 맨끝 양쪽에서 ..

팰린드롬인지 판별하는 문제였다. 크게 2가지 방법으로 해결할 수 있었다. 1. for문으로 문자열 역전하기 시간복잡도 : O(n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: bool isPalindrome(int x) { string original = to_string(x); string reversed = ""; for(int i=original.size()-1; i>=0; i--){ reversed += original[i]; } if(original==reversed){ return true; } return false; } }; Colored by Color Scripter cs 2. 나머지와 몫으로 문자열 역전하기 시간복잡..

integer값을 반대로 출력하는 문제였다. [핵심 포인트] 가장 핵심 포인트는! 형변환이었던 것 같다. 32-bit signed integer range: [−231, 231 − 1]라고 범위가 명시되어 있었다. 특히, 음수의 경우 음수에서 양수로 바꾸면 딱 정수의 범위를 넘어가는 경우가 나올 수 있기 때문에,,,(ex.-2147483648) long long형으로 바꾸어서 string으로 변환했다. 12345678910111213141516171819202122232425262728293031323334#include class Solution {public: int reverse(int x) { bool isMinus = false; string s = ""; if(x=0; i--){ temp +=..

행과 열에 대한 개념을 확실하게 알고 있으면 쉽게 풀 수 있는 문제이다. [메인 로직] 1. (numRows-1)만큼 일직선으로 내려간 후(내려가면서 행+1, 열은 그대로) 2. (numRows-1)만큼 대각선으로 올라간다.(행-1, 열+1) 말 그래도 zigzag의 형태로 행과 열을 조절하면 된다. 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 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public: char map[1001][1001]; string convert(string s, int ..

팰린드롬 문제인데... 사실 풀이 방법은 여러가지가 있는 듯하다. DP, Brute Force 등... 하지만, 일단 글쓴이는 Brute Force 방법 밖에는 생각이 나지 않아 이 방법으로 풀이를 했다. 추후, 다양한 방법에 대한 풀이를 update해보겠다. Brute Force 시간복잡도 : O(n^2) 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 // BruteForce class Solution { public: string..