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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 생각보다 어려워 보였지만 생각보다 쉬웠던 문제였다.

 

규칙을 보면 길을 한번 지나가면 다음 길로 바뀌는 부분이 있다.

처음에는 int배열을 만들어 현재 어떤 길이 있는지 탐색하고 다음길을 가리키도록 하려고 했지만, 그냥 정렬을 한 다음 queue로 한번 지나간 길은 pop & push를 하면 길 찾기가 쉽다고 생각해 queue로 구현했다.

 

그렇게 한번 지나갈 때마다 어떤 leaf에 도달하는지를 구하면, 그 leaf에는 1~3의 값이 들어갈 수 있다.

 

이후 특정 leaf에 숫자가 들어가는게 정해질 때마다  target과 비교해 도달할 수 있는지를 비교했다.

target을 만들 수 있는지 비교하는 방법은 최대와 최소를 이용했다.

 

leaf에 숫자를 담을 때 최소 1, 최대 3을 담을 수 있으므로 만약 leaf에 숫자를 담은 count*1<=target<=count*3의 범위 안에 있으면 그 leaf는 조건을 만족한다.

 

만약 count*3보다 target이 크다면 계속 숫자를 떨어뜨려 leaf에 숫자를 담을 수 있는 기회가 있고,

만약 하나의 leaf라도 count*1이 target보다 크면 더 이상 배열을 만족할 수 없으므로 [-1]을 return하면 된다.

 

마지막으로 배열을 사전에서 빠른순으로 나열을 해야하는데, 이는 뺄셈을 이용했다.

 

1. [target에 담을 수 있는 숫자 개수-1] * 3이 [target의 수-1] 보다 크거나 같을 경우

위 경우를 만족하면 배열에 1을 추가하고, 다음 leaf에 어떤 수를 넣을지 계산한다.

만약 이 경우를 만족하지 않는다면 더 이상 1을 담을 수 없으므로 2번으로 넘어간다.

 

2. [target에 담을 수 있는 숫자 개수-1] * 3이 [target의 수-2] 보다 크거나 같을 경우

이 경우를 만족하면 배열에 2를 추가하고, 다음 leaf에 어떤 수를 넣을지 계산한다.

만약 이 경우도 만족하지 않는다면 3번 경우만 남게된다.

 

3. [target에 담을 수 있는 숫자 개수-1] * 3이 [target의 수-2] 만 가능하다.

이유는 위에 최소 배열의 길이를 구할 때 최대 범위를 3으로 잡고 계산했기 때문에 1번과 2번 둘다 만족하지 않으면 3번 경우만 남기 때문이다.

 

​

[아이디어 정리]

1. leaf에 숫자가 들어오는 수를 세 cnt로 저장한다.
2. leaf에 숫자가 들어올 때마다 target과 비교해 target 배열을 완성 가능한지 검사한다.
3. 만약 target 배열을 아직 완성할 수 없다면, 1번과 2번을 반복한다.
4. 만약 target 배열을 완성할 수 있다면, 1, 2, 3을 빼면서 사전순으로 가장 빠른 배열을 만든다.
5. 만약 target 배열의 완성이 불가능하다면, [-1]을 return한다.

 

 

Code

 

 

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

vector<queue<int>> nodeRoad;
vector<vector<int>> nodeV;
vector<int> targetCnt;
vector<int> realTarget;
int targetLeaf() // road변경하는 함수
{
    int stNode=1;
    int nowRoad;
    while (!nodeRoad[stNode].empty())
    {
        nowRoad=nodeRoad[stNode].front();
        nodeRoad[stNode].pop();
        nodeRoad[stNode].push(nowRoad);
        stNode=nowRoad;
    }
    return stNode;
}

int canMakeLeaf() // returnInt가 0이면 끝, 1이면 계속 찾기, 2면 불가능
{
    int returnInt=0;
    for (int i=0; i<targetCnt.size(); i++)
    {
        if (targetCnt[i]*3<realTarget[i])
        {
            returnInt=1;
        }
        if (realTarget[i]<targetCnt[i])
        {
            returnInt=2;
            return returnInt;
        }
    }
    return returnInt;
} 

vector<int> solution(vector<vector<int>> edges, vector<int> target) {
    nodeV=vector<vector<int>>(target.size()+1);
    nodeRoad=vector<queue<int>>(target.size()+1);
    targetCnt=vector<int>(target.size()+1,0);
    realTarget.push_back(0);
    realTarget.insert(realTarget.end(), target.begin(), target.end());
    
    for (int i=0;i<edges.size();i++)
    {
        nodeV[edges[i][0]].push_back(edges[i][1]);
    }
    for(int i=0; i<nodeV.size(); i++)
    {
        sort(nodeV[i].begin(),nodeV[i].end());
    }
    // nodeRoad 복사
    for (int i = 0; i < nodeV.size(); i++) {
        for (int j=0; j<nodeV[i].size(); j++)
        {
            nodeRoad[i].push(nodeV[i][j]);
        }
    }
    
    int canMake;
    int leafNum;
    vector<int> answer;
    while(true) // 방문 가능한 최소 횟수를 계산
    {
        leafNum=targetLeaf();
        answer.push_back(leafNum);
        targetCnt[leafNum]+=1;
        canMake=canMakeLeaf();
        if (canMake==0)
        {
            break;
        }
        else if(canMake==2)
        {
            return vector<int>(1,-1);
        }
    }
    // 사전순으로 계산하는 부분
    vector<int>RA;
    for (int i=0; i<answer.size(); i++)
    {
        leafNum=answer[i];
        targetCnt[leafNum]-=1;
        if (targetCnt[leafNum]*3>=realTarget[leafNum]-1)
        {
            RA.push_back(1);
            realTarget[leafNum]-=1;
        }
        else if(targetCnt[leafNum]*3>=realTarget[leafNum]-2)
        {
            RA.push_back(2);
            realTarget[leafNum]-=2;
        }
        else
        {
            RA.push_back(3);
            realTarget[leafNum]-=3;
        }
    }
    
    return RA;
}

 

---

 

 

코드가 길어서 그렇지 생각보다 어려운 문제는 아니였다.

다만 구현을 하다보니 중간에 검사를 안하고 쭉 나열하면서 코드를 작성했는데 다행히 틀린 부분이 없어서 빨리 풀 수 있었다.

이런 유형의 문제들이 풀면 은근히 잘 풀리는데 왠지 찜찜하단 말이지...

 

프로그래머스