[프로그래머스 LV.4] 1,2,3 떨어트리기 (C++) - 2023 KAKAO BLIND RECRUITMENT

1. 문제

LV 4.1,2,3 떨어트리기 - 2023 KAKAO BLIND RECRUITMENT

 

2. 문제 풀이

제 생각에 이 문제는, 답이 될 수 없는 경우를 적절히 체크하는 것으로 완전탐색/시뮬레이션이 가능함을 관찰하는 게 핵심인 문제였습니다.

먼저 답이 될 수 없는 경우에 대해 생각해 봅시다.

어떤 노드 x+1에 쌓인 숫자의 합$(= target[x])$이 아닌, 노드 x에 쌓인 숫자의 개수를 $stacked[x]$라고 합시다.

(어떤 노드 'x+1'인 이유는, 노드 번호는 1부터 시작하고 $target$의 index는 0부터 시작해서 그렇습니다.)

숫자의 크기가 1~3 사이이므로, 모든 x가 $stacked[x]<=target[x]<=3*stacked[x]$를 만족할 때 답이 될 수 있습니다.

(이 경우를 '충분히 쌓였다'라고 표현하겠습니다.)

그렇다면 우리는 모든 x에 대해, $3*stacked[x]>=target[x]$ 이 될 때까지 시뮬레이션을 계속해야만 합니다.

이 시뮬레이션은 무한히 계속될까요? 그렇지 않습니다.

우리는 모든 x에 대해 $stacked[x]<=target[x]$ 라는 조건을 만족해야 하므로,

단 하나라도 $stacked[x]>target[x]$인 경우가 발생한다면 답이 될 수 없습니다. 따라서 즉시 {-1} 을 리턴하면 됩니다.

(이 경우를 '과하게 쌓였다'라고 표현하겠습니다.)

 $target$값은 최대 $(100 = val)$밖에 안되고, 노드수 $= edges+1 <= 101 = n$ 이므로,

비둘기집 원리에 의해, $val*n+1$번의 시뮬레이션을 거치면 적어도 하나의 노드는 과하게 쌓이게 됩니다.

한 번의 시뮬레이션 과정에서, 방문하는 노드는 최대 $n$개 이므로,

시간복잡도는 $O(n^2*val)$ 입니다. ($n$ = 노드수, $val = target$의 최댓값)

 

이제 문제에서 설명한 그대로 구현하고, $stacked$ 배열을 이용해서 적당한 크기로 숫자를 골라주면 됩니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
 
int drop(vector<vector<int>> &tree,vector<int> &road){//x번 노드가 현재 road[x]번째 자식노드를 가리키고 있다. 
    int node=1;// [게임의 규칙] 1.
    while(!tree[node].empty()){// [게임의 규칙] 2.
        int nx=tree[node][road[node]];
        road[node]=(road[node]+1)%tree[node].size();// [게임의 규칙] 3.
        node=nx;
    }
    return node;
}
 
vector<int> solution(vector<vector<int>> edges, vector<int> target) {
 
    vector<vector<int>> tree(edges.size()+2);
    for(auto e:edges) tree[e[0]].push_back(e[1]);
    //[게임의 규칙] 3. 과, 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정한다는 조건을 위해 정렬한다.
    for(int i=0;i<tree.size();i++)
        sort(tree[i].begin(),tree[i].end());
 
    vector<int> road(tree.size(),0),stacked(tree.size(),0),simulation;
    vector<bool> enough(tree.size(),0);
 
    int cnt=0;
    for(int i=0;i<target.size();i++)
        if(target[i]<=stacked[i]*3)enough[i]=1,cnt++;
 
    while(cnt<target.size()){
        //x번 노드의 정보가 target[x-1]에 있으므로, -1해줘야함.
        int x=drop(tree,road)-1;
        simulation.push_back(x),stacked[x]++;
 
        if(target[x]<stacked[x]) return {-1};//과하게 쌓인 경우.
        if(target[x]<=stacked[x]*3)
            if(!enough[x])cnt++,enough[x]=1;//충분히 쌓인 경우.
    }
 
    vector<int> result;
    for(auto i:simulation){
        int x=max(1,target[i]-(stacked[i]-1)*3);
        target[i]-=x;stacked[i]--;
        result.push_back(x);
    }
    return result;
}

 

4. 코드 설명

int cnt=0;
for(int i=0;i<target.size();i++)
    if(target[i]<=stacked[i]*3)enough[i]=1,cnt++;

만약 처음부터 '충분히 쌓여있는' 노드가 있다면, 시뮬레이션 과정 중에 그러한 노드가 한 번도 방문되지 않더라도 답이 될 가능성이 있습니다. 그런데 그런 경우는 $cnt$가 갱신되지 않아 while문의 조건문을 만족시킬 수 없게 되므로, 미리 처리해주어야 합니다.

(사실 위의 if문은 $if(target[i]==0)$ 과 같은 의미이지만, 충분함을 만족하는 경우라는 것을 강조하기 위해 위와 같이 작성했습니다.)

    vector<int> result;
    for(auto i:simulation){
        int x=max(1,target[i]-(stacked[i]-1)*3);
        target[i]-=x;stacked[i]--;
        result.push_back(x);
    }
    return result;

숫자가 쌓인 노드의 번호들$(simulation)$을 보면서, 그 노드에 쌓인 숫자의 개수$(stacked)$를 $result$ 배열로 변환하는 과정입니다.

$simulation$배열을 쓰기 싫다면, 그냥 시뮬레이션했던 횟수만 기록해 둔 다음 $road$배열만 0으로 초기화해서 기록한 횟수만큼 다시 시뮬레이션을 돌리는 방법도 있습니다. 시간이 두배로 걸리겠지만요.

int x=max(1,target[i]-(stacked[i]-1)*3);

적당한 크기의 숫자 x를 고르는 과정입니다.

$(stacked[i]-1)*3$ 이 의미하는 것은, 현재 고를 숫자를 제외한(-1) 다른 숫자들을 다 3으로 골랐을 때(*3)의 값입니다.

이 값이 $target[i]$보다 크다는 것은, 아직은 사전 순으로 출력하기 위해서는 3보다 작은 숫자를 골라야 한다는 뜻입니다.

1이나 2를 고를 때마다 $target[i]-(stacked[i]-1)*3$ 값은 점점 커지게 되고, 이후 x=3이 되면서 $result$배열이 사전 순으로 완성됩니다.

 

    vector<int> result(simulation.size(),3);
    for(int i=0;i<target.size();i++)target[i]-=stacked[i]*3;
    
    for(int i=0;i<simulation.size();i++){
        int mi=max(-2,target[simulation[i]]);
        result[i]+=mi,target[simulation[i]]-=mi;
    }
    return result;

처음에 모든 숫자를 3으로 세팅해 놓고, 앞에서부터 숫자의 크기를 최대한 작게 만드는 위와 같은 방법도 있습니다.

이게 더 이해하기 쉬운 것 같네요.