전체 글

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 == '*'..