23.09.09. 풀었던 문제들

Programmers PCCP 모의고사 #1 외톨이 알파벳, 5분

 프로그래머스 짝지어 제거하기를 풀어봤다면 바로 이어져 나오는 중복 char를 쉽게 줄일 수 있다. stack을 쓰든, string의 뒤에 중복을 빼고 붙여넣든. 이 방법을 사용하면 중복을 제거할 수 있고, 그러면 map으로 count만 하면 된다. 간단한 손풀기 문제.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;

string solution(string str) {
    stack<char> stk;
    for(char c : str){
        if(!stk.empty() && stk.top() == c) continue;
        stk.push(c);
    }
    
    map<char, int> m;
    while(!stk.empty()){
        m[stk.top()]++;
        stk.pop();
    }
    
    string answer = "";
    for(auto &[key, value] : m) {
        if(value > 1) answer += key;
    }
    sort(answer.begin(), answer.end(), less<char>());
    
    return answer == "" ? "N" : answer;
}

 

시간복잡도

 string 중복 제거에 O(n), map에 넣는 데 O(n)이 걸린다.

 

 

 

Programmers PCCP 모의고사 #1 체육대회, 18분

 처음에는 이걸 어떻게 시간 내에 풀지..? 하고 나중에 풀었었는데. 그냥 단순한 순열 문제다! 순열은 뭐.. 예전에 포스팅했었고 별로 어렵지 않게 DFS로 코드를 짤 수 있었다.

 문제 조건은 10이므로 10!, 약 3백만으로 넉넉하게 풀 수 있다.

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

using namespace std;

// stat[i][j] : i번째 학생이 종목 j의 능력치
// vertex가 
/*
DP vs graph vs BF
앞 단에서 최대값을 택한다고, 전체가 최대가 되는 게 아님. -> BF 써야 하긴 하는데.
worst 10^10
*/

// 일단 DFS
int answer = -1e9;
vector<vector<int>> stats;
vector<bool> isSelected; // isSelected[i] : i번째 학생을 골랐는지 여부
int student_num, event_num;
void DFS(int cur_d, int max_d, int result){
    if(cur_d == max_d){
        answer = max(answer, result);
        return;
    }
    
    for(int i = 0; i<student_num; i++){
        if(!isSelected[i]){
            isSelected[i] = true;
            DFS(cur_d + 1, max_d, result + stats[i][cur_d]);
            isSelected[i] = false;
        }
    }
}


int solution(vector<vector<int>> input) {
    stats = input;
    student_num = input.size();
    event_num = input[0].size();
    isSelected.resize(student_num);
    fill(isSelected.begin(), isSelected.end(), false);
    
    DFS(0, event_num, 0);
    
    return answer;
}

 

시간복잡도

 10!의 순열이므로 O(10!), 약 3백만

 

후기

 일단은 naive하게 되는 대로 DFS로 풀었는데, 바로 맞아서 다행이다. 역시 아무것도 안 하는 것보다는 BF로 부분점수라도 받는 마인드가 맞다.

 

 

 

Programmers PCCP 모의고사 #1 유전법칙, 31분

 규칙 찾기 문제. 각 그룹은 무조건 1개의 parent와 4개의 child로 이루어져 있으므로 몇 번째 generation의 몇 번째 index인지만 찾으면 된다.

 사실 진법 변환이랑 같은 류의 로직. 언제 끝내고 어떻게 처리할지만 잘 처리해 주면 된다. 나는 map에 vector를 넣어서 해결했다!

#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

// 4^15는 1억이 넘으므로 전부 다 계산하고 뽑는 것은 안 된다. 적당히 찾아야 한다.

// record[i] : i+1번째 generation에서 어떤 index를 가지는지
// ex) record[2] == 2 : 3번째 generation에서 index가 2
// 2번째 generation까지 계산함. 1번째 generation은 있기 때문.
vector<int> getRecords(int n, int p){
    vector<int> records; 
    records.push_back((p-1) % 4);
    while(n > 2){
        int before = ceil(((double)p)/4);
        records.push_back((before-1) % 4);
        
        p = before;
        n--;
    }
    reverse(records.begin(), records.end());
    return records;
}

