[백준, Java] 1039번 : 교환

🔗 문제 링크

https://www.acmicpc.net/problem/1039

😮 문제 해결 방법

주어진 숫자 M에 대해서 자릿수 교환이 K번 일어났을 때 나올 수 있는 최대값을 구하는 문제이다.

1. 자릿수 i보다 자릿수 j가 더 커야하는 제한 조건이 있기 때문에 교환할 수 있는 자릿수의 순서쌍을 모두 구한다.
2. 모두 구한 순서쌍과 함께 초기에 주어진 M 값과 K = 0인 상태로 큐에 넣어준다.
3. 매 턴 마다 존재할 수 있는 값을 순서쌍을 이용해 구한다.
   1. 큐의 사이즈만큼 반복한다.
   2. 순서쌍을 이용해 자릿수 교환이 이뤄졌을 때 값을 체크한다.
   3. 이미 현재 턴에 교환한 숫자가 나왔거나 0으로 시작하는 경우의 값은 큐에 넣지 않는다.
   4. 만약 턴을 모두 사용한 경우에는 Set에다가 넣어주고 큐에는 넣지 않는다.
   5. 이외의 경우라면 변경한 값으로 만들 수 있는 순서쌍을 반복해서 큐에 넣어준다.
4. 모든 턴을 돌고 Set에 들어간 값 중 최대값을 구하면된다.

✔️  메모리 초과가 발생한 부분은 큐에서 중복되는 값을 체크를 안해줘서 났었다. 중복적으로 나오눈 숫자를 제거하기 위해 배열을 선언해 체크해주는 부분이 주요했다.

🚩 Java 코드

package com.second.algorithm.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main_1039_교환 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        String N = st.nextToken();
        int K = Integer.parseInt(st.nextToken());

        int rst = changeNumber(N, K);
        System.out.println(rst);

        br.close();
    }

    private static int changeNumber(String n, int k) {
        if(n.length() == 1) return -1;
        if(n.length() == 2 && n.contains("0")) return -1;

        // 순서쌍 구하기
        List<Pair> pairs = getPairs(n.length());

        // 가능한 경우의 수로 큐로 변환
        Queue<Possible> queue = pairs.stream()
                .map(pair -> new Possible(n, pair.getFirst(), pair.getSecond(), 1))
                .collect(Collectors.toCollection(LinkedList::new));

        // 셋을 이용해 중복 제거
        Set<String> available = new HashSet<>();

        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean[] check = new boolean[1000001];

            // 큐 사이즈만큼 돌리기
            for (int loop = 0; loop < size; loop++) {
                Possible possibleNumber = queue.poll();

                String number = possibleNumber.getNumber();
                int firstIndex = possibleNumber.getFirst();
                int secondIndex = possibleNumber.getSecond();
                int turn = possibleNumber.getTurn();

                String afterSwap = swapNumber(firstIndex, secondIndex, number);

                // 이미 해당 턴에 체크했거나, 0으로 시작하는 경우 제외
                if (afterSwap.startsWith("0") || check[Integer.parseInt(afterSwap)]) continue;
                check[Integer.parseInt(afterSwap)] = true;

                // 턴을 다 사용한 경우
                if (turn == k) {
                    available.add(afterSwap);
                    continue;
                }

                // 변경된 값 큐에 넣기
                for (Pair pair : pairs) {
                    queue.add(new Possible(afterSwap, pair.getFirst(), pair.getSecond(), turn + 1));
                }
            }
        }

        // 최대값 구하기
        return available.stream().mapToInt(Integer::parseInt).max().getAsInt();
    }

    // 숫자 교환
    private static String swapNumber(int firstIndex, int secondIndex, String n) {
        return n.substring(0, firstIndex) + n.charAt(secondIndex) +
                n.substring(firstIndex + 1, secondIndex) + n.charAt(firstIndex) + n.substring(secondIndex + 1);
    }

    // 자릿수 교환 가능 경우의 수 담기
    private static List<Pair> getPairs(int m) {
        List<Pair> pairs = new ArrayList<>();
        for (int first = 0; first < m; first++) {
            for (int second = first + 1; second < m; second++) {
                pairs.add(new Pair(first, second));
            }
        }

        return pairs;
    }

    static class Pair {
        private int first;
        private int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public int getFirst() {
            return first;
        }

        public int getSecond() {
            return second;
        }
    }

    static class Possible {
        private String number;
        private int first;
        private int second;
        private int turn;

        public Possible(String number, int first, int second, int turn) {
            this.number = number;
            this.first = first;
            this.second = second;
            this.turn = turn;
        }

        public String getNumber() {
            return number;
        }

        public int getFirst() {
            return first;
        }

        public int getSecond() {
            return second;
        }

        public int getTurn() {
            return turn;
        }
    }
}