백준 10973번 이전순열

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

public class Pre_Sort {
    static int N;
    static boolean[] visited;
    static List<Integer> list;
    static StringBuilder sb;
    static String prestr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        sb = new StringBuilder();
        StringBuilder firstsb = new StringBuilder();
        visited = new boolean[N+1];

        list = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <N+1 ; i++) {
            sb.append(st.nextToken()).append(" ");
            firstsb.append(i).append(" ");
        }
        if(sb.toString().equals(firstsb.toString())) {
            System.out.println(-1);
            return;
        }
        dfs(1);
        System.out.println(prestr);
    }
    public static void dfs(int num){
        if(list.size()==N){
            StringBuilder dfssb = new StringBuilder();
            for (int i = 0; i <N; i++) {
                dfssb.append(list.get(i)).append(" ");
            }
            if(dfssb.toString().equals(sb.toString())){
                return;
            }
            else {
                prestr = String.valueOf(dfssb);
            }
            System.out.println(prestr);
        }
        for (int i = 1; i < N+1; i++) {
            if(!visited[i]){
                list.add(i);
                visited[i] = true;
                dfs(i);
                visited[i] = false;
                list.remove(list.size()-1);
            }
        }
    }
}

풀이방법

1. 주어진 순열을 저장하는 sb, 가장 처음 순열을 뜻하는 firstsb를 만들고 두개가 같다면 -1을 출력한다.
2. 숫자를 오름차순으로 하나씩 담아 dfs 재귀함수를 수행한다. list에 숫자가 N개가 되면 dfssb를 만들어준다.
3. dfssb와 처음 입력받은 sb가 같다면 이전 순열을 저장하는 prestr을 출력시킨다.

후기

일단 백준사이트에서 이방법은 실패가 나온다. 처음부터 순열을 탐색하면 시간초과가 나온다.
하지만 정답인 풀이를 생각해내는게 개인적으로 억지라고 생각되서 그냥 dfs풀이로 남긴다.
저번 글에서도 언급했지만, 나는 시간복잡도 보다 구현가능성을 더 우선시 하기 때문에,,
dfs로 구현하는것 자체도 쉽지 않았고
👉 stringbuilder로 문자열 비교할때는 string으로 다시 바꿔서 equals 메서드를 사용한다는 점을 새로 알게 되었다.