백준 2661[자바] java 좋은 수열

 

문제 링크: https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

 

▶문제

 

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그중에서 작은 수를 나타내는 수열은 1213121이다.

 

▶입력

 

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

▶출력

 

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

▶해설

 

1,2,3을 이용해서 수열을 만들어 나가는 문제입니다. 따라서 특정 조건을 만족한다면 숫자를 계속 붙이고, 만족하지 못한다면 그 숫자는 더이상 진행하지 않습니다.

 

진행 조건을 만들어보겠습니다.

 

어떠한 문자열이 동일하게 뒤이어 바로 반복 됐을 경우는 더 이상 진행하지 않습니다. 따라서 한 숫자를 붙였을 때 그 문자열 안에 동일한 문자열이 반복되는지 확인해주면 됩니다.

 

문자열이 반복되려는 최대 길이는 문자열을 반으로 잘랐을 때 반절이 가장 큰 길이입니다. 따라서 문자열의 길이가 1 ~ N/2까지 확인합니다.

 

1,2,3을 붙이기 전에 문자열은 이미 확인된 문자열이기 때문에 마지막 문자열을 포함한 문자열만 비교하면 됩니다. 

 

따라서

 

N까지의 문자열과 N-1까지의 문자열

N ~ N-1의 문자열과 N-2 ~ N-3까지의 문자열

N ~ N-3의 무자 열과 N-4 ~ N-6까지의 문자열을 비교하여 하나라도 같은 것이 있다면 더 이상 진행할 수 없는 문자열입니다. 앞서 말했듯이 N/2까지가 반복될 수 있는 문자열의 최대 길이입니다.

private static boolean check(String checkStr) {
    int length = checkStr.length() / 2;

    for (int i = 1; i <= length; i++) {
        if (checkStr.substring(checkStr.length() - i).equals(checkStr.substring(checkStr.length() - 2 * i, checkStr.length() - i))) {
            return false;
        }
    }

    return true;
}

 

전체 코드

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


public class Main {

    static int n;
    static String[] list = {"1", "2", "3"};
    static String answer = "9";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());


        dfs(0, "");

        System.out.println(answer);
    }

    private static void dfs(int index, String origin) {
        if (index == n) {
            System.out.println(origin);
            System.exit(0);
        }

        for (int i = 0; i <= 2; i++) {
            if (check(origin+list[i])) {
                dfs(index + 1, origin + list[i]);
            }
        }
    }

    private static boolean check(String checkStr) {
        int length = checkStr.length() / 2;

        for (int i = 1; i <= length; i++) {
            if (checkStr.substring(checkStr.length() - i).equals(checkStr.substring(checkStr.length() - 2 * i, checkStr.length() - i))) {
                return false;
            }
        }

        return true;
    }
}