// n : 세대, p : 개체
// 윗세대가 어떤 것인지 찾아야 한다.
string process(int n, int p){
    if(n == 1) return "Rr";
    
    map<string, vector<string>> m;
    m["RR"] = {"RR", "RR", "RR", "RR"};
    m["Rr"] = {"RR", "Rr", "Rr", "rr"};
    m["rr"] = {"rr", "rr", "rr", "rr"};
    
    vector<int> records = getRecords(n, p);
    
    string cur = "Rr";
    for(int record : records){
        //cout<<"cur : "<<cur<<", record : "<<record<<endl;
        cur = m[cur][record];
        
    }
    //cout<<endl;
    
    return cur;
}

vector<string> solution(vector<vector<int>> queries) {
    vector<string> answer;
    for(vector<int> query : queries){
        answer.push_back(process(query[0], query[1]));
    }
    return answer;
}

 

시간복잡도

 n이 15이므로, getRecords() 함수의 while loop는 15번 돈다. 그러니까 O(n). map에 접근하는 것은 map size가 3이므로 사실상 O(1)로 치고. 그러면 O(n)이다.

 

 

 

Programmers PCCP 모의고사 #1 운영체제, 38분

 많이 봤던 simulation 문제. pq를 써서 주어진 대로 풀면 된다.

 실수했던 점은, future와 wait 2개의 queue에 다른 우선순위를 적용시켜줘야 했는데, 같은 우선순위를 썼었다. future의 경우에는 빨리 오는 게 먼저 와야 하고, wait queue의 경우에는 점수가 낮은 것이 먼저 와야 했다.

 이것 말고는 뭐.. 딱히 실수한 것이 없었고, 잘 구현했던 것 같다. 디버깅도 빨리 해서 다행이다.

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

using namespace std;

typedef long long ll;

struct info{
    int point;
    int income_time;
    int running_time;
};

// 정렬 기준 : 1. 빨리 오는 것 2. 우선순위 높은 것
struct futurecmp{
    bool operator()(info &a, info &b){
        if(a.income_time == b.income_time) return a.point > b.point; // 우선순위 숫자 작은 게 top에
        return a.income_time > b.income_time; // income time 빠른 게 top에
    }
};

// 정렬 기준 : 1. 우선순위 높은 것 2. 빨리 오는 것 
struct waitcmp{
    bool operator()(info &a, info &b){
        if(a.point == b.point) return a.income_time > b.income_time; // income time 빠른 게 top에
        return a.point > b.point; // 우선순위 숫자 작은 게 top에
    }
};

// 초기화 : 시작 시간이 t보다 작은 것들을 waits에 넣음
void pushIntoWaitsLessThanT(int t, priority_queue<info, vector<info>, waitcmp> &waits, priority_queue<info, vector<info>, futurecmp> &future){
    while(1){
        if(future.empty()) break;
        if(future.top().income_time > t) break;
        if(future.top().income_time <= t){
            waits.push(future.top());
            future.pop();
        }
    }
}

vector<long long> solution(vector<vector<int>> program) {
    priority_queue<info, vector<info>, waitcmp> waits; // 실행 대기 중인 thread queue
    priority_queue<info, vector<info>, futurecmp> future; // 미래에 thread queue
    for(vector<int> p : program){
        info i;
        i.point = p[0];
        i.income_time = p[1]; 
        i.running_time = p[2];
        future.push(i);
    }
    
    // 초기화
    int time = 0;
    pushIntoWaitsLessThanT(time, waits, future);
    cout<<endl;
    
    // answer[0] : 모든 프로그램 종료 시간, answer[i] : 점수가 i인 프로그램 대기시간 합
    vector<long long> answer(11, 0);
    while(1){
        if(waits.empty()){
            // 종료조건
            if(future.empty()) break;
            
            // future가 남아있으면 그것 넣음
            waits.push(future.top()); 
            time = future.top().income_time;
            future.pop();
        }
        
        // waits 중 제일 높은 것 실행 중으로 변경
        info cur = waits.top(); 
        waits.pop();
        // cout<<"현재 시간 : "<<time<<endl;
        // cout<<"현재 실행 중 : "<<cur.point<<", "<<cur.income_time<<", "<<cur.running_time<<endl;
        
        // 해당 thread의 대기시간 추가
        int wait_time = time - cur.income_time;
        answer[cur.point] += wait_time;
        // cout<<"대기시간 : "<<wait_time<<endl;
        
        time += cur.running_time;
        // cout<<"끝난 시간 : "<<time<<endl;
        pushIntoWaitsLessThanT(time, waits, future);
        
        
        // cout<<endl;
    }
    answer[0] = time;
    
    return answer;
}

 

