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이다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int N, M;

// 오른쪽으로 90도 회전
vector<vector<int>> rotate(vector<vector<int>> &key){
    vector<vector<int>> rotated_key(M, vector<int>(M, 0));
    for(int i = 0; i<M; i++){
        for(int j = 0; j<M; j++){
            rotated_key[j][M-1-i] = key[i][j];
        }
    }
    return rotated_key;
}

// total 초기화 함수
// total 중에서 lock의 시작 위치는 (M-1, M-1)부터 (M+N-2, M+N-2)까지임.
void initTotal(vector<vector<int>> &total, vector<vector<int>> &lock){
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            total[i+M-1][j+M-1] = lock[i][j];
        }
    }
}

// lock이 가득 찼는지 확인하는 함수
// total 중에서 lock의 시작 위치는 (M-1, M-1)부터 (M+N-2, M+N-2)까지임.
bool isLockFull(vector<vector<int>> &total){
    int end = M+N-2;
    for(int i = M-1; i<=end; i++){
        for(int j = M-1; j<=end; j++){
            if(total[i][j] != 1) return false;
        }
    }
    return true;
}

// total에서 key의 시작 위치가 (r, c)일 때 key를 더하고 확인하는 함수
bool isMatch(vector<vector<int>> total, vector<vector<int>>& key, int r, int c){
    for(int i = 0; i<M; i++){
        for(int j = 0; j<M; j++){
            total[i+r][j+c] += key[i][j];
        }
    }
    return isLockFull(total);
}


bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    M = key.size(); N = lock.size();
    
    // 회전된 key들 생성
    vector<vector<vector<int>>> keys;
    keys.push_back(key);
    for(int i = 0; i<3; i++){
        key = rotate(key);
        keys.push_back(key);
    }
    
    // size 충분한 한 배열 생성. 가운데에 lock이 들어가고, key들은 위치를 옮겨가며 가득 차는지 볼 것임.
    int total_size = N+2*M-2;
    vector<vector<int>> total(total_size, vector<int>(total_size));
    initTotal(total, lock);
    
    // key의 시작 위치는 (0, 0부터) (M+N-1, M+N-1)까지 가능.
    int end = M+N-1;
    for(int i = 0; i<end; i++){
        for(int j = 0; j<end; j++){
            for(int k = 0; k<4; k++){
                if(isMatch(total, keys[k], i, j)) return true;
            }
        }
    }
    return false;
}
/*
가운데 lock 두고
상하좌우에 key만큼 size 추가함
그러면 N + 2M짜리. 
*/

 

시간복잡도

 키가 열쇠에 맞는지 확인하는 로직이 O(N$^2$), 키를 옮길 때 O((M+N)$^2$)가 걸린다. O((M+N)$^2$)이다.

 

공간복잡도

 추가 공간은 O((M+N)$^2$)만큼 쓴다.

 

후기

 53분... 너무 오래 걸렸다. 일단 실수한 건, 좌표를 확실하게 생각하지 않고 시작한 것. 이게 열쇠가 들어갈 공간을 M-1 by M-1로 겹쳐 두니 계산이 조금 힘들었다.

 또, 다른 실수한 것은 lock이 가득 찼는지 확인하는 함수에서 != 1로 해야 하는데 != 0으로 했던 것도 실수.

 

 이런 문제를 35분 내에 풀어야 하는데.. 구현 문제 속도는 언제쯤 빨라질까. 그래도 모듈화를 잘 해놨어서 실수를 빨리 잡긴 했다.

 

 

 

Programmers GPS

 문제를 처음 딱 보면 brute-force인 것 같다. bellman ford부터 접근할 생각을 하는데, 그러면 안 된다.

 sweeping 느낌으로 DP를 써야 한다. 점화식은 다음과 같다.

 

 dp[t][l] : 시간 t에서 위치가 l일 때 최소로 고치는 개수라고 두자.

 그러면 점화식은, 모든 dp[t-1][l의 neighbor]에 대해 gps_log[t] == l의 neighbor이면 +0, 아니면 +1. 그 중에서 최소값을 뽑으면 된다.

 

 점화식 자체는 간단한데, 이걸 생각하는 과정이... 모든 DP 문제가 그렇듯 점화식을 세우는 게 어렵다.

#include <vector>

using namespace std;

/*
거점 개수가 200개
도로 개수는 10000개
BF같은데
dp[t][l] : 시간 t에서 위치가 l일 때
모든 dp[t-1][l의 neighbor]에 대해서 (이전단계)
gps_log[t] == l이면 +1
아니면 +0

*/

