문제

풀이 과정

완전 탐색 문제. 문제 풀이는 비교적 간단한 편이다. 문제에 주어진대로, K 만큼씩 일부 문자를 뒤집어서 오름정렬이 될 수 있는 최소의 수를 구하면 된다. 즉 너비 우선 탐색의 미로 경로 최소 값 찾는 것과 같은 문제라고 할 수 있다.

문제는 풀긴 했지만 메모리 초과가 많이 나와서 애를 먹었는데, 메모리를 줄이는 방법을 찾아보려고 애를 많이 쓴 편이다.

일일이 코드로 테스트해서 구해보았음

1. 무엇보다도 식을 개선하여 메모리를 줄이는게 제일 효과적이다.

2. BufferedReader 를 써라. Scanner 보다 시간 속도도 빠르고, 메모리도 덜 차지한다.

3. StringBuilder.reverse() 보다는 for 문으로 직접 하는 것이 메모리를 덜 차지하는 듯 하다.

4. String.subString() 이 for 문 보다 메모리를 덜 차지하는 듯 하다. (확실치 않음)

5. 자주 사용하는 변수를 static 으로 돌리는 것이 그나마 메모리를 덜 차지하는 듯 하다.

6. String 자체가 메모리 사용이 크다! StringBuilder 를 사용하자!

메모리 초과의 주요 원인은 6번이었다..

정답

import java.util.*;

public class Main {
    static String sortStr;
    static int N, K, L, R;
    static String prevStr, midStr, nextStr;

    static StringBuilder midSb;
    static class Node {
        String str;
        int cnt;

        public Node(String str, int cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    }
    static Node curr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < N; i++) {
             str.append(sc.next());
        }
        char[] temp = str.toString().toCharArray();
        Arrays.sort(temp);
        sortStr = new String(temp);
        System.out.println(BFS(str.toString()));
    }

    private static int BFS(String st) {
        Queue<Node> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        q.add(new Node(st, 0));

        while (!q.isEmpty()) {
            curr = q.poll();

            if (sortStr.equals(curr.str)) {
                return curr.cnt;
            }

            if (set.contains(curr.str)) continue;
            set.add(curr.str);

            L = 0;
            R = K;
            while (R <= N) {
                prevStr = curr.str.substring(0,L);
                midStr = curr.str.substring(L, R);
                nextStr = curr.str.substring(R,N);
                midSb = new StringBuilder();
                for(int i=midStr.length()-1; i>=0; i--) midSb.append(midStr.charAt(i));

                q.add(new Node(new StringBuilder().append(prevStr).append(midSb.toString()).append(nextStr).toString(), curr.cnt + 1));
                L++;
                R++;
            }
        }

        return -1;
    }
}