• 문제: https://www.acmicpc.net/problem/2661

문제를 푸는 과정을 떠올리는 것은 쉬웠지만, 코드로 구현하는 것이 어려웠다. 🥲

설명

1. 1~3으로 이루어진 수열 만들기

private static void findSequence(String sequence) {
    if (sequence.length() == N) {
    	System.out.println(sequence);
        System.exit(0);
     }
     for (int i = 1; i <= 3; i++) {
         if (isGood(sequence + i)) {
             findSequence(sequence + i);
         }
     }
}

• 문자열 수열의 길이가 N과 같아질 때까지 재귀적으로 수열을 늘려나간다.
• 만들어진 문자열이 좋은 수열인지 매번 검사한다.
• 가장 작은 수를 출력하는 것이므로, 가장 먼저 나온 좋은 수열을 출력하고 함수를 종료한다.

2. 좋은 수열인지 확인하기
지금까지 좋은 수열이었지만, 문자가 추가되면 나쁜 수열이 될 수 있다. 따라서 매번 좋은 수열 여부를 확인하는 것이 필요하다.
수열은 마지만 인덱스를 기준으로 길이를 1씩 늘려가며 비교한다. 이때 left와 right가 같다면, 해당 수열은 나쁜 수열이 된다.

private static boolean isGood(String sequence) {
    for (int i = 1; i <= sequence.length() / 2; i++) {
        String front = sequence.substring(sequence.length() - i * 2, sequence.length() - i);
        String back = sequence.substring(sequence.length() - i, sequence.length());
        if (front.equals(back)) {
	         return false;
        }
    }
    return true;
}

• 위의 그림에 따라 문자열의 절반만큼 비교한다.
• 시작점 기준으로 비교하는 문자열의 왼쪽은 left가 되고, 문자열의 오른쪽은 right이다.
  • 문자열은 subString 함수를 이용하여 잘랐다.

subString 알아보기
간단해서 바로 간단히 정리하고 넘어간다.

• String substring(int index)
  index는 0부터 시작하고, 문자열의 앞에서 부터 몇번째 위치를 지정하는 값이다. 해당 index부터 문자열의 마지막 값까지 호출한다.

String str = "0123456789";
str.substring(5);	// 56789

• String substring(int beginIndex, int endIndex)
  시작 지점과 끝 점을 지정하여 호출할 수 있다.

String str = "0123456789";
str.substring(2, 5);	// 2345

3. 고려할 것

• 수열을 만든다. -> 무조건 int 배열로 만든다 (X)
  처음에 기존에 푸는 스타일대로 int 배열로 만들어 풀었지만, 이 문제에서는 문자열 비교와 출력을 고려했을 때, String으로 푸는 것이 적합했다. String도 문자들의 배열이니 덧셈을 제공한다.
• return vs System.exit(0)
  • return은 해당 메서드를 끝내는 것으로 아직 실행되어야 하는 함수가 있다면 마저 실행하고 종료한다.
  • System.exit(0)은 프로그램 자체를 종료시킨다. 이 문제에서는 최솟값만 구하고 종료하면 되기 때문에 System.exit(0)이 적합하다.

코드

package Algorithm.P2661;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class P2661 {
    static int N;
    static StringBuilder sb;
    static String result;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P2661/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        result = "";

        findSequence(result);
    }

    private static void findSequence(String sequence) {
        if (sequence.length() == N) {
            System.out.println(sequence);
            System.exit(0);
        }
        for (int i = 1; i <= 3; i++) {
            if (isGood(sequence + i)) {
                findSequence(sequence + i);
            }
        }
    }

    private static boolean isGood(String sequence) {
        for (int i = 1; i <= sequence.length() / 2; i++) {
            String front = sequence.substring(sequence.length() - i * 2, sequence.length() - i);
            String back = sequence.substring(sequence.length() - i, sequence.length());
            if (front.equals(back)) {
                return false;
            }
        }
        return true;
    }
}