백준 1327번
https://www.acmicpc.net/problem/1327

문제

---

생각하기

---

• BFS, 문자열 문제이다.

• 사실 완탐이긴 하나, 가지치기를 통한 BFS 방식으로 약간의 최적화를 해준다.

동작

        clone = arr.clone();
        Arrays.sort(arr);
        
        arrStr = new String(arr);
        cloneStr = new String(clone);

오름차순으로 정렬된 문자열과 원본 문자열 2개로 분리하고
이를 다시 문자열로 만듭니다.

        ArrayDeque<Swap> que = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        que.offer(new Swap(cloneStr, 0));
        // BFS를 통한 완탐인데, 가지치기를 포함

        while (!que.isEmpty()) {
            Swap cur = que.poll();

            if (arrStr.equals(cur.str)) return cur.cnt;

            if (set.add(Integer.parseInt(cur.str))) {
                for (int i = 0; i <= N - K; i++) {
                    que.offer(new Swap(makeStr(cur.str, i, i + K), cur.cnt + 1));
                }
            }
        }

que에 원본 문자열을 넣고 0부터 N - K까지 계속 반복하면서 문자열을 i 기준으로 i + i + K까지 문자열을 뒤집고 다시 연결 지으면서 일치하는 값을 찾아나간다.

처음 구현에서 가지치기할 때 boolean[Integer.parseInt()]를 통해 체크했는데
다른 분들 정답 결과와 비교해 보니 메모리가 2배 이상 많은 이유가 이 때문이었습니다.

HashSet<Integer>을 사용하면 훨씬 공간 효율성을 높일 수 있기 때문에 결국에
HashSet을 사용하는 것이 더 올바른 정답에 가깝다는 생각이 들었습니다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, K;
    private static char[] arr, clone;
    private static String arrStr, cloneStr;

    private static class Swap {
        String str;
        int cnt;

        private Swap(String str, int cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    } // End of Swap class


    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        clone = arr.clone();
        Arrays.sort(arr);

        arrStr = new String(arr);
        cloneStr = new String(clone);

        int ret = BFS();
        sb.append(ret);
        return sb.toString();
    } // End of solve()

    private static int BFS() {
        ArrayDeque<Swap> que = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        que.offer(new Swap(cloneStr, 0));
        // BFS를 통한 완탐인데, 가지치기를 포함

        while (!que.isEmpty()) {
            Swap cur = que.poll();

            if (arrStr.equals(cur.str)) return cur.cnt;

            if (set.add(Integer.parseInt(cur.str))) {
                for (int i = 0; i <= N - K; i++) {
                    que.offer(new Swap(makeStr(cur.str, i, i + K), cur.cnt + 1));
                }
            }
        }

        return -1;
    } // End of BFS()

    private static String makeStr(String str, int i, int j) {
        StringBuilder sb = new StringBuilder();

        sb.append(str, 0, i);
        String temp = str.substring(i, j);
        for (int k = K - 1; k >= 0; k--) {
            sb.append(temp.charAt(k));
        }

        sb.append(str, j, str.length());
        return sb.toString();
    } // End of makeStr()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new char[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = st.nextToken().charAt(0);
        }
    } // End of input()
} // End of Main class