23.02.25. 풀었던 문제들

리트코드 daily challenge - 121. Best Time to Buy and Sell Stock

 어떤 array가 주어지고, [ith element보다 뒤에 있는 것들 중 제일 큰 값 - ith element]을 maximize하는 문제. 실수했던 것은 answer가 0보다 작을 때는 0으로 출력해야 했는데, 이걸 인지하지 못했다.

 

 ith element보다 뒤에 있는 값들 중 제일 큰 값 - ith element를 모든 element에 대해 수행해야 한다. 그러나 이 접근을 flip해서, [ith element보다 앞에 있는 것들 중 제일 작은 것을 알아와서 ith element에서 그 값을 뺌]도 같은 문제가 된다. 이렇게 되면 앞에서부터 처리할 수 있어서 조금 편해진다.

 

 dp 문제인 것 같다.

• dp[i] = prices[0] ~ prices[i-1]까지 최소값
• dp[i] = min(dp[i-1], prices[i-1])
• answer = max(answer, prices[i] - dp[i])

 이렇게 점화식을 세우면 문제 조건을 해결할 수 있을 것 같다.

 

 그러나 조금 더 생각해 보면 굳이 dp array가 있을 필요가 없다는 것을 생각해 볼 수 있다. dp[i]는 dp[i-1]의 값만 사용하기 때문에, dp[i+1]에서는 dp[i-1]의 값을 사용하지 않는다. 따라서 이걸 prevMinValue라는 변수를 만들어서 처리해 주면 메모리를 더 적게 쓸 수 있다.

// Runtime 128ms, Beats 88.61%
// Memory 93.3MB, Beats 56.82%

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        // 초기 접근, array 이용
        // vector<int> dp(n, INT_MAX);
        // int answer = INT_MIN;
        // for(int i = 1; i<n; i++){
        //     dp[i] = min(dp[i-1], prices[i-1]);
        //     answer = max(answer, prices[i] - dp[i]);
        // }

        // 굳이 array 쓸 필요 없음
        int prevMinValue = INT_MAX, answer = INT_MIN;
        for(int i = 1; i<n; i++){
            prevMinValue = min(prevMinValue, prices[i-1]);
            answer = max(answer, prices[i] - prevMinValue);
        }

        return answer < 0 ? 0 : answer; // 실수 : profit 얻지 못할 경우 계산하지 않음
    }
};

 

시간복잡도

 for문에서 1부터 n까지 순회하기 때문에 O(n)이다.

 

공간복잡도

 dp 배열을 선언하면 O(n)이지만, dp 배열이 필요없기 때문에 O(1)이다.

 

 

프로그래머스 - 2022 카카오 인턴 코딩테스트

1. 성격 유형 검사하기

 손풀기 문제. 적당히 모듈화하면 쉽게 풀린다.

#include <string>
#include <vector>
#include <map>

using namespace std;

map<char, int> m; // [성격 유형]의 [점수] mapper
vector<string> order = {"RT", "CF", "JM", "AN"};

// survey와 choice가 주어졌을 때 해당하는 type에 점수를 추가
void addPointToType(string survey, int choice){
    if(choice < 4){ //앞
        m[survey[0]] += 4 - choice;
    }
    else if(choice > 4){ // 뒤
        m[survey[1]] += choice - 4;
    }
    // else then nothing
    // if empty map, then int value must set by 0
}

// m에 저장된 정보로 i번째 type을 리턴
char getIthType(int i){
    char first = order[i][0], second = order[i][1];
    if(m[first] >= m[second]){
        return first;
    }
    else return second;
}

// 해당 사용자의 type을 리턴
string getType(){
    string result = "";
    for(int i = 0; i<4; i++){
        result += getIthType(i);
    }
    return result;
}

string solution(vector<string> surveys, vector<int> choices) {
    int n = surveys.size();
    for(int i = 0; i<n; i++){
        addPointToType(surveys[i], choices[i]);
    }
    return getType();
}

 

 

2. 두 큐 합 같게 만들기

 greedy 문제. sum이 큰 queue에서 pop하고 sum이 작은 queue로 insert하는 연산을 조건이 만족할 때까지 반복하면 되는 문제. 이 조건은 쉽게 찾았는데 종료조건을 못 찾아서 답을 봤다. 종료 조건은 4n번 실행되었을 때인데, 그 이유는 종료하지 않는다면 cycle이 만들어 진다는 것이고, 한쪽 queue의 모든 element가 다른 queue로 갔다가 자신에게 돌아오려면

• q1에서 q2로 모든 element가 가야 함(n)
• q2에서 q1으로 모든 element가 가야 함(2n)
• q1에서 q2로 q2의 element가 가야 함(n)

이기 때문에 4n이다.

#include <string>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

