Problem solving/LeetCode22 [LeetCode] 20. Valid Parentheses (C++) 문제 괄호들이 주어질 때 괄호 구문이 올바른지 여부 생각할 것 자주 나오는 유형의 문제로 나는 항상 스택을 활용했다! 한 방향의 괄호를 넣고 반대 방향의 괄호가 나올 때 스택에서 가장 위에 있는 값을 비교하며 없앤다. 마지막에 스택이 비어있는 경우에만 유효한 구문이다. 코드 class Solution { public: bool isValid(string s) { stack st; for(int i=0; i 2023. 6. 30. [LeetCode] 19. Remove Nth Node From End of List (C++) 문제 링크드리스트의 head가 주어졌을 때, 끝에서 n번째 노드를 제거하고 head를 리턴 주어진 리스트 노드의 구조는 다음과 같다 * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ 생각할 것 어떤 노드를 제거할 지 찾기 head node만 주어졌으므로 노드들의 정보를 저장하면서 tail노드를 찾아야한다. a. next가 Nullptr인.. 2023. 6. 30. [LeetCode] 17. Letter Combinations of a Phone Number (C++) 문제 위의 사진의 2부터 9 숫자 버튼에 문자가 포함되어 있다. 중복되지 않는 모든 가능한 문자열을 찾기 생각할 것 입력으로 들어온 숫자 하나에 대해 모든 문자를 하나씩 대입해야 할 것이다! 반례 빈 digits로 시작했을 때 빈 문자열을 배열에 추가하는 문제 input : digits = "" output : [""] expected : [] 유효하지 않은 결과이므로 배열에 추가하면 안된다! if(strs.size() > 0) 인 경우에만 문자열을 결과배열에 추가하도록 수정했다. 코드 class Solution { public: vector res; vector m = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; string .. 2023. 6. 29. [LeetCode] 15. 3Sum (C++) 문제 정수 배열이 주어졌을 때, i ≠ j i ≠ k j ≠ k nums[i] + nums[j] + nums[k] == 0 결과에 중복된 트리플을 포함하지 않는다 즉, 3개의 값이 모두 다르고 합이 0인 정수 3개 묶음을 리턴하기 생각할 것 브루트포스를 사용한다면 O(n^3)의 시간복잡도가 소요된다. 하지만 배열의 최대 인자 개수가 3000개이므로 3000 * 3000 * 3000 = 3 * 3 * 3 * 10^9 최대 10의 9제곱이상의 연산이 필요할 수 있다. → 보통 1초 제한이라고 하면 1억개의 연산이 소요된다고 여기며 그 이상일 경우 시간 제한에 걸리는 경우가 많다. 다른 방법으로 투포인터를 활용할 수 있다. 가장 먼저 정수 배열을 정렬한다. low 값 하나를 고정하고 다음 값을 투포인터를 활용.. 2023. 6. 29. 이전 1 2 3 4 5 6 다음
