코딩 테스트 일기 - 2일 차

김혁·2025년 6월 27일

프로그래머스

목록 보기

2/65

택배상자

문제 링크 : 택배상자

문제 설명

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.
만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.
예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.
택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

제한사항

1 ≤ order의 길이 ≤ 1,000,000
order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

입출력 예

order	result
[4, 3, 1, 2, 5]	2
[5, 4, 3, 2, 1]	5

풀이 방법

문제 설명이 매우 길어서 이해하는 데 시간이 걸렸지만, 메인 컨테이너 벨트는 큐 구조로 되어있고 뺄 수 있지만, 보조 컨테이너 벨트는 스택 구조로 되어있고 가장 위의 것만 뺄 수 있다는 것이 문제의 핵심 같았다. 그래서 기본적으로 메인 컨테이너 벨트와 보조 컨테이너 벨트를 생성해서, 보조 컨테이너 벨트의 탑을 확인한 후에 택배 상자와 다른 경우에는 메인 컨테이너 벨트에서 하나씩 빼가면서 검사하는 방법을 하고자 했다.
-> 해당 방법으로 할 시에 시간복잡도 O(N) 만큼이 걸릴 것으로 추정했다.

구현

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    int n = order.size();
    queue<int> mainContainer; // 메인 컨테이너 벨트 : 큐
    stack<int> subContainer;  // 보조 컨테이너 벨트 : 스택
    
    // 메인 컨테이너 벨트에 값 삽입 
    for(int i = 1; i <= n; i++){
        mainContainer.push(i);
    }
    
    while(answer < n){
        // 보조 컨테이너 벨트의 Top 체크
        if(!subContainer.empty() && order[answer] == subContainer.top()){
            subContainer.pop();
            answer++;
            continue;
        }
        
        bool isFlag = false;
        // 기본 컨테이너 벨트에서 빼가면서 체크
        while(!mainContainer.empty()){
            if(order[answer] == mainContainer.front()){
                mainContainer.pop();
                isFlag = true;
                answer++;
                break;
            }else{  // 기본 컨테이너 벨트의 상자 순서가 다르면 보조 컨테이너 벨트에 삽입
                subContainer.push(mainContainer.front());
                mainContainer.pop();
            }
        }
        
        if(!isFlag) break;
    }
    
    return answer;
}

큰 수 만들기

문제 링크 : 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요

제한사항

number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

풀이 방법

k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수는 맨 앞 자리의 수가 가장 커야한다. 최대한 큰 수를 앞에 둬야 하기 때문에 앞에서부터 스택에 값을 넣어가면서 뒤에 나오는 수보다 작다면 k개만큼의 수를 없애야 한다.
-> number의 길이만큼 테스트를 해야 하고, 스택에 쌓인 값을 검사했을 때, k의 값이 number의 길이 - 1이라고 하더라도 O(N)의 시간복잡도가 발생할 것으로 생각된다.
만약에 모든 수가 같거나, 앞의 숫자가 큰 경우 뒤에서 k만큼의 수를 지워줄 수 있어야 하기 때문에, 모든 값을 스택에 넣어서 k에서 남은 수만큼을 pop을 통해 제거해줘야 한다.
다음에 스택에 쌓아놓은 값들을 다시 answer에 넣은 후에 reverse를 통해서 숫자의 순서를 맞춰줘야 한다.
-> 최악의 경우 k가 1인 경우에는 reverse() 함수로 인해 O(N)만큼의 시간복잡도가 발생할 것으로 추정된다.

구현

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

using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> numStack;
    
    // 스택에 저장하면서 스택의 탑보다 큰 숫자가 나올 경우 체크하면서 삭제하기
    for(int i = 0; i < number.size(); i++){
        while(!numStack.empty() && k > 0 && numStack.top() < number[i]) {
            numStack.pop();
            k--;
        }
        numStack.push(number[i]);
    }
    
    // 혹시 모든 앞의 숫자가 뒤의 숫자보다 큰 경우, 뒤의 숫자 삭제
    for(int i = 0; i < k; i++){
        numStack.pop();
    }
    
    // 스택의 모든 값 빼기 및 순서 바꿔주기
    while(!numStack.empty()){
        answer += numStack.top();
        numStack.pop();
    }
    
    reverse(answer.begin(), answer.end());
    
    return answer;
}