PS/PS Log

23.05.06. 풀었던 문제들

Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition 일단 이 문제를 brute-force로 푼다면, length n인 것들에 대해 모든 subset을 봐야 하므로 $2^n$ 개수를 보아야 한다. 그러나 n이 100,000이기 때문에 시간 초과가 무조건 난다. 다른 방법을 풀어야 한다. 이 문제는 two-pointer로 푸는 문제이다. 만약 array가 정렬된 상태에서 어떤 subarray를 골랐다고 치자. 정렬된 상태이므로 subarray의 첫 번째 index, 마지막 index element만 가져와서 target의 값과 비교하면 된다. 그 합이 target보다 작다면 해당 subarray의 모든 subset은 문제 조건..

23.05.04. 풀었던 문제들

Leetcode 649. Dota2 Senate Greedy + Queue를 사용하는 문제. 2개의 종류 R, D가 있을 때 이 문제는 앞에서부터 선택권을 가지기 때문에, 자신보다 뒤에 있는 다른 종류의 char를 없애는 것이 제일 optimal한 선택이다. 예를 들어 RD가 있다고 하자. 만약 D의 차례에서 자신보다 앞에 있는 R의 char를 없애는 것을 optimal이라 하자. 그러나 순서는 R부터이기 때문에 R은 D를 지울 수 있다. 따라서 이건 optimal이 아니므로 - 자신보다 뒤에 있는 다른 종류의 char를 지우는 것이 제일 optimal이다. (greedy) 자신보다 뒤에 있는 다른 type의 char를 없애는 것을 반복한다면 다시 처음부터 시작하게 되는데, 결국 환형을 이루게 된다. -..

23.05.02. 풀었던 문제들

Leetcode 1822. Sign of the Product of an Array nums의 모든 element 곱이 양수인지 음수인지 0인지 리턴하는 문제. 당연히 전부 다 곱하면 overflow 나니까 0이 있으면 return 0, 아니면 음수 개수가 짝순지 홀순지 판별하면 되는 문제이다. // Runtime 7 ms Beats 57.19% // Memory 10.2 MB Beats 45.94% class Solution { public: int arraySign(vector& nums) { int isNegative = 1; for(int n : nums){ if(n == 0) return 0; if(n < 0) isNegative *= -1; } return isNegative; } }; 시간복..

23.05.01. 풀었던 문제들

Leetcode 1491. Average Salary Excluding the Minimum and Maximum Salary 주어진 배열에서 max값, min값을 뺀 값들의 평균을 구하는 문제. 전체를 sort하고 min, max값만 빼고 평균 구해도 되지만 그러면 시간복잡도가 O(nlogn)이다. 그냥 한 번 순회하면서 min, max값, sum 구하고 구하는 게 나을 거라 생각했다. // Runtime 0 ms Beats 100% // Memory 7 MB Beats 98.74% typedef long long ll; class Solution { public: double average(vector& salary) { ll sum = 0, minValue = INT_MAX, maxValue = I..

23.04.30. 풀었던 문제들

Leetcode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable 어제 문제를 풀었다면 접근을 조금 쉽게 할 수 있는 문제. 문제 힌트에도 대놓고 [graph를 완성한 후 비교하는 것이 아니라, 거꾸로 생각해라] => [0부터 build해나가는 식으로 만들어라] => 즉, union-find를 이용해 graph를 이어나가면 된다. A와 B 각각의 edge를 union-find를 이용해 graph를 만들어가는 방법을 생각했다. 단 주의해야 할 부분으로 A, B로만 edge를 만들고 common edge 중 없앨 수 있는 edge만 없앨지 common edge로 기본 graph를 만들고, A, B edge 중 사용해야 하는 것만 사용하고 나머..

23.04.29. 풀었던 문제들

1697. Checking Existence of Edge Length Limited Paths edge 간 weight가 있는 어떤 graph와 [vertex 1, vertex 2, limit]으로 주어지는 query list가 있을 때 각 query의 vertex 1부터 vertex 2까지 path 중 max값이 limit보다 작으면 true를, 아니면 false를 계산하는 문제. vertex 개수를 V, edge 개수를 E, query 개수를 Q라고 했을 때 0

23.04.28. 풀었던 문제들