시간복잡도

 n이 10만이고, pq의 각 연산이 O(logn)이므로 O(nlogn)에 얼추 풀린다.

 

 

후기

 디버깅이 빨리 끝나서 다행이다. 구조화를 잘 해놔서..

 

 

 

Programmers PCCP 모의고사 #2 실습용 로봇, 10분

 손 푸는 문제. 2D 좌표에서 이동하는 방법만 알면 된다. 실수했던 건 direction-- 이후 modular 연산을 한 것. C++에서는 음수의 modular 연산을 하면 a = bq + r에서 r = a - bq로 연산한다. 이것 때문에 한 3분? 날린 듯. 그래도 빨리 찾아서 다행이다. 디버깅도 안 찍었고.

#include <string>
#include <vector>

using namespace std;

int direction = 0; // dx, dy의 index. R이면 +1, L이면 -1
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

vector<int> position = {0, 0};

void rotate(char command){
    if(command == 'R'){
        direction++;
        if(direction == 4) direction = 0;
    }
    else if(command == 'L'){
        direction--;
        if(direction < 0) direction = 3;
    }
}

void move(char command){
    int d = direction;
    if(command == 'B'){
        d += 2;
        d %= 4;
    } 
    position[0] += dx[d];
    position[1] += dy[d];
}

vector<int> solution(string command) {
    for(char c : command){
        if(c == 'R' || c == 'L'){
            rotate(c);
        }
        else if(c == 'G' || c == 'B'){
            move(c);
        }
    }
    return position;
}

 

 

 

Programmers PCCP 모의고사 #2 신입사원 교육, 5분

 문제를 딱 보면 greedy같다는 느낌이 든다. 증명해볼까?

 점수가 a, b, c, ... 순서로 오름차순 정렬되어 있다고 할 때,

• a와 b를 합치는 경우 a+b, a+b, c, ...가 된다.
• a와 c를 합치는 경우 a+c, a+c, b, ...가 된다.
• 이 둘의 차이는 c-b인데, 이는 무조건 양수이다. 따라서 최소인 것을 고르지 않으면 sum이 최소가 되지 않는다는 것을 proof by contradiction으로 보일 수 있다.

 

 그러면 min값 2개를 뽑으면 되는데, 이건 pq를 쓰면 쉽다.

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

using namespace std;

int solution(vector<int> ability, int n) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int a : ability) pq.push(a);
    
    while(n--){
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();
        pq.push(first + second);
        pq.push(first + second);
    }
    
    int answer = 0;
    while(!pq.empty()){
        answer += pq.top();
        pq.pop();
    }
    return answer;
}

 

시간복잡도

 ability는 백만, n은 1만. 한 번의 연산에 O(log(1백만))이고 이 연산을 O(n)번 하므로 O(1만 * log(1백만))이다. 여기서 log(1백만)이 20 정도로, O(20만)으로 처리할 수 있다.

 

 

 

Programmers PCCP 모의고사 #2 실습용 로봇, 18분 풀고 이후 40분, 총 58분

 처음에는 간단한 시뮬레이션 문제인 줄 알고 풀었는데.. 생각보다 까다로운 문제였다.

 중요한 건 예외가 하나 있었다는 건데, 만들고 나가는 사람 + 들어오는 사람이 있으면 무조건 만들고 나가는 사람이 먼저 나간다는 것이다. 때문에 이에 대한 예외 연산을 빼놓지 않고 풀었어야 했다. 다행인 건 예제에 이 edge case를 저격하는 예외가 있었다는 것. 덕분에 쉽게 풀었다.

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

using namespace std;

