코딩테스트 -- 택배상자 - (프로그래머스 / C++)

 

프로그래머스

 

문제!

---

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

 

---

요약하면 컨테이너벨트에서 정렬된 숫자가 차례대로 내려올텐데 이걸 택배기사가 원하는 배열대로 정렬시켜주면 되는 문제입니다.....

 

처음에 문제를 이해할때 헷갈려버렸습니다... 

글을 잘 읽어봐야하는 문제였습니다.

 

[4, 3, 1, 2, 5]   >>>> [1,2,3,4,5]  (x)

 

[1,2,3,4,5]  >>>>  [4, 3, 1, 2, 5]  (o)

 

처음에는 첫번째 방법인줄 알았는데

 

 

"영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다."

 

이 문장 하나로 이해했습니다   어쩐지 이상하더라..

 

 

 

그래서 나온 첫번째 풀이는! 실패....

숫자들을 2등분해서 보는 방식이였는데 이게 중간중간 계속 확인해줘야 한다는 것을 뒤늦게 알아버렸습니다.

 

틀린코드!

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

#include <queue>
using namespace std;



int solution(vector<int> order) {
    int answer = 0;
    vector<int> save1;//보조
    queue <int> save2;//원래
    
    
    // 1 2 3 4 5  이런식의 물건을  4 3 1 2 5  순으로 만들기!
    
    int p1=0;
    int p2=0;
    
    int index=0;// 채워넣어야할 order 위치
    
    for(int i=1;i<order.size()+1;i++){
        if(order[0]==i){//여기서부터 넣어주기
            save1.push_back(i);
            index=0;
            break;
        }
        else{
            save1.push_back(i);
        }
    }
    
    
    
    for(int i=order[index]+1;i<order.size()+1;i++){
        save2.push(i);
    }
    
    
    
    
    while(1){
        if(save1.size()==0){
            if(save2.front()==order[index] and order[index]!=0){/// 머지..?
                save2.pop();
                index+=1;
                answer+=1;
            }
            else{
                break;
            }
        }
        else if(save2.size()==0){
            if(save1.back()==order[index]){
                save1.pop_back();
                index+=1;
                answer+=1;
            }
            else{
                break;
            }
        }
        else{
            if(save1.back()==order[index]){
                save1.pop_back();
                index+=1;
                answer+=1;
            }
            else if(save2.front()==order[index]){
                save2.pop();
                index+=1;
                answer+=1;
            }
            else{
                break;
            }
        }
    }
    

    
    return answer;
}

 

 

 

그럼 이제 진짜 코드 시작!

---

먼저 보조 컨테이너를 만들어 줍시다.

그리고 이것저것 선언

 int answer = 0;
    vector<int> save1;//보조
    save1.push_back(10000001);
    
    // 1 2 3 4 5  이런식의 물건을  4 3 1 2 5  순으로 만들기!
    
    int index=0;// 채워넣어야할 order 위치

 

그다음은 원래 컨테이너 벨트에서 숫자를 하나씩 받아서 이걸 보조에 넣을지, 바로 트럭에 실을지 확인해 봅시다.

for(int i=1;i<order.size()+1;i++){
        if(order[index]==i){//바로 처리
            index+=1;

        }
        else if(order[index]==save1.back()){// 보조컨테이너에서 바로처리
            save1.pop_back();
            index+=1;
            i-=1;
            
        }
        else{
            save1.push_back(i);
        }
    }

여기서 i가 원래 컨테이너벨트에서 내려오는 숫자 역할을 하는데 

보조 컨테이너 벨트에서 숫자를 사용할때 i -1 을 해주시는 부분이 가장 중요! 나머지는 문제 그대로 구현해 주시면됩니다.

 

 

그리고 원래 컨테이너에서 모든 숫자가 빠졌을때

 while(save1.size()!=1){
        
        if(save1.back()==order[index]){
            index+=1;
            save1.pop_back();
        }
        else{
            break;
        }
        
    }

 보조 컨테이너에 들어있는 것들도 찾아서 봐줍시다.

 

 

여기까지가 끝!

 

 

문제를 이해하는 부분에서 헤멧네요... 꼼꼼히 읽어봅시다!

 

 

 

ALL

 

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    vector<int> save1;//보조
    save1.push_back(10000001);
    
    // 1 2 3 4 5  이런식의 물건을  4 3 1 2 5  순으로 만들기!
    
    int index=0;// 채워넣어야할 order 위치
    
    for(int i=1;i<order.size()+1;i++){
        if(order[index]==i){//바로 처리
            index+=1;

        }
        else if(order[index]==save1.back()){// 보조컨테이너에서 바로처리
            save1.pop_back();
            index+=1;
            i-=1;
            
        }
        else{
            save1.push_back(i);
        }
    }
    

    while(save1.size()!=1){
        
        if(save1.back()==order[index]){
            index+=1;
            save1.pop_back();
        }
        else{
            break;
        }
        
    }

    return index;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!