PS/PS Log

23.09.25. 풀었던 문제들

Programmers Lv. 3 입국심사, 8분 parametric search. typedef long long ll; vector times; // t시간동안 심사할 수 있는 인원 수 ll calculateNumPass(ll t){ ll num_pass = 0; for(int time : times){ num_pass += ((ll) t / time); } return num_pass; } long long solution(int n, vector t) { ll start = 0, end = 1e18; times = t; while(start = n..

23.09.24. 풀었던 문제들

Programmers Lv. 3 보석 쇼핑, 19분 two-pointer를 활용하면 되는 문제. 유의할 점은 start와 end 사이에 있는 보석 개수를 세야 하는데, map으로 숫자를 세면 count에 O(보석 개수)만큼의 시간이 걸리고, multiset을 쓰면 identical한 보석 개수를 셀 수 없기 때문에 map과 set을 같이 썼다. set cur_gems; int num; map cur_gem_count; bool isContainAll(){ return cur_gems.size() == num; } void insert(string gem){ cur_gem_count[gem]++; cur_gems.insert(gem); } void erase(string gem){ cur_gem_count..

23.09.23. 풀었던 문제들

Programmers Lv. 3 불량 사용자, 28분 문제 자체는 주어진 것만 풀면 되는 문제. input size가 8이므로 최대 8!의 시간 복잡도이며, 따라서 backtrack(순열)로 풀면 된다. 단, 유의할 점은 `제재 아이디 목록을 구했을 때 아이디들이 나열된 순서와 상관없이 아이디 목록의 내용이 동일하면 같은 것으로 처리한다`이기 때문에, 이를 잘 처리해야 한다. 모든 banned_id에 대해 가능한 user_id의 후보군들을 나열하고, permutation/backtrack으로 가능한 모든 조합을 나열하고, 해당 조합에서 겹치는 것을 빼면 되겠네. 위 3가지 flow로 쉽게 처리할 수 있다. // banned_id와 user_id가 일치하는지 bool isBanned(string banne..

23.09.19. 풀었던 문제들

Programmers Lv. 3 여행경로, 17분 그냥 DFS 돌리면 되는 문제. 단 각각의 vertex가 string으로 표현되는 점과 [사용한 표]를 어떻게 표기할지에 대해 유의해야 한다. 뭐.. 정석 DFS처럼 각 ticket의 index를 visit했는지 안했는지를 표기할 수 있긴 한데. 결국 alphabet 순서로 DFS + edges를 만들어야 하기 때문에 map을 사용해야 할 것 같다. 처음에는 multiset을 썼었는데, DFS를 위해 multiset에서 element를 빼고 넣는 과정에서 계속 같은 위치를 참조하는 것 같았다. (무한루프) 그래서 map of map을 썼다. edges[i]는 i에 인접한 공항들의 map 목록이고, 이것은 [도착지 이름, 같은 표가 몇 개인지]를 나타낸다...

23.09.17. 풀었던 문제들

Programmers Lv. 3 베스트앨범, 15분 그냥 풀면 되는 구현 문제. 장르별 재생회수의 순서 장르 내부에서 재생회수의 순서 위 2가지에 대해 정렬되어 있어야 하기 때문에 map을 2개 써야 한다. 그냥 뭐.. map에 genre를 key로 넣어 재생회수 합계와 해당 genre에 속한 노래들의 {재생회수, index}를 저장하면 된다. int len; struct Info{ int play, index; }; struct cmp{ // 조건 1. play가 큰 것. // 조건 2. index가 작은 것. bool operator()(Info &a, Info &b){ if(a.play == b.play) return a.index > b.index; return a.play < b.play; } ..

23.09.14. 풀었던 문제들

프로그래머스 Lv. 2 최댓값과 최솟값, 4분 30초 c++에서 delimiter를 사용해 string을 파싱할 줄 알면 바로 풀리는 문제. iss 쓰고 while getline으로 풀면 된다! string solution(string s) { int min_v = INT_MAX; int max_v = INT_MIN; istringstream iss(s); string buffer; while(getline(iss, buffer, ' ')){ int v; if(buffer[0] == '-'){ v = stoi(buffer.substr(1)); v *= -1; } else{ v = stoi(buffer); } min_v = min(min_v, v); max_v = max(max_v, v); } return..

23.09.12. 풀었던 문제들

Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique, 30분 첫 접근 그냥 주는 대로 풀었다. 일단 각 char이 몇 번 나오는지 알아둬야 하니까 map같은 걸 써야 하는데, 이 문제의 경우 알파벳 소문자만 나오기 때문에 vector(26, 0)을 map처럼 쓰면 된다. 이후, 내림차순으로 정렬한다. 정렬한 후, 만약 겹치는 값이 있는 경우에는 해당 값을 1 줄이고, 해당 문을 다시 반복한다. 이 접근이 문제될 때는, 2 2 2와 같은 예시를 보자. 2 2 2에서 index 1이 2 1 2로 바뀐다. index 1에서 같은 값의 비교는 앞의 값만 보기 때문에 pass. index 2에서 앞의 값만 보기 때문에 pass한다. 문제가 ..

23.09.11. 풀었던 문제들

Leetcode 1282. Group the People Given the Group Size They Belong To, 30분 문제 자체는 빨리 풀었는데, 여러 개선을 한다고 시간이 좀 걸렸다. 첫 번째 접근 최대한 생각나는 대로 구현했다. groupMap은 특정 size를 가지고 있는 모든 group의 정보를 가지고 있다. 때문에 구현은 단순하다. 입력으로 받은 size의 group이 없는 경우 생성한다. 입력으로 받은 size의 group이 있는 경우, 해당 group이 존재하지만 아직 size만큼 차지 못하는 경우 - 해당 group에 현재 인원을 넣어준다. 해당 group이 있고, size만큼 찬 경우 - 새로운 group을 넣어준다. 이렇게 푸니까 runtime 22ms, beats 8.5%..

23.09.10. 풀었던 문제들

오늘은 프로그래머스 데브코스 PCCP를 풀었다. 총 4문제였는데, 1번, 2번, 3번을 풀었다. 4번은 시간이 없더라. 구현이 너무 복잡했다. 4번 문제를 손을 대야 lv4를 받고, 올솔해야 lv5를 받는다... 음... lv5는 기대 안했지만, lv4는 받을 줄 알았는데. 아쉽다.

23.09.09. 풀었던 문제들

Programmers PCCP 모의고사 #1 외톨이 알파벳, 5분 프로그래머스 짝지어 제거하기를 풀어봤다면 바로 이어져 나오는 중복 char를 쉽게 줄일 수 있다. stack을 쓰든, string의 뒤에 중복을 빼고 붙여넣든. 이 방법을 사용하면 중복을 제거할 수 있고, 그러면 map으로 count만 하면 된다. 간단한 손풀기 문제. #include #include #include #include #include using namespace std; string solution(string str) { stack stk; for(char c : str){ if(!stk.empty() && stk.top() == c) continue; stk.push(c); } map m; while(!stk.empty(..

23.09.08. 풀었던 문제들

Programmers 자물쇠와 열쇠, 53분 자물쇠에 열쇠를 넣어서 맞는지 보면 되는 문제. 문제 접근 자체는, N과 M이 20으로 매우 작아서 brute-force로 다 돌릴 수 있었고, 결국 구현 문제였다. 열쇠를 특정 크기로 자르는 것은 매우 귀찮고 힘들기 때문에, 그렇게 하는 것보다는 아래와 같이 for문으로 돌리는 것이 편하다. 총 N + 2M - 2 크기의 배열을 만들고, 가운데에 자물쇠를 배치한다. 자물쇠에 해당하는 좌표는 [M-1, M-1]부터 [N+M-2, N+M-2]까지다. 이후 열쇠를 모든 위치에 두고, 자물쇠를 해제할 수 있는지 본다. 열쇠는 [0, 0]부터 [N+M-1, N+M-1]까지 가능하다. 열쇠 위치를 옮겨가면서, 자물쇠에 해당하는 모든 좌표들의 숫자가 1이면 OK이다. #..

23.08.21. 풀었던 문제들 복기

Leetcode 459. Repeated Substring Pattern, 15분 주어진 대로 구현만 하면 되는 문제. 일단 substring으로 원 string을 표시하기 위해서는 substring의 길이가 s의 약수여야 한다. 만약 그렇다면, 해당 substring을 q개(s.length()/substr.length())만큼 만들어서 전체를 살펴보면 된다. // Runtime 19 ms Beats 64.17% // Memory 15.4 MB Beats 38.41% class Solution { public: bool repeatedSubstringPattern(string s) { int len = s.length(); for(int i = 0; i

23.08.17. 풀었던 문제들 복기

Leetcode 542. 01 Matrix, 20분 0과 1만 있는 matrix에서 0으로부터 거리를 리턴하면 되는 문제. 나는 BFS를 사용했다. 모든 0지점부터 BFS 탐색을 시작한다. 단, 갱신할 수 없는 위치라면(다른 0으로부터 더 가깝다면) 그곳은 탐색하지 않는다. 하나의 최적화를 추가하는데, 0에서 BFS를 각각 수행하는 것이 아니라(그렇게 하면 BFS가 10000번 수행될 수도 있다.) 모든 0을 queue에 넣고 한 칸씩 BFS 해 나가는 것이다. 그러면 0에 인접한 칸은 그 개수만큼 방문하지만, 다음 갱신할 칸은 1번씩만 방문한다. 그러면 worst case 최대 1만번 겹치는 탐색이 존재하고, 모든 칸을 1만번씩 방문하게 되므로 시간 내에 충분히 풀 수 있다. // Runtime 62 ..

23.08.16. 풀었던 문제들 복기

9646. 다이어그램과 태블로, 2시간 딱 보면 backtracking + purning으로 푸는 문제. 일단 아래로 내릴 수 있으면 내리고, 너무 많이 내려간 경우 다음 col로 넘어가는 형식으로 구현했다. 그러면 backtracking의 종료조건은 마지막 col을 탐색하고, 다음 칸을 탐색할 때 answer++를 해 주면 된다. 다음으로, backtracking 과정은 위/왼쪽에 있는 값을 보고 조건을 맞춘다. 여기서 하나 purning을 하는데, 아래 칸으로 내릴 수 있으면 바로 내리고, 그렇지 않으면 바로 다음 col을 탐색한다. 만약 이 과정을 recurse()에서 if문으로 걸면 call stack이 1번씩 더 쌓인다. worst case 모든 경우에 하나씩 더 쌓이게 되므로 이 과정을 여기로..

23.08.15. 풀었던 문제들 복기

Leetcode 86. Partition List, 25분 linked list에서 entry를 옮기는 방법을 알고 있으면 쉽게 풀리는 문제. 단, doubly linked list가 아니므로 head에 있는 값을 옮기기 위해 dummy head를 만들어야 했다. 접근 1. x보다 작은 것들만 옮기고, 기존 것들은 유지하는 방법. // Runtime 5 ms Beats 52.61% // Memory 10.3 MB Beats 21.22% /* x보다 작은 entry들은 다른 linked list로 옮기고, x보다 큰 entry들은 그대로 둠. - start pointer를 하나 두고, x보다 작은 것은 다 start로 옮김. x 이상인 것은 순서를 유지한 채로 head에 있을 것임. 이후 start와 원래..

23.08.11. 풀었던 문제들 복기

Leetcode 518. Coin Change II, 25분 백준 2293. 동전 1과 동일한 문제. 일단 2차원 dp로 푼다고 하면, dp[i][j] : coin i까지 봤을 때 j원을 표기할 수 있는 개수로 두자. i번째 coin을 안쓰는 경우 - dp[i][j] = dp[i-1][j] i번째 coin을 쓰는 경우 - dp[i][j] = dp[i][j-coin[i-1]] 위와 같이 되므로 이 점화식을 그대로 적용하기만 하면 된다. space complexity를 조금 개선할 수 있는데, dp[i][j] = dp[i-1][j]는 항상 고정이므로 dp를 1차원 배열로 만들수도 있다. // time O(nm), space O(nm) // Runtime 43 ms Beats 39.13% // Memory 1..

23.08.10. 풀었던 문제들 복기

Leetcode 53. Maximum Subarray, 25분 백준 1912 ,최대 연속 부분수열 합을 구하는 문제와 같은 문제. dp로 쉽게 풀 수 있다. 링크에 풀 수 있는 4가지 방법이 있다. // Runtime 76 ms Beats 96.56% // Memory 67.7 MB Beats 32.89% class Solution { public: int maxSubArray(vector& nums) { int n = nums.size(); int answer = -1e9, sum = 0; for(int i = 0; i>T; int x, y; for(int i = 0; i>x>>y; V[{x, y}] = 0; } queue q; // 좌표, dist q.push({0, 0, 0}); while(!q.e..

23.08.09. 풀었던 문제들 복기

BOJ 2224. 명제 증명, 30분 floyd warshall로 푸는 문제. floyd-warshall은 예전에 포스팅 한 적이 있다. floyd warshall의 특징은 모든 vertex에서 모든 vertex의 path weight를 최단거리로 만들고, 이를 위해 kij 순서로 for loop를 돌린다. typedef pair pcc; ////////////////////// write your code below // 모든 vertex에서 모든 vertex로의 path 여부를 알아야 하므로, floyd-warshall // directed임. int V = 52; int char2int(char c){ if(isupper(c)) return c - 'A'; if(islower(c)) return c..

23.08.08. 풀었던 문제들 복기

BOJ 7512. 연속하는 소수의 합 어떤 n1, n2, ... n$_m$이 주어졌을 때 연속된 n$_i$개의 소수의 합으로 나타낼 수 있는 가장 작은 소수를 찾는 문제. 처음에는 n개의 연속된 소수의 합을 빠르게 계산하기 위해 prefix sum을 사용했고, 메모리가 터졌다. 대체 왜..? 계산해 보면 그렇게 큰 값도 아닌데. ////////////////////// write your code below // 1000000000000 int INF = 1e7+1; //int INF = 312; vector primes; vector psum; void getPrime(){ vector isPrime(INF+1, true); isPrime[0] = isPrime[1] = false; for(int i ..

23.08.07. 풀었던 문제들 복기

Leetcode 74. Search a 2D Matrix, 25분 matrix가 정렬되어 있으므로 target이 있는 row를 찾고, 이후 col을 찾으면 된다. row를 찾을 때 binary search를 하고, col을 찾을 때 binary search를 하면 O(logm + logn)으로 해결할 수 있다. 이외에도, 모범답안은 전체를 하나의 array로 보고, index / m을 row index, index / n을 col index로 보고 O(log(m*n))만에 해결하는 방법도 있다. // Runtime 3 ms Beats 82.89% // Memory 9.6 MB Beats 19.73% class Solution { public: bool searchMatrix(vector& matrix, ..

23.08.05. 풀었던 문제들 복기

Leetcode 95. Unique Binary Search Trees II unique한 binary tree를 어떻게 만들지 ? ... 라고 생각하면. dp(start, end) = for all i in [start, end], dp[start, i-1] + dp[i+1, end] 로 풀면 된다. 이게 무슨 말이냐? start ~ end 사이에 있는 어떤 i를 root로 두고, 그 start ~ i-1은 왼쪽 subtree에, i+1 ~ right는 오른쪽 subtree에 넣는 DP라는 말이다. 그러면, left subtree와 right subtree의 cartesian product하면 모든 가능한 결과가 나온다. // Runtime 16 ms Beats 75.53% // Memory 16.1 ..

23.08.04. 풀었던 문제들 복기

Leetcode 139. Word Break, 1시간 첫 접근 처음에는 일단 brute-force로 접근했다. for문으로는 돌릴 수 없어서, dfs를 사용한 backtracking으로 접근했다. 코드는 뭐.. 간단하다. DFS(i)는 i부터 s.length()까지 만들 수 있는지 여부이다. 내부적인 구현은, i부터 모든 wordDict를 순회하면서 끝까지 도달할 수 있으면 true, 아니면 false인 식으로 class Solution { public: bool DFS(int i, string& s, vector& wordDict){ if(i == s.length()) return true; for(string word : wordDict){ int wordlen = word.length(); if(s..

23.08.02. 풀었던 문제들 복기

Leetcode 46. Permutations, 7분 어제와 마찬가지로 순열만 하면 되는 backtracking 문제. 마찬가지로 같은 포스팅에 작성해 두었다. 리트코드는 한 번 주제가 나오면 계속 그걸로 하는 느낌이라.. 뭔가 아쉽다. daily challenge가 분류 3개정도 나눠서 랜덤으로 하면 좋을 것 같다. // Runtime 3 ms Beats 67.29% // Memory 8 MB Beats 29.89% class Solution { public: vector answer; vector nums, result; vector isUsed; int N; void permutation(int cur_depth, int max_depth){ if(cur_depth == max_depth){ ans..

23.08.01. 풀었던 문제들 복기

Leetcode 77. Combinations, 8분 예전에 DFS로 순열/조합/중복순열/중복조합 코드를 썼었다. 코드야 그대로 쓰면 된다. 예전에 짰던 게 제일 깔끔하게 짜였던 걸로 기억했는데, 이번에 안 보고 짠 것도 비슷하게 짜진다. 다행이군. // Runtime 10 ms Beats 93.32% // Memory 9.9 MB Beats 56.99% class Solution { public: vector nums; vector answer; void combination(int cur_d, int max_d, int prev_idx, vector& result){ if(cur_d == max_d){ answer.push_back(result); return; } for(int i = prev_id..

23.07.31. 풀었던 문제들 복기

백준 2252. 줄 세우기 topological sort 문제. 처음에는 어떻게 풀지.. 생각했는데, 문제가 topological sort임을 깨달았다. 예전에 포스팅도 했었는데... 일단 topological sort의 핵심은, incoming edge가 0개인 vertex에서 연결된 모든 edge를 삭제하는 과정을 n번 반복하면 된다. 만약 n번 반복이 끝나기 전에 incoming edge가 0개인 vertex가 없다면, 어딘가에 cycle이 있다는 것이다. 또, edge를 직접 지우기에는 낭비가 심하니 incoming edge 개수 정보를 저장하고, edge를 삭제할 때 여기서 빼면 된다. vector edges; // edges[i] : src가 i인 edge array vector incomin..

23.07.29. 풀었던 문제들 복기

백준 14906 스러피 : 50분 사실상 regular expression을 구현하는 문제인데, regular expression만으로는 구현할 수 없기 때문에 무조건 string parse를 해야 하는 문제이다. 일단 slump와 slimp를 판별하는 것은 간단한데, 문제에서 주어진 조건을 그대로 풀면 된다. 그리고 slump의 경우에는 내부에 slump가 있고, slimp의 경우에는 내부에 slimp나 slump가 있다. 때문에 각 조건을 판별할 때 재귀로 slump인지 slimp인지 판별하기는 쉽다! 귀찮을 뿐이지. 이후, 전체 string은 slimp + slump로 구성되기 때문에 slump의 시작 지점을 잘 잡아야 한다. 그러나 어느 지점에서 시작하기 잡기 까다롭다. slimp 내부에 slum..

23.07.27. 풀었던 문제들 복기

2141. Maximum Running Time of N Computers binary search로 푸는 문제. 일단 제일 문제가 됐던 것은 time만에 batteries를 사용해서 n개의 computer를 동시에 돌릴 수 있는지를 O(b) 시간 안에 푸는 것이었다. 여기서 핵심은 time보다 큰 용량을 가진 battery들은 계속 컴퓨터에 꽂아두면 time만큼 쓸 수 있다. 그러면, 나머지, time보다 작은 용량을 가진 battery들로 나머지 컴퓨터의 사용 시간을 채워야 한다. 이 둘을 합친 것이 sum += min(time, b)이다. 만약 sum이 n*time보다 크다는 것은 battery들로 time만큼 쓸 수 있다는 것을 의미한다. // Runtime 160 ms Beats 95.32% /..

23.07.26. 풀었던 문제들 복기

Leetcode 1870. Minimum Speed to Arrive on Time 문제를 읽다 보니, binary search라는 느낌이 딱 왔다. 그리고 정리를 하다 보니, 아래와 같은 flow로 이건 무조건 binary search (parametric search)라는 생각이 들었다. 1. 불가능한 조건은 언제 나올까? 아무리 큰 speed로 dist[i]를 나누어도 올림한다. 즉, dist[i] 하나당 최소 1시간은 필요하다는 의미이다. (단, 마지막 dist[i]는 예외이다.) 따라서, hour 안에 도착하기 위해서는 n-1보다 큰 시간이 필요하다. 만약 hour 최대 10^7로 잡으면 된다는 것 같다. 여기서 binary search가 맞다는 것을 확신했다. 첫 접근 // Runtime 47..

23.05.09. 풀었던 문제들

Leetcode 54. Spiral Matrix 첫 접근 (wrong) 처음에는 위 그림처럼 풀려 했다. 결국 spiral로 풀기 때문에 겉면만 벗겨가면서 풀면 된다고 생각했기 때문이고, 가능하면 모든 변을 동일하게 접근하는 게 구현에서 쉬울 거라 생각했다. 일단 벗기는 회수는 row size를 m, col size를 n이라 했을 때 min((m+1)/2, (n+1)/2)이다. 이건 뭐 간단하게 나오는 답. 그러나 복잡한 경우는 matrix가 3 by 3라서 제일 겉면을 벗겼는데, 안에 딱 1개의 element만 남는 경우이다. [시작점]부터 [끝점-1]까지만 접근하기 때문에 이런 경우를 처리할 수 없다. 올바른 접근 (correct) 결국 한 번은 전부 다에 접근해야 한다. 구현의 편의를 위해 row ..

23.05.07. 풀었던 문제들

Leetcode 1964. Find the Longest Valid Obstacle Course at Each Position 일단 이 문제는 i까지 진행하면서 모든 obstacles에 대해 longest course length를 저장하면 될 것 같은 문제이다. 이 때, 각 course는 obstacles[i]부터 i = 0까지 내림차순으로 진행되어야 하며 i는 꼭 포함되어야 한다. 어디서 많이 본 접근 아닌가? 바로 LIS이다. 예전에 작성했던 DP + LIS 포스팅, lower bound & upper bound 포스팅 그대로 풀면 될 것이다. 단, 대신, 기존 LIS는 strictly increasing인 반면 이 문제는 monotinic increasing이다. 이를 고려해서 문제를 풀어야 한다..