int solution(vector<int> menu, vector<int> order, int k) {
    int total_num = order.size();
    
    queue<int> waits; // 대기자 목록. 들어오는 것은 index
    int future_idx = 0; // 제일 근미래에 올 사람의 index
    int time = 0;
    
    int answer = -1;
    
    while(1){
        // 종료조건
        if(time >= total_num * k) break;
        
        // time보다 빨리 와서 그동안 줄을 선 손님들 waitQ에 추가
        while(1){
            if(future_idx < total_num && future_idx * k <= time){
                waits.push(future_idx);
                future_idx++;
            }
            else break;
        }
        
        // 만듬
        if(!waits.empty()){
            time += menu[order[waits.front()]];
        }
        
        // 만들 동안 와서 그동안 줄을 선 손님들 waitQ에 추가
        while(1){
            if(future_idx < total_num && future_idx * k <= time){
                waits.push(future_idx);
                future_idx++;
            }
            else break;
        }
        
        // 대기열 계산. 단, 만들고 나간 시간 == 들어온 시간이면 1을 빼 주어야 함.
        int isDuplicated = (time%k == 0 ? 1 : 0);
        answer = max(answer, (int)waits.size() - isDuplicated);
        
        // 만들었다면, 빼고, 그렇지 않다면 타임트립.
        if(!waits.empty()) waits.pop();
        else{
            time = future_idx * k;
        }
    }
    
    return answer;
}

 

시간복잡도

 menu length는 100, order length는 1만으로, time을 1씩 늘려가면서 계산해도 1백만 정도로 시간은 여유롭다.

 

후기

 이 문제는 진짜 아슬아슬했다.

 

 

 

Programmers PCCP 모의고사 #2 보물 지도, 50분

 Acmicpc 벽 부수고 이동하기를 풀어봤다면 매우 쉽게 접근할 수 있는 문제. 아이템의 사용 여부도 visited 배열에 넣음으로써 쉽게 풀 수 있다.

 단.. 이 문제의 경우 (x, y) 좌표로 주어지는데, 이를 (r, c) 좌표로 변환해야 했다. 이것 때문에 시간을 많이 잡아먹었다.

 처음에 hole 위치를 초기화 할 때 seg fault가 나는 것을 보고 엥? 싶었는데.. 이런... 역시 문제를 잘 읽어야 한다. 항상 인지하고 문제를 읽지만 이런 "당연히 이러겠지" 싶은 것에서 항상 뒤통수를 맞는 것 같다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int INF = 1e9;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

struct info{
    int r;
    int c;
    int used;
    int dist;
};

int solution(int n, int m, vector<vector<int>> holes) {
    vector<vector<int>> board(m, vector<int>(n, 0)); // 0 : 빈칸, 1 : 함정
    // (m-1, 0)부터 (0, n-1)까지 가야 함.
    for(vector<int> hole : holes){
        int r = m - hole[1];
        int c = hole[0]-1;
        // cout<<r<<", "<<c<<endl;
        board[r][c] = 1;
    }
    
    vector<vector<vector<int>>> visited(m, vector<vector<int>>(n, vector<int>(2, 0)));
    // visited[r][c][u] : (r, c) 위치를 방문했는지 여부. u가 1이면 신발 쓴 것이고, 0 신발 안 쓴 것.
    queue<info> q;
    info i; i.r = m-1; i.c = 0; i.used=0; i.dist=0;
    q.push(i);
    visited[m-1][0][0] = true;
    int answer = INF;
    while(!q.empty()){
        info cur = q.front(); q.pop();
        // cout<<"현재위치 : "<<cur.r<<", "<<cur.c<<", 사용여부 : "<<cur.used<<", dist : "<<cur.dist<<endl;
        
        // 종료조건
        if(cur.r == 0 && cur.c == n-1) answer = min(answer, cur.dist);
        
        // 안 쓰고 넘어가는 경우
        for(int d = 0; d<4; d++){
            int nr = cur.r + dr[d];
            int nc = cur.c + dc[d];
            if(0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] == 0 && !visited[nr][nc][cur.used]){
                // 사용 여부는 이전 상태 유지
                visited[nr][nc][cur.used] = true;
                info next; next.r = nr; next.c = nc; next.used = cur.used; next.dist = cur.dist+1;
                q.push(next);
            }
        }
        
        // 쓰고 넘어가는 경우
        if(cur.used == 1) continue;
        for(int d = 0; d<4; d++){
            int nr = cur.r + 2*dr[d];
            int nc = cur.c + 2*dc[d];
            if(0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] == 0 && !visited[nr][nc][1]){
                visited[nr][nc][1] = true;
                info next; next.r = nr; next.c = nc; next.used = 1; next.dist = cur.dist+1;
                q.push(next);
            }
        }

    }

    return answer == INF ? -1 : answer;
}

 