int solution(vector<int> queue1, vector<int> queue2) {
    int n = queue1.size();
    
    ll q1sum = 0, q2sum = 0;
    queue<int> q1, q2;
    for(int i = 0; i<n; i++){
        q1.push(queue1[i]); q1sum += queue1[i];
        q2.push(queue2[i]); q2sum += queue2[i];
    }
    
    int answer = 0;
    for(int i = 0; i<4*n; i++, answer++){
        if(q1sum == q2sum) return answer;
        if(q1sum > q2sum){
            q1sum -= q1.front(); q2sum += q1.front();
            q2.push(q1.front()); q1.pop();
        }
        else{ // q1sum < q2sum
            q2sum -= q2.front(); q1sum += q2.front();
            q1.push(q2.front()); q2.pop();
        }
    }
    
    return -1;
}

 

시간복잡도

 각 연산은 O(1), 이 연산을 4n번 반복하기 때문에 O(n)

 

공간복잡도

 queue 2개만 쓰기 때문에 O(n)

 

 

3. 코딩 테스트 공부

 처음에는 주어진 수치가 작아서 BFS 문제일 거라 생각하고 풀었는데 시간 초과가 났다. 답을 확인하니 DP 문제라더라. 감이 딱 와서, 풀었는데 계속계속 틀려서 화가 너무 났다. 더 분발해야지..

 실수한 점은 다음과 같다.

• dp 배열을 dp[MAX][MAX]로 설정하고, 이 값을 넘어가는 값에 대해서 MAX index에 할당하게 했다.
  • 이 경우, max_alp가 MAX보다 작은 경우를 해결하지 못한다.
• max_alp, max_cop 값을 INT_MIN으로 초기화했다.
  • 이 경우, max_alp가 alp보다 작은 경우를 해결하지 못한다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <climits>

using namespace std;

// problem[i] : [alp_req, cop_req, alp_rwd, cop_rwd, cost]
int solution(int alp, int cop, vector<vector<int>> problems) {
    int max_alp = alp, max_cop = cop; // 오류 : INT_MIN으로 초기화하면 max_alp가 alp보다 작은 경우를 처리하지 못함
    for(vector<int>& problem : problems){
        max_alp = max(max_alp, problem[0]);
        max_cop = max(max_cop, problem[1]);
    }

    vector<vector<int>> dp(max_alp + 1, vector<int>(max_cop + 1, INT_MAX));   
    dp[alp][cop] = 0;
    
    for(int i = alp; i<=max_alp; i++){
        for(int j = cop; j<=max_cop; j++){
            if(i+1 <= max_alp) dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
            if(j+1 <= max_cop) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
            
            for(vector<int> &problem : problems){
                int alp_req = problem[0], cop_req = problem[1], alp_rwd = problem[2], cop_rwd = problem[3], cost = problem[4];
                if(alp_req <= i && cop_req <= j){
                    int nexti = i+alp_rwd > max_alp ? max_alp : i+alp_rwd; // 오류 : MAX값으로 잡아버리면 max_alp값이 정확하게 갱신 안됨
                    int nextj = j+cop_rwd > max_cop ? max_cop : j+cop_rwd;
                    dp[nexti][nextj] = min(dp[nexti][nextj], dp[i][j] + cost);
                }
            }
        }
    }
    
    return dp[max_alp][max_cop];
}

/*
DP였다고..? ;;
dp[i][j] : alp i, cop j를 채우기 위해 걸리는 최소 시간
dp[i][j]에서
    dp[i+1][j] = dp[i][j] + 1
    dp[i][j+1] = dp[i][j] + 1
    모든 문제에 대해, 풀 수 있는 문제의 증가량 봐주면 될듯
    
    */

 

시간복잡도

 max_alp(150), max_cop(150), problem(100)을 곱한 값이다. O(max_alp * max_cop * problem)

 

공간복잡도

 max_alp, max_cop를 곱한 값이다. 그만큼의 배열을 쓰기 때문.

 

 

4. 등산코스 정하기

 처음에 딱 봤을 땐 DFS 문제인 줄 알고 DFS로 풀었다. 근데 이렇게 풀면 일반 vertex 사이에서 계속 탐색을 왔다갔다 한다. 그렇다고 visit 배열을 쓰면 다른 gate vertex에서 탐색이 제대로 안된다.

 dijkstra로 풀어야 하는 문제였다. 다만 filp이 몇가지 필요했는데,

• gate - summit - gate로 path가 이루어진다. 그러나, gate - summit과 summit - gate를 똑같이 해버리면 뒷부분(summit -gate)를 탐색할 이유가 없다. 따라서 gate부터 summit까지 최소 weight를 찾아야 한다.
  • 따라서 gate에서는 outgoing edge만 (단, gate-gate는 버려야 한다),
  • summit에서는 incoming edge만 남겨야 한다.