Leetcode 839. Similar String Groups n이 작다는 점에서 2중for문을 고려할 만한 문제. DFS와 같은 방식으로, [어떤 string과 유사한 string]을 찾으면 계속 이어 나가서 하나의 group을 만들어야 한다. 단순 DFS로만 구현해도 되긴 하다. DFS로 구현하면 어떤 string을 탐색할 때 모든 strs를 탐색하며 유사한 것을 찾고, 찾는다면 그것으로 DFS를 한다. 찾은 것은 따로 넘버링을 하고 넘버링의 개수를 리턴한다. 나는 union-find로 구현했다. union-find 특성상 dfs보다 좀 더 빠르고 메모리도 적게 사용할 것이라 생각했기 때문. Union-find는 내가 작성했던 포스트와 동일하게 구현했다. 그러면 이 문제의 메인 로직. 2중 for문..

23.04.27. 풀었던 문제들

Leetcode 319. Bulb Switcher 오늘 풀었던 문제는 좀 레전드인 것 같다. 이 문제는 어떤 수 i의 약수 개수를 쉽게 풀 수 있다면 쉽게 풀 수 있는 것으로 보인다. i의 약수 개수만큼 bulb가 꺼졌다 켜졌다 하기 때문이며, 결과적으로 i의 약수 개수가 홀수면 켜져 있는 상태가 될 것이다. 따라서 1

23.04.26. 풀었던 문제들

Leetcode 258. Add Digits 어떤 수 n이 있을 때 n의 자리수를 모두 합쳐 n을 만든다. n이 한 자리가 될때까지 이것을 반복하는 문제. 첫 번째 접근 trivial하게 단순 구현으로 접근. // Runtime 0 ms Beats 100% // Memory 5.9 MB Beats 63.10% class Solution { public: int addDigits(int num) { while(num >= 10){ int temp = 0; while(num){ temp += num % 10; num /= 10; } num = temp; } return num; } }; 시간복잡도 n이 INT_MAX면 $2^32$, 약 21억이다. 그러나 21억의 모든 자리수를 합쳐도 약 180정도로 3자리..

23.04.25. 풀었던 문제들

Leetcode 2336. Smallest Number in Infinite Set 2개의 값으로 쉽게 풀 수 있다. 처음에는 pq로 두었는데... 이렇게 두면 이미 addBack한 숫자를 또 addBack하는 경우 중복이 발생하는데 이를 해결하지 못한다. 따라서 set으로 해결했다. infinite set에서 제일 작은 숫자인 start 변수, 그리고 infinite에 있지 않은, popSmallest() 한 이후에 addBack()된 숫자들을 저장하는 목록 s을 둔다. popSmallest()의 경우, s에 값이 있는 경우 무조건 start보다 작은 수가 s에 들어가 있는 것이므로 s에서 제일 작은 숫자를 pop하고 그것을 리턴한다. 그렇지 않다면 start값을 리턴하고, start++한다. addB..

23.04.24. 풀었던 문제들

Leetcode 1046. Last Stone Weight PQ를 이용하면 쉽게 풀 수 있는 문제. 딱히 설명할 거리도 없다,,, // Runtime 0 ms Beats 100% // Memory 7.7 MB Beats 41.71% class Solution { public: int lastStoneWeight(vector& stones) { priority_queue pq; for(int stone : stones) pq.push(stone); while(pq.size() > 1){ int f = pq.top(); pq.pop(); int s = pq.top(); pq.pop(); if(f != s) pq.push(abs(f - s)); } if(pq.empty()) return 0; return pq..

23.04.23. 풀었던 문제들

1416. Restore The Array 일단 문제 조건이 n = 100000이므로 O(n)으로 풀어야 하는 문제이다. 따라서 1D array dp[i]를 둔다. 처음엔 dp[i]를 0부터 i까지 만들 수 있는 경우의 수로 생각하려 했는데 그러면 dp[i+1]을 구하기 까다로워 거꾸로 정의했다. dp[i] : i부터 n까지 가능한 경우의 수라고 정의 그러면 다음으로 점화식을 세워야 한다. 처음에는 i부터 k length만큼 전진하고, 각 단계에서 number를 만들고 k와 비교하려 했다. 그런데 그러면 k와 비교하는 로직이 중복되어서 숫자를 만들고, 숫자가 k보다 작으면 더하는 게 구현하기 편할 것 같았다. 일단 dp[i]를 계산하기 위해 i부터 substring을 만들고, 이 때 substring이 ..

23.04.22. 풀었던 문제들