시간복잡도

 m, n이 각각 1000 총 vertex size는 mn이고, O(1백만)이고,

 각 vertex당 아이템을 사용하지 않을 때 4개 방향 + 아이템을 사용할 때 4개 방향으로 8개의 edge가 있다.

 BFS의 시간복잡도는 O(V+E)이므로 O(9mn), O(mn)이다. 

 

후기

 왜 문제를 (x, y)로 냈을 까... 그냥 푸는 사람들을 괴롭히기 위해서가 아닐까?

 

 

 

Leetcode 377. Combination Sum IV, 30분

첫 접근 : duplicated permutation

 일단은 문제를 딱 보고... [순서를 신경쓰는 + 합이 k가 되게 만드는 조합]이라길래 중복순열 딱 생각나서 중복순열로 풀었따. 그러나 문제의 input은 nums.size()가 200이기 때문에... 절대 풀 수 없다. 중복순열의 시간복잡도는 O(n$^n$)이니까. DFS 스택이 너무 많이 터져서 MLE가 떴다.

class Solution {
public:
    vector<vector<int>> answer;
    vector<int> nums;
    int target;
    void duplicatePermutation(int cur_d, vector<int> result, int sum){
        if(sum == target){
            answer.push_back(result);
            return;
        }

        for(int i = 0; i<nums.size(); i++){
            if(nums[i] + sum > target) continue;

            result.push_back(nums[i]);
            duplicatePermutation(cur_d + 1, result, sum + nums[i]);
            result.pop_back();
        }
    }
    int combinationSum4(vector<int>& i_nums, int i_target) {
        nums = i_nums;
        target = i_target;
        sort(nums.begin(), nums.end(), less<int>());

        duplicatePermutation(0, {}, 0);

        return answer.size();
    }
};

/*
중복순열 문제 같은데. + 합이 k가 되는...
*/

 

 

두 번째 접근 : DP

 다른 방법이 필요하다... DFS의 tree를 보면 sum이 같을 때, 같은 연산을 반복하는 중복이 꽤나 발생하는 것을 알 수 있다. 이를 줄이기 위해서는? memoization이다. memozation? DP다!

 앞선 관측에서 중복되는 부분은 [남은 값]으로 판별했다. 그러면, dp[i]를, [남은 값이 i일 때 만들 수 있는 경우의 수]로 세우면 될 것이다! 이것만 만들면 일사천리다.

 점화식은 다음과 같으며, 이를 코드로 나타내면 된다. dp[0] = 1이니까 top-down이 쉬울 것 같다!

• dp[0] = 1. (초기값)
• dp[i] = 모든 n에 대해 dp[i-n]의 합

// Runtime 3 ms Beats 50.37%
// Memory 6.7 MB Beats 20.91%

class Solution {
public:
    vector<int> nums;
    int INF = -1;
    vector<int> dp;

    int recurse(int remain){
        if(dp[remain] != INF) return dp[remain];

        int num_cases = 0;
        for(int n : nums){
            if(n > remain) break;
            num_cases += recurse(remain - n);
        }
        dp[remain] = num_cases;
        return dp[remain];
    }
    int combinationSum4(vector<int>& i_nums, int target) {
        nums = i_nums;
        dp.resize(target + 1, INF);
        dp[0] = 1;
        sort(nums.begin(), nums.end(), less<int>());

        return recurse(target);
    }
};

 

시간복잡도

 nums.size()가 n, target이 t일 때, recurse()를 수행하기 위해서 O(n)이 걸리고, 모든 dp 배열을 채우기 위해서 O(t)가 필요하므로 O(nt)이다.

 

후기

 dp 으악