• dijkstra는 dist[to] = max(dist[from] + weight)이지만, 여기서는 gate부터 summit까지 shortest path를 찾는 게 아니라 maximum weight를 찾는 것이기 때문에 dist[to] = max(dist[from], weight)로 해 주어야 했다.

 

 실수한 점은, dist 배열 초기값을 INT_MAX로 지정했는데 이러면 overflow가 난다. 또한 dijkstra의 갱신 로직에서 등호를 넣었는데 이러면 일반 vertex끼리 계속 왔다갔다 하기 때문에 >로 끊었어야 했다.

#include <string>
#include <vector>
#include <climits>
#include <set>
#include <queue>

using namespace std;

typedef long long ll;

struct Edge{
    int dest;
    int weight;
};

// weight가 작은 것이 top
struct cmp{
    bool operator() (const Edge&a, const Edge&b){
        if(a.weight == b.weight) return a.dest > b.dest;
        return a.weight > b.weight;
    }
};

bool isExists(int n, set<int>& s){
    if(s.find(n) == s.end()) return false;
    return true;
}
    
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    // init
    set<int> Gates, Summits; // 출입구, 산봉우리
    for(int i : gates) Gates.insert(i);
    for(int i : summits) Summits.insert(i);
    
    // flip : 갔다가 돌아오는 게 아니라, gate로부터 summit까지만 가면 됨.
    // 따라서 gate에서는 outgoing edge만, summit에서는 incoming edge만 남겨야 함.
    vector<vector<Edge>> Edges(n+1);
    for(vector<int>& path : paths){
        bool isPath0Gate = isExists(path[0], Gates), isPath1Gate = isExists(path[1], Gates);
        bool isPath0Summit = isExists(path[0], Summits), isPath1Summit = isExists(path[1], Summits);
        if(isPath0Gate && isPath1Gate){} // gate를 연결하는 edge
        else if(isPath0Summit && isPath1Summit){} // summit을 연결하는 edge
        else if(isPath0Gate || isPath1Summit){ // gate에서는 나가기만 해야 하고, summit으로는 들어오기만 해야함
            Edge e1; e1.dest = path[1]; e1.weight = path[2];
            Edges[path[0]].push_back(e1);    
        }
        else if(isPath1Gate || isPath0Summit){
            Edge e2; e2.dest = path[0]; e2.weight = path[2];
            Edges[path[1]].push_back(e2);    
        }
        else{
            Edge e1; e1.dest = path[1]; e1.weight = path[2];
            Edges[path[0]].push_back(e1);
            Edge e2; e2.dest = path[0]; e2.weight = path[2];
            Edges[path[1]].push_back(e2);
        }
    }
    
    // dijkstra init
    // 모든 gate를 시작점으로 dijkstra해볼 수 없음.
    // flip : 모든 gate에서 weight를 0으로 두고, pq에 해당 edge 넣으면 그 점에서 시작 가능
    priority_queue<Edge, vector<Edge>, cmp> pq;
    vector<int> dist(n+1, 987654321); // 실수 : INT_MAX로 하면 1만 더해도 overflow남. 적당한 수로 해야 함
    for(int v : gates){
        dist[v] = 0;
        Edge e; e.dest = v; e.weight = 0;
        pq.push(e);
    }
    
    // dijkstra
    while(!pq.empty()){
        int cur = pq.top().dest; pq.pop();
        
        for(Edge e : Edges[cur]){
            int next = e.dest, weight = e.weight;
            if(dist[next] > max(dist[cur], weight)){
                // 실수 1 : sum이 아니라 max로 해야 문제 조건에 맞음
                // 실수 2 : >=로 해버리면 무한루프 돌 수 있기 때문에 >로 해야 함
                dist[next] = max(dist[cur], weight);
                Edge nextE; nextE.dest = next; nextE.weight = dist[next];
                pq.push(nextE);
            }
        }
    }
    
    vector<int> answer = {-1, INT_MAX}; // v, intensity
    for(int v : Summits){
        if(dist[v] < answer[1]){
            answer[0] = v;
            answer[1] = dist[v];
        }
    }
    
    return answer;
}

 

시간복잡도

 O((V + E)logV)이다. pq의 시간복잡도가 O(logV)이며 모든 vertex를 거치며 탐색하기 때문에 (V+E)이다. 따라서 dijkstra 시간복잡도와 동일하다.

 

공간복잡도

 pq의 공간은 worst O(V), 각 vertex, edge array를 합치면 O(V + E)이다. 이만큼 쓴다.

 

 

후기

 찾아보니 4솔을 해야 합격한 것 같다.(3솔 + 정확성 2개 푼 사람이 떨어졌으니) 아직 많이 멀었음을 느낀다.

• 최대한 원큐에 solve를 찍을 수 있게 해야 한다... 디버깅에서 시간을 많이 쓰면 안 된다.
• 문제 접근을 잘못한 경우가 많았다. 특히 dp. 많이많이 보자...