Leetcode 1312. Minimum Insertion Steps to Make a String Palindrome longest palindrome subsequence length(x라고 하자)를 알아내면 되는 문제이다. 왜냐하면, 전체 길이를 n이라 할 때, n - x를 하면 되기 때문이다.longest palindrome subsequence는 이미 palindrome이기 때문에 나머지 부분인 n - x인 부분만만 채워 넣으면 palindrome이 되기 때문이다. 그렇다면 쉬운 문제다. longest palindrome subsequence를 찾는 건 LCS와 유사한 DP로 쉽게 풀 수 있다. dp[i][j]를 index i to j까지 longest palindrome subsequence ..

23.04.21. 풀었던 문제들

Leetcode 879. Profitable Schemes 또 그놈의 3D DP이다. 문제를 보고 일단 knapsack같은 문제인가? 라고 생각했다. 일단 문제 조건이 n=100으로 아주 널널한 편이어서 아마 3D DP일 거라 생각했다. 100 * 100 * 100은 백만으로 딱 $n^3$으로 적당히 풀리는 문제니까. 첫 번째 접근 그래서 dp[i][j][k]를 세우고 어떤 식일까 유추했다. i부터 j까지 k명 썼을 때 가능한 개수? 음... 모든 case에 대해 각 case가 얻은 profit을 얻어야 다음 경우를 계산할 수 있다. 기각. i부터 j까지 k원 썼을 때 가능한 개수? 음.. 모든 case에 대해 각 case가 몇 명을 사용했는지가 있어야 다음 경우를 계산할 수 있다. 그러면 변수가 [어떤..

23.04.20. 풀었던 문제들

Leetcode 662. Maximum Width of Binary Tree 첫 번째 접근 (Wrong) 모든 vertex에 대해 해당 vertex가 몇 번째 vertex인지 index를 매긴다. (binary tree를 array로 변환하는 것과 같이) left가 있으면 cur vertex index * 2, right는 cur vertex index * 2 + 1로. 그러나 이렇게 풀면 문제 제한조건에서 vertex가 max 3000개이므로 2^3000을 계산해야 한다. 엄...이다. overflow가 나지 않는 방법을 생각해야 한다. typedef pair pii; class Solution { public: vector depthInfos; // depthInfos[i].first : depth ..

23.04.19. 풀었던 문제들

Leetcode 1372. Longest ZigZag Path in a Binary Tree 어떤 binary tree가 주어졌을 때, zigzag로 탐색한 가장 긴 path length를 찾는 문제. 여기서 zigzag는 왼쪽 - 오른쪽 - 왼쪽 - ... , 또는 오른쪽 - 왼쪽 - 오른쪽 - ... 와 같이 [이전에 탐색한 방향]과 [이번에 탐색한 방향]이 다른 경우로 정의한다. dfs를 하면서 top-down으로, 그러니까 parent의 값을 child에 넣고, 탐색 종료 시 정답을 갱신하는 방식이 아니라 child의 값을 parent로 끌어올리면서 정답을 계산해야 하는 문제 같다.정확하게 문제는 기억나질 않는데, 프로그래머스에서 이런 유형의 문제를 풀었던 것 같다. 일단 해설하자면, root부터..

23.04.18. 풀었던 문제들

Leetcode 1768. Merge Strings Alternately string 2개를 index 하나씩 합치는 문제. merge-sort를 알고 있다면 merge하는 방식으로 쉽게 구현할 수 있다. // Runtime 2 ms Beats 50.88% // Memory 6.5 MB Beats 19.57% class Solution { public: string mergeAlternately(string word1, string word2) { int i = 0, j = 0, len1 = word1.length(), len2 = word2.length(); string result = ""; while(i < len1 && j < len2){ result += word1[i]; i++; result ..

23.04.17. 풀었던 문제들

Leetcode 1431. Kids With the Greatest Number of Candies 설명할 필요도 없는 간단한 문제. candies[i] + extraCandies가 max value of candies보다 크거나 같으면 extraCandies는 candies vector에서 max값이 될 수 있다. // Runtime 0 ms Beats 100% // Memory 8.9 MB Beats 86.24% class Solution { public: vector kidsWithCandies(vector& candies, int extraCandies) { int n = candies.size(); int maxCandies = *max_element(candies.begin(), candies..

23.04.16. 풀었던 문제들

Leetcode 1639. Number of Ways to Form a Target String Given a Dictionary DP 문제. 처음에 이해를 잘못해서 어렵게 푼 문제... words가 [abbac, eabbc, abbbc]와 같이 주어졌을 때 아래처럼 정렬해 보자. abaac eabbc abbbc 이렇게 두고, 만약 words[1][1]의 a를 골랐다고 하면 모든 word에 대해 index 1 이하인 것은 사용할 수 없다. ab / aac ea / bbc ab / bbc 이렇게 생각하면 words의 어떤 column j을 이용해 target[i]를 만들 수 있는지 여부를 판단하면 될 것 같다. 따라서, dp[i][j] : substring j까지 ith col 이용해 만드는 경우의 수라고..

23.04.14. 풀었둔 문제들

Leetcode 516. Longest Palindromic Subsequence subsequence 중 가장 긴 palindrome을 찾는 문제다. LCS를 찾는 것처럼 DP를 이용해야 한다는 것을 직관으로 알았다. dp[i][j]를 index i부터 index j까지 longest palindrome length라고 두자. base case : s[i], 길이가 1인 substring은 palindrome이다. 모든 i에 대해 dp[i][i]를 1로 초기화한다. dp[i][i]부터 길이를 한 칸씩 늘려가면서 탐색할 것이다. 아래 표를 참고하자. 0 1 2 3 0 1번째 탐색 2번째 탐색 3번째 탐색 4번째 탐색 1 1번째 탐색 2번째 탐색 3번째 탐색 2 1번째 탐색 2번째 탐색 3 1번째 탐색 대..

23.04.13. 풀었던 문제들

Leetcode 946. Validate Stack Sequences programmers에서 풀어 본 stack simulation 문제이다. 2개의 vector가 주어지며 pushed vector 순서대로 숫자가 주어졌을 때 push를 자유롭게 한다. 이 때 popped vector 순서대로 숫자를 pop할 수 있는지 여부를 도출하는 문제다. 첫 접근 처음 떠올린 아이디어는 다음과 같다. 모든 숫자가 0보다 크거나 같고 1000보다 작거나 같으므로 isPushed라는 flag를 하나 만든다. ... 1 popped vector를 순회한다. 그 값(v라고 하자)이 unpushed인 경우, 그 수가 나올 때까지 stack에 push한다. ... 2 push 할 때, isPushed를 true로 마킹한다...

23.04.12. 풀었던 문제들

Leetcode 71. Simplify Path 이번 주는 stack 관련된 문제가 나오는 주인가보다. 계속 stack 문제가 나온다. 일단 문제 조건은 directory 구분은 /로 한다. //와 같이, / 사이가 빈 경우에는 아무것도 하지 않는다. .은 아무것도 하지 않는다 ..은 상위의 directory를 가리킨다. 그러면 /를 delimiter로 사용해 parsing한 뒤, "."이나 ""가 나오면 아무것도 하지 않고 ".."가 나왔을 때만 stack에서 pop하면 될 것이다. 그리고 그 결과를 계산하면 될 것. 사실상 string parsing문제임을 알 수 있다. 기억하자. string parseing은 stringstream, buffer, delimiter, while(getline) 4개..

23.04.11. 풀었던 문제들

Leetcode 2390. Removing Stars From a String 문제를 보면 stack을 쓰는 쉬운 문제라는 것을 깨달을 수 있다. 어제 풀었던 문제와도 같은 문제. 그러나 stack을 쓰면 O(n)만큼 쓰고, 또 그걸 string에 넣어야 하니까 O(2n)이 된다. 그래서 그냥 바로 string을 쓰면 된다. string에 push_back(또는 + 연산), pop_back 연산이 있기 때문이다. // Runtime 68 ms Beats 95.74% // Memory 25.9 MB Beats 57.75% class Solution { public: string removeStars(string s) { string answer = ""; for(char c : s){ if(c == '*'..

23.04.10. 풀었던 문제들

Leetcode 20. Valid Parentheses stack을 사용할 줄만 안다면, 쉽게 구현할 수 있는 문제. 백준의 stack의 첫 문제였던 것으로 기억한다. // Runtime 0 ms Beats 100% // Memory 6.2 MB Beats 81.54% class Solution { public: bool isValid(string s) { stack stk; for(char c : s){ if(c == '(' || c == '[' || c == '{') stk.push(c); else{ if(stk.empty()) return false; if(c == ')'){ if(stk.top() == '(') stk.pop(); else return false; } else if(c == ']'..

23.04.09. 풀었던 문제들

Leetcode 1857. Largest Color Value in a Directed Graph 문제를 읽고, 일단 귀찮은 문제라는 것은 깨달았다. 해야 하는 것만 해도 cycle 존재 여부 검증 cycle이 없는 경우, 모든 path에 대해 모든 색깔의 경우의 수를 구해야 한다. 이 문제의 경우 outgoing edge가 1개라는 조건이 없기 때문에 일반적인 directed graph에서 cycle 여부를 검증하는 방법을 사용해야 했고, 모든 path를 탐색해야 한다는 점에서 topological sort가 떠올랐다. 그러나 topological sort를 사용한 지 오래되어서 해당 구현은 이전에 쓴 게시글을 참고했다. topological sort의 큰 로직은 아래와 같다. source vertex..

23.04.08. 풀었던 문제들

Leetcode 133. Clone Graph Node pointer로 이루어진 graph 하나를 clone하는 문제. 중복된 edge는 없고, 각 Node가 가지고 있는 val은 unique하다는 조건에서 시작한다. 사실상 그렇게 어려운 문제는 아니다. DFS나 BFS를 쓰고, 그 과정에서 몇 줄만 추가해 주면 되는 문제. 첫 접근 일단 BFS로 풀었다. naive하게 2번의 BFS를 했다. 첫 BFS에서는 unvisit인 모든 Node에 대해 clone을 생성한다. 생성한 Node clone들을 value를 key로 가지는 map에 저장한다. ... 1 두 번째 BFS에서는 edge를 연결한다. 첫 번째 BFS에서 모든 Node를 찾았기 때문에 두 번째 BFS에서는 모든 clone들의 edge만 연결..

23.04.07. 풀었던 문제들

Leetcode 1020. Number of Enclaves 첫 접근 어제 풀었던 문제와 동일한 문제. boundary에 있지 않으면서 0으로 둘러싸여 있는 1을 찾는 문제이다. 어제는 추가 공간을 할당해 모든 island의 좌표를 추가로 저장했는데, 그렇게 말고 i번째 island가 enclave인지 여부, 그리고 i번째 island에 있는 1의 개수를 저장했다. // Runtime 87 ms Beats 30.50% // Memory 35.1 MB Beats 14.72% int dr[4] = {1, 0, -1, 0}; int dc[4] = {0, 1, 0, -1}; class Solution { public: int m, n; vector grid; vector visited; vector isEncl..

23.04.06. 풀었던 문제들

Leetcode 1254. Number of Closed Islands 많이 보던 grid에서 섬이 몇 개 있는지 탐색하는 문제이지만 추가 조건으로 모든 땅이 물 안에 있어야 하는 조건이 추가된다. 이 문제에서는 땅이 0, 물이 1로 표현되기에 모든 0으로 표현되는 연결된 영역이 모든 1 안에 있어야 한다. 이를 판별하는 법은 0으로 연결된 영역이 grid의 테두리가 아니면 된다. grid의 테두리가 아닌 0으로 영역된 섬들은 모두 1로 둘러싸여 있기 때문이다. DFS로 grid[r][c]가 0인 connected island를 모두 찾는다. 찾으면서 해당 좌표를 islands에 push한다. ... 1 DFS가 종료되면 모든 islands에 대한 정보를 찾은 것이다. islands의 모든 좌표를 순회하..

23.04.05. 풀었던 문제들

2439. Minimize Maximum of Array 첫 접근 오름차순인 부분수열에 대해 그들의 평균값이 될 수 있고, 남는 것을 균등히 분배할 수 있다. 1 3 5라면 -> 3 3 3이 될 것. 1 3 6라면 -> 3 3 4가 될 것. 1 3 7라면 -> 3 4 4가 될 것. 따라서 오름차순 부분수열을 찾고, [그 부분수열 합의 평균] + [나머지 존재 then 1 else 0]이 답일 것이라 생각했다. 그러나 [6, 9, 3, 8, 14]와 subarr를 바꾼 결과가 [7, 8, 8, 8, 9]처럼 또 오름차순인 경우에는 문제가 발생하며, strictly increasing이 아니라 monotonic increasing인 경우도 포함해야 한다. 그래서 이 접근은 틀린 접근이다. 다음 접근 전체 수..

23.04.04. 풀었던 문제들

Leetcode 2405. Optimal Partition of String 첫 접근 greedy로 풀었다. 어떤 index i를 탐색할 때, 지금까지 본 char가 아니라면 지금 string에 push, 한 번이라도 봤던 char라면 다음 string에 push하는 방법이다. 만약 이게 optimal이 아니라면 string의 길이가 더 길어져야 한다는 것인데, 그렇다면 한 string에서 모든 char가 unique하지 않게 되므로 모순. 따라서 optimal이다. // Runtime 325 ms Beats 5.4% // Memory 88 MB Beats 8.67% class Solution { public: int partitionString(string s) { int answer = 0, i = ..