[BOJ2661] 좋은 수열 (Java, 백트래킹)

문제 링크

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

 

 

풀이

- 백트래킹 사용

- 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다

- 인접한 두 개의 부분 수열이 서로 다르면서 좋은 수열 중 가장 작은 값을 찾는다

 

①재귀를 호출할 때 항상 1 ~ 3을 순차적으로 순회하기 때문에 처음 종료 조건(길이가 N인)에 부합하는 값이 최소값임이 보장된다

for(int i = 1; i <= 3; i++) {
  //..백트래킹 호출
}

 

 

*좋은 수열이기 위한 유효성 검사 관련하여

 

② 이전 값(prev)를 재귀 호출시 파라미터로 전달하고 for문에서 다음으로 연결할 값과 같은 경우(prev == i) continue

③ 이전 값(prev)과 다른 경우 해당 숫자를 문자열에 붙인 후(next) 임의의 길이의 부분 수열이 반복되는지 검증한다

(이때 길이 1은 ②에서 검증하기 때문에 2 ~ s.length() / 2 길이 만큼 검증하게 된다)

앞의 문자열을 front, 뒤의 문자열을 back이라고 했을 때
String back = s.substring(s.length() - i, s.length()); // 끝에서 i 길이 만큼의 문자열
String front = s.substring(s.length() - i * 2, s.length() - i); // back의 앞부분에서 i 만큼 길이를 자른 문자열

private static boolean possible(StringBuilder s) {
    int len = s.length();
    for(int i = 2; i <= len / 2; i++) {
        String back = s.substring(len - i, len);
        String front = s.substring(len - i * 2, len - i);
        if(front.equals(back)) return false;
    }

    return true;
}

 

 

제출 코드

추가로 리터럴 방식으로 문자열을 하게 될 경우 메모리 이슈가 발생할 수 있을거 같아 StringBuilder를 사용하였다

특히 눈에 띄는게 deleteCharAt(index)로 지정한 인덱스의 문자열을 버퍼에서 제거하는게 백트래킹에서 유용하게 사용되었다

*위에가 StringBuilder 사용한 방식, 아래가 String 리터럴을 사용한 방식

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 n;
    private static boolean finished;
    
    private static void input() {
        n = inputProcessor.nextInt();
    }

    private static void pro() {
        rec(0, 0, new StringBuilder());
    }

    private static void rec(int len, int prev, StringBuilder current) {
        if(finished) return;
        if(len == n) {
            finished = true;
            sb.append(current.toString());
            return;
        }

        for(int i = 1; i <= 3; i++) {
            if(i == prev) continue;

            current.append(i);
            if(possible(current)) {
                rec(len + 1, i, current);
            }

            current.deleteCharAt(current.length() - 1);
        }
    }

    private static boolean possible(StringBuilder s) {
        int len = s.length();
        for(int i = 2; i <= len / 2; i++) {
            String back = s.substring(len - i, len);
            String front = s.substring(len - i * 2, len - i);
            if(front.equals(back)) return false;
        }

        return true;
    }

    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());
        }
    }
}