int INF = 1e9;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    vector<vector<int>> edges(n+1);
    for(vector<int> e : edge_list){
        edges[e[0]].push_back(e[1]);
        edges[e[1]].push_back(e[0]);
    }
    for(int i = 1; i<=n; i++){
        edges[i].push_back(i);
    }
    
    vector<vector<int>> dp(k, vector<int>(n+1, INF));
    dp[0][gps_log[0]] = 0;
    for(int t = 1; t<k; t++){
        for(int l = 1; l<=n; l++){
            int isLonT = gps_log[t] == l ? 0 : 1;
            for(int neighbor : edges[l]){
                dp[t][l] = min(dp[t-1][neighbor] + isLonT, dp[t][l]);
            }
        }
    }
    
    if(dp[k-1][gps_log[k-1]] >= INF) return -1;
    return dp[k-1][gps_log[k-1]];
}

 

시간복잡도

 모든 DP를 채우는 데 O(k$^2$n) 만큼의 시간이 든다.

 

공간복잡도

 추가 공간은 O(kn)과 O(n)만큼 쓰니까 O(kn).

 

후기

 어떻게 이런 문제가 lv 3에 있는 건지 모르겠다. DP인 걸 알 수 있는 단서가 너무나도 적은데..

 

 

 

Programmers 다리를 지나는 트럭, 20분

 문제에서 주는 대로 구현만 하면 되는 문제. queue를 사용하면 굉장히 편?리하게 풀 수 있다.

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

using namespace std;

typedef pair<int, int> pii;
int solution(int len, int weight, vector<int> truck_weights) {
    int cur_sum = 0; // 현재 다리 위에 있는 트럭 무게
    queue<pii> curs; //.first : 무게, .second : 들어온 시간 t
    
    // 대기열
    queue<int> waits;
    for(int wait : truck_weights) waits.push(wait);
    
    int t = 1;
    while(1){
        // 다리에서 나가는 경우
        if(!curs.empty() && t >= curs.front().second + len){
            cur_sum -= curs.front().first;
            curs.pop();
        }
        
        // 다리에 진입하는 경우
        if(curs.size() < len && !waits.empty() && cur_sum + waits.front() <= weight){
            curs.push({waits.front(), t});
            cur_sum += waits.front();
            waits.pop();
        }
        
        // 종료조건
        if(waits.size() == 0){
            return t + len;
        }
        
        t++;
    }
    return t;
}

 

시간복잡도

 while문은 worst case 1억 정도로 돈다. 만약 최적화가 필요하면, 다리에 진입하는 트럭이 없는 경우에 curs.front()를 내보내는 시간으로 설정하면 된다.

 

후기

 이건 왜이렇게 빨리 풀렸지?

 

 

 

Programmers 짝지어 제거하기, 35분

 첫 번째 접근은 s.substr()을 이용해서 겹치는 부분을 삭제하고, index를 앞으로 당기는 방법이었다. 시간복잡도가 O(n)일 것이라 생각했으나... substr() 함수는 문자열을 자르고 복사하기 때문에 O(n)만큼의 시간이 걸렸다. 때문에 다른 방법을 택해야 했다.

 

 stack을 사용하면 아주 쉽게 풀린다. 설명할 필요도 없고, 코드 보면 바로 이해가 될 것이다.

#include <iostream>
#include <iostream>
#include <stack>
#include<string>
using namespace std;

int solution(string s)
{
    stack<char> stk;
    for(char c : s){
        if(!stk.empty() && stk.top() == c){
            stk.pop();
        }
        else stk.push(c);
    }
    
    return stk.empty();
}

 

시간복잡도

 s를 순회하므로 O(n)

 

공간복잡도

 stack size는 worst case O(n)

 

후기

 안 되는 풀이를 너무 오래 붙들고 있었다.

 

 

 

Leetcode 118, Pascal's Triancle, 10분

 그냥 배열 쓸 줄 알면 풀리는 문제.

// Runtime 0 ms Beats 100%
// Memory 6.9 MB Beats 20.86%

class Solution {
public:
    vector<vector<int>> generate(int n) {
        vector<vector<int>> answer;
        answer.push_back({1});

        for(int l = 1; l<n; l++){
            vector<int> layer(l+1);
            layer[0] = layer[l] = 1;
            for(int i = 1; i<l; i++){
                layer[i] = answer[l-1][i] + answer[l-1][i-1];
            }
            answer.push_back(layer);
        }

        return answer;
    }
};

 

시간복잡도

 2차원 배열 채우는 거니 O(n^$2$).