22.08.15. 풀었던 문제들 *** vector erase, remove

프로그래머스 코딩테스트 실전 대비 모의고사 3회

1번

 주어진 대로 반복문을 써서 풀면 되는 문제.

int solution(int give, int take, int cur) {
    int answer = 0;
 
    while(cur >= give){ // 현재 가지고 있는 게 주는 것보다 많으면 줄 수 이씅ㅁ
        int ret = (cur / give) * take; // 돌려받는 것
        answer += ret;
        cur = cur - ((cur / give) * give) + ret; // 현재 개수 = 현재 개수 - 준 것 + 돌려받은 것
    }
 
    return answer;
}

 

2번

 뒤에서 4개가 주어진 조건을 만족한다면, 그것을 빼고 추가하면 되는 문제. list를 쓸까 vector를 쓸까 고민하다가 결국 더 빠른 vector를 선택했다. vector의 erase, remove의 차이에 대해 알아두자.

int solution(vector<int> ingredients) {
    int answer = 0;
 
    vector<int> cur;
    for(int i = 0, cidx = 0; i<ingredients.size(); i++){
        cur.push_back(ingredients[i]);
        int csize = cur.size();
        if(csize >= 4){
            if(cur[csize-1] == 1 && cur[csize-2] == 3 && cur[csize-3] == 2 && cur[csize-4] == 1){
                cur.erase(cur.begin() + csize - 4, cur.end());
                answer++;
            }
        }
    }
 
    return answer;
}

 

3번

 '경계 지역'에 근무를 서는 최솟값을 알아내면 되는 문제. 문제 자체는 [1 <= (i % cycle_time) <= guard[2]]라는 규칙이 있어서 쉬운데, 모든 경계 지역에 대해 이 값을 알아내야 하면 시간초과가 날 것 같았는데, 생각보다 테스트 케이스가 빈약했던 문제. 

bool cmp(vector<int>& a, vector<int>& b){
    if(a[0] == b[0]){
        if(a[1] == b[1]){
            if(a[2] == b[2]){
                return a[3] < b[3];
            }
            return a[2] < b[2];
        }
        return a[1] < b[1];
    }
    return a[0] < b[0];
}
 
int solution(int distance, vector<vector<int>> scope, vector<vector<int>> times) {
    vector<vector<int>> guards(scope.size());
    // [i][0] : 경계 시작 지점, [i][1] : 경계 끝 지점
    // [i][2] : 근무 시간, [i][3] : 휴식 시간
    for(int i = 0; i<scope.size(); i++){
        if(scope[i][0] > scope[i][1]){
            guards[i].push_back(scope[i][1]);
            guards[i].push_back(scope[i][0]);
        }
        else{
            guards[i].push_back(scope[i][0]);
            guards[i].push_back(scope[i][1]);
        }
        guards[i].push_back(times[i][0]);
        guards[i].push_back(times[i][1]);
    }
    sort(guards.begin(), guards.end(), cmp);
 
    int answer = distance;
    for(vector<int>& guard : guards){
        int cycle_time = guard[2] + guard[3];
        // 감시하는 구간에 근무시간이라면 break
        // 어떤 i가 근무 시간에 있는 건...
        // 1 <= (i % cycle_time) <= guard[2]
        // 이면 근무 시간이라는 것을 판별할 수 있음
        for(int i = guard[0]; i<=guard[1]; i++){
            int remainder = i%cycle_time;
            if(1 <= remainder &&  remainder <= guard[2]){
                answer = min(answer, i);
            }
        }
    }
    
    return answer;
}

 

4번

 꽤나 재밌었던 문제. DFS의 특성을 이용해서 [현재 칸을 색칠하는 경우, 그렇지 않은 경우]에 대해 최소 색칠 횟수를 leaf에서부터 가지고 올라와야 한다.

 만약 parent를 색칠했다면 child는 색칠해도 되고, 색칠하지 않아도 되므로 parent.first(색칠한 경우) += min(child를 색칠한 경우, child를 색칠하지 않은 경우)이고, parent를 색칠하지 않았다면 child는 색칠해야 하므로 parent.second(색칠하지 않은 경우) += child를 색칠한 경우로 문제를 풀면 된다.

typedef pair<int, int> pii;
int N;
vector<int> visited;
vector<vector<int>> edges;
 
// .first : cur을 색 칠한 경우 최소 색칠 횟수, .second : cur을 색칠하지 않은 경우 최소 색칠 횟수
pii dfs(int cur){
    visited[cur] = true;
 
    pii result = {1, 0}; // .first : cur을 색칠한 경우 
    for(int adj : edges[cur]){
        if(!visited[adj]){
            pii child_result = dfs(adj);
            result.first += min(child_result.first, child_result.second);
            // cur을 색칠했다면 child는 색칠해도 되고, 안 해도 됨
            result.second += child_result.first;
            // cur을 색칠하지 않았다면 child을 색칠되어 있어야 함
        }
    }
    return result; // child가 없다면 {1, 0}을 리턴.
}
 
int solution(int n, vector<vector<int>> lighthouse) {
    N = n+1;
    visited.resize(N);
    fill(visited.begin(), visited.end(), false);
    edges.resize(N);
    for(vector<int>& vi : lighthouse){
        edges[vi[0]].push_back(vi[1]);
        edges[vi[1]].push_back(vi[0]);
    }
 
    pii answer = dfs(1);
 
    return min(answer.first, answer.second);
}