[BOJ10597] 순열장난 (Java, 백트래킹)

문제 링크 

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

 

풀이

- 백트래킹 사용

- 정답은 구했으나 boolean[] visited 배열을 사용하는 것과 최대 수가 50인걸 파악하지 못한 풀이로 시간 초과 발생

- 잘못 풀이한 부분에 대한 이력 남김

 

문제 설명과 같이 1 ~ N까지의 숫자로 이루어진 순열을 구해야한다

- N = 10인 경우 1 부터 10 까지의 수가 중복 없이 모두 포함되어 있어야 한다는 의미

- "kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다."에서 (러프하게)최대 수가 50까지 라는 것을 파악할 수 있다

- 연산을 편하게 하기 위해서 int[] nums 배열을 선언 후 숫자 초기화를 수행하였다

 

백트래킹 수행할 함수를 아래와 같이 선언하였다

(idx >= 배열의 길이)인 경우 종료 조건에 걸리게 되고, 1 ~ max(N)까지 숫자가 모두 사용되었는지 검증한다

rec(int idx, int max, List<Integer> selected) { .. }

 

max의 경우 재귀 호출시 최대값을 갱신하게 되는데 종료 조건에서 1 ~ max까지 방문 여부 확인하여 모두 방문한 경우에만 정답 출력하게 된다

if(idx >= len) {
    for(int i = 1; i <= max; i++) {
        if(!visited[i]) return;
    }

    finished = true;
    for(int s : selected) {
        sb.append(s).append(" ");
    }

    return;
}

 

그리고 백트래킹에서 한 자리 수나 두 자리 수를 구해 각 재귀 호출하게 되는데 아래 검증을 통해 연산 횟수를 줄이게 된다

- visited[a] 방문 여부 : 중복 방문 필터링

- a < 51 범위 확인

- 이때 두 자리 수를 확인할 때는 (idx + 1 < 배열의 길이) 인지 확인이 필요하다 (배열 인덱스 초과 오류 발생 가능 하므로)

 

제출코드

import java.util.*;
import java.io.*;

public class Main {
    
    private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    public static void main(String[] args) {
        input();
        pro();
        output();
    }

    private static int[] nums;
    private static boolean[] visited;
    private static int len;
    private static boolean finished;

    private static void input() {
        String input = inputProcessor.next();
        len = input.length();

        nums = new int[len];
        for(int i = 0; i < len; i++) {
            nums[i] = input.charAt(i) - '0';
        }

        visited = new boolean[51];
    }

    private static void pro() {
        rec(0, 0, new ArrayList<>());
    }

    private static void rec(int idx, int max, List<Integer> selected) {
        if(finished) return;
        if(idx >= len) {
            for(int i = 1; i <= max; i++) {
                if(!visited[i]) return;
            }

            finished = true;
            for(int s : selected) {
                sb.append(s).append(" ");
            }

            return;
        }

        // 한 자리 수
        int a = nums[idx];
        if(!visited[a]) {
            visited[a] = true;
            selected.add(a);
            
            rec(idx + 1, Math.max(max, a), selected);
            
            selected.remove(selected.size() - 1);
            visited[a] = false;
        }
        
        // 두 자리 수
        if(idx + 1 < len) {
            a *= 10;
            a += nums[idx + 1];

            if(a > 50 || visited[a]) return;

            visited[a] = true;
            selected.add(a);
            
            rec(idx + 2, Math.max(max, a), selected);
            
            selected.remove(selected.size() - 1);
            visited[a] = false;
        }
    }

    private static void output() {
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static class InputProcessor {
        private BufferedReader br;
        private StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String result = "";

            try {
                result = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return result;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}