Part of your World

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

x y n result

입출력 예 설명

입출력 예 #1

x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3

x를 y로 변환할 수 없기 때문에 -1을 return합니다.

너비 우선 탐색(BFS)를 사용하여 풀 수 있다. 주어진 연산에 대하여 모든 가능한 결과를 큐에 넣고, 이를 반복하면서 y에 도달할 때까지의 최소 연산 횟수를 찾을 수 있다.

package LV2;

import java.util.LinkedList;
import java.util.Queue;

public class H154538 {
    public int solution(int x, int y, int n) {
        // 연산 결과 범위를 1_000_001로 설정
        final int MAX = 1_000_001;

        // check 배열은 각 숫자에 도달하기 위한 최소 연산 횟수를 저장
        // 아직 도달하지 못한 숫자는 -1로 초기화하기
        int[] check = new int[MAX];
        for (int i = 0; i < MAX; i++) {
            check[i] = -1;
        }

        // 큐를 생성하고 시작 숫자 x를 넣는다.
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        // x에 대한 연산 횟수를 0으로 설정한다.
        check[x] = 0;

        // 큐가 비어있지 않은 동안 다음을 반복!
        while (!queue.isEmpty()) {
            // 큐에서 숫자를 꺼낸다.
            int current = queue.remove();

            // 꺼낸 숫자가 y와 같다면, 그 때의 연산 횟수를 반환한다.
            if (current == y) {
                return check[current];
            }

            // 꺼낸 숫자에 n을 더하거나, 2를 곱하거나, 3을 곱하여 다음 숫자를 계산한다.
            int[] next = {current + n, current * 2, current * 3};
            for (int i = 0; i < 3; i++) {
                // 다음 숫자가 범위 내에 있고 아직 방문하지 않았다면,
                if (next[i] > 0 && next[i] < MAX && check[next[i]] == -1) {
                    // 큐에 다음 숫자를 넣고 연산 횟수를 업데이트한다.
                    queue.add(next[i]);
                    check[next[i]] = check[current] + 1;
                }
            }
        }

        // 큐가 비어도 y에 도달하지 못했다면, y에 도달할 수 없다는 의미이므로 -1을 반환한다.
        return -1;
    }
}

입력값 범위가 1,000,000 이하라는 것을 이용한다. check 배열은 각 숫자에 도달하기 위한 최소 연산 횟수를 저장하며, 아직 도달하지 못한 숫자는 -1로 초기화한다.

큐에 시작 숫자 x를 넣고, x에 대한 연산 횟수를 0으로 설정한다. 그 후, 큐가 비어있지 않은 동안 다음을 반복한다:

1. 큐에서 숫자를 꺼내온다.
2. 꺼낸 숫자가 y와 같다면, 그 때의 연산 횟수를 반환한다.
3. 꺼낸 숫자에 n을 더하거나, 2를 곱하거나, 3을 곱하여 다음 숫자를 계산한다.
4. 만약 다음 숫자가 범위 내에 있고 아직 방문하지 않았다면, 큐에 다음 숫자를 넣고 연산 횟수를 업데이트한다.

만약 큐가 비어도 y에 도달하지 못했다면, y에 도달할 수 없다는 의미이므로 -1을 반환한다.

https://aihtnyc-h.tistory.com/entry/%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers result

입출력 예 설명

입출력 예 #1

2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2

9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

스택을 이용해 풀 수 있다. 문제의 요구사항에 따라 자신보다 큰 가장 가까운 숫자를 찾기 위해, 우선 모든 숫자의 뒷 큰수를 -1로 설정해두고, 오른쪽부터 왼쪽으로 스택에 숫자를 넣어가며, 스택의 최상위 숫자보다 큰 숫자가 나올 경우 해당 숫자를 스택에서 빼고 그 자리에 뒷 큰수를 저장한다.

package LV2;

import java.util.Stack;

public class H154539 {
    public int[] solution(int[] numbers) {
        // numbers의 길이를 length에 저장한다.
        int length = numbers.length;

        // 결과를 담을 배열 answer를 초기화하고, 모든 원소를 -1로 설정한다.
        int[] answer = new int[length];

        // 숫자를 저장할 스택을 생성한다.
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < length; i++) {
            answer[i] = -1;
        }

        // 오른쪽에서 왼쪽으로 이동하면서 각 숫자에 대한 뒷 큰수를 찾는다.
        for(int i = length - 1; i >= 0; i--) {
            // 현재 숫자가 스택의 최상위 숫자보다 크면, 스택에서 숫자를 빼고 뒷 큰수를 현재 숫자로 설정한다.
            while(!stack.isEmpty() && stack.peek() <= numbers[i]) {
                stack.pop();
            }

            // 스택이 비어있지 않고, 스택의 최상위 숫자가 현재 숫자보다 크다면, 뒷 큰수를 스택의 최상위 숫자로 설정한다.
            if(!stack.isEmpty() && stack.peek() > numbers[i]) {
                answer[i] = stack.peek();
            }

            // 현재 숫자를 스택에 넣는다.
            stack.push(numbers[i]);
        }

        // 모든 숫자의 뒷 큰수를 담은 배열을 반환한다.
        return answer;
    }
}

answer 배열을 입력받은 numbers의 길이로 초기화하고, 모든 원소를 -1로 설정한다. 그 후, 스택을 생성한다.

그 다음, 오른쪽부터 왼쪽으로 숫자를 보면서, 현재 숫자가 스택의 최상위 숫자보다 클 경우, 스택에서 숫자를 빼고 해당 숫자의 뒷 큰수를 현재 숫자로 설정한다. 이 과정을 반복하여 모든 숫자에 대한 뒷 큰수를 찾는다. 마지막으로, 현재 숫자를 스택에 넣는다.

모든 숫자에 대해 이 과정을 반복하면, 최종적으로 모든 숫자의 뒷 큰수를 찾을 수 있다.

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers return

package LV2;

import java.util.Arrays;
import java.util.Comparator;

public class H42746 {
    public String solution(int[] numbers) {
        // 숫자를 문자열로 변환
        String[] result = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            result[i] = String.valueOf(numbers[i]);  // 정수를 문자열로 변환하여 저장
        }

        // 정렬
        Arrays.sort(result, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 두 문자열을 앞뒤로 이어 붙인 두 경우를 비교하여 더 큰 숫자 순서로 정렬
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        // 0만 여러 개 있는 경우에 대한 처리
        if (result[0].equals("0")) {  // 가장 큰 수가 '0'이라면 전체가 0이므로 "0"을 반환
            return "0";
        }

        String answer = "";
        for (String str : result) {
            answer += str;  // 정렬된 문자열을 이어붙여 결과 생성
        }

        return answer;  // 결과 반환
    }
}

문자열을 비교할 때 **(o2 + o1).compareTo(o1 + o2)**를 사용하여 두 문자열을 이어붙였을 때 어느 경우가 더 큰지 비교하고 있다. 이렇게 하면 숫자를 이어붙였을 때 가장 큰 수를 만들 수 있는 순서로 정렬할 수 있다.