Part of your World

문제 설명

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

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

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

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

제한사항

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

입출력 예

order result

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 모든 상자를 보조 컨테이너 벨트에 모두 넣고, 역순으로 하나씩 빼서 트럭에 싣습니다.

package LV2;

import java.util.Stack;

public class H131704 {
    public int solution(int[] order) {
        // 실은 상자의 개수를 저장하는 변수
        int answer = 0;

        // 보조 벨트를 구현한 스택
        Stack<Integer> stack = new Stack<>();

        // 다음에 트럭에 실어야 할 상자 번호
        int next = 1;

        // 현재 메인 벨트에서 확인하고 있는 상자의 위치
        int i = 0;

        // order 배열의 각 원소를 key로, 그 위치를 value로 하는 box 배열을 생성
        // 이 배열은 각 상자가 트럭에 언제 실어야 하는지를 저장
        int[] box = new int[order.length + 1];
        for(int j = 0; j < order.length; j++) {
            box[order[j]] = j+1;
        }

        // 모든 상자를 확인할 때까지 반복
        while (next <= order.length) {
            // 현재 확인하고 있는 상자가 트럭에 실어야 할 상자라면
            if (i < order.length && box[i+1] == next) {
                // 트럭에 실고, 다음 상자를 확인
                next++;
                i++;
                answer++;

                // 보조 벨트에서 상자를 확인하면서, 트럭에 실어야 할 상자가 있으면 싣는다.
                while (!stack.isEmpty() && stack.peek() == next) {
                    stack.pop();
                    next++;
                    answer++;
                }
                // 현재 확인하고 있는 상자가 트럭에 실어야 할 상자가 아니라면
            } else if (i < order.length){
                // 보조 벨트에 넣고, 다음 상자를 확인한다.
                stack.push(box[i+1]);
                i++;
            } else {
                // 모든 상자를 확인했다면 반복문을 종료한다.
                break;
            }
        }

        // 트럭에 실은 상자의 개수를 반환한다.
        return answer;
    }
}

order 배열의 원소는 해당 상자가 메인 컨베이어 벨트에 위치한 순서가 아니라, 트럭에 실어야 하는 순서이다다. 따라서 order 배열을 순서대로 처리하면서, 메인 컨베이어 벨트에서 상자를 가져와야 한다.

수정된 알고리즘은 다음과 같다:

1. order 배열을 순서대로 처리하면서, 트럭에 실어야 할 다음 상자가 메인 컨베이어 벨트의 첫 번째 상자인지 확인한다.
2. 만약 그렇다면, 트럭에 싣고 다음 숫자로 넘어간다.
3. 만약 그렇지 않다면, 메인 컨베이어 벨트에서 상자를 하나씩 꺼내서 보조 컨베이어 벨트(스택)에 넣는다. 이 과정을 트럭에 실어야 할 다음 상자가 나올 때까지 반복한다.
4. 트럭에 실은 상자의 개수를 반환한다.

box 배열을 생성해서 order의 값이 트럭에 언제 실어야 하는지에 대한 정보를 가지고 있다.

그리고 메인 벨트에서 상자를 하나씩 확인하며, 필요한 상자가 나오면 트럭에 싣고 다음 상자를 확인한다.

만약 필요한 상자가 아니라면, 해당 상자를 보조 벨트에 넣는다.

이 과정을 필요한 상자가 보조 벨트에 없을 때까지 반복한다.

order 배열의 각 상자를 한 번씩만 확인하므로, 시간 복잡도는 O(n)이다.

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법 124 나라 10진법 124 나라

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 50,000,000이하의 자연수 입니다.

입출력 예

n result

package LV2;

public class H12899 {
    public String solution(int n) {
        // 1, 2, 4를 각각 인덱스 1, 2, 0에 위치시킨 배열
        String[] numbers = { "4", "1", "2" };
        // 변환 결과를 저장할 문자열
        String answer = "";

        // n이 0이 될 때까지 반복
        while (n > 0) {
            // n을 3으로 나눈 나머지를 구함
            int remainder = n % 3;
            // n을 3으로 나눔
            n /= 3;

            // 나머지가 0인 경우, 즉 n이 3의 배수인 경우 n에서 1을 뺌
            if (remainder == 0) n--;

            // 나머지에 해당하는 숫자를 answer 문자열의 앞에 붙임
            answer = numbers[remainder] + answer;
        }

        return answer;
    }
}

3진법 변환과 유사하나, 각 자리가 0부터 시작하는 것이 아닌 1부터 시작하고, 숫자 3 대신에 숫자 4를 사용하는 것이 특징이다. 따라서 숫자 n을 3으로 나눈 나머지와 몫을 사용하여 문제를 풀 수 있다. 그러나 n이 3의 배수일 때에는 몫에서 1을 빼고 나머지를 4로 바꿔줘야 한다.

numbers 배열을 만들어 1, 2, 4를 각각 인덱스 1, 2, 0에 위치시킵니다. 이후 주어진 숫자 n에 대해 while 루프를 돌며 3으로 나눈 나머지를 구하고, n을 3으로 나눈다. 나머지가 0인 경우, 즉 n이 3의 배수인 경우에는 n에서 1을 빼준다. 이후 나머지에 해당하는 숫자를 answer 문자열의 앞에 붙여준다. 이 과정을 n이 0이 될 때까지 반복한다.

문제 설명

어떤 숫자에서 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

package LV2;

import java.util.Stack;

public class H42883 {
    public String solution(String number, int k) {
        // 결과를 저장할 배열, k개의 숫자를 제거하므로 전체 길이에서 k를 뺀 만큼만 필요
        char[] result = new char[number.length() - k];
        // 숫자를 저장할 스택
        Stack<Character> stack = new Stack<>();

        // 입력 문자열의 모든 문자를 순회
        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            // 스택이 비어있지 않고, 스택의 맨 위 숫자가 현재 숫자보다 작고, 아직 제거할 숫자가 남아있는 동안
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop(); // 스택의 맨 위 숫자 제거
            }
            // 현재 숫자를 스택에 삽입
            stack.push(c);
        }
        // 스택의 내용을 결과 배열에 복사
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        // 결과 배열을 문자열로 변환하여 반환
        return new String(result);
    }
}

스택 자료구조를 활용하여 풀 수 있다.

문제의 목표는 k개의 수를 제거했을 때 가장 큰 숫자를 만드는 것이다. 이를 위해 앞자리에서부터 하나씩 스택에 넣는다. 이때 스택의 맨 위의 수보다 큰 수가 들어온다면, 그보다 큰 수가 들어올 때까지 스택의 맨 위의 수를 제거하고 카운트한다. 이렇게 하면 항상 스택의 맨 위에는 현재까지의 최댓값이 위치하게 된다. 그리고 카운트가 k에 도달하면 더 이상 수를 제거하지 않고 나머지 수를 모두 스택에 넣는다.

우선 입력 문자열 **number**의 각 문자에 대해 반복문을 돌면서 처리한다. 그리고 **stack.peek() < c**인 경우(즉, 스택의 맨 위의 수보다 더 큰 수가 들어온 경우)에는 그 수를 스택에서 제거하고 카운트를 증가시킨다. 그리고 그런 경우가 아니라면 수를 스택에 그대로 넣는다. 마지막으로, 결과 문자열 **result**에 스택에 남아 있는 수를 차례로 넣어 반환한다.