백준 2661번 좋은수열 (JAVA)

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

2661번: 좋은수열

저는 해당 문제를 재귀를 이용하여 문제를 해결하였습니다.

숫자 배열을 통해 각각의 수를 넣어주고 해당 배열이 좋은 수열인지를 판단하고 맞다면 계속 진행하고 아니라면 진행하지 않았습니다.

(처음에는 모든 수를 구하고 좋은 수열인지 판단하였지만 이렇게하면 시간초과를 피할 수 없습니다.)

위의 방법은 int배열을 통해 문제를 해결하였고, 밑의 방법은 substring을 통해 문제를 해결하였습니다.

개인적으로 메모리 제한이 넉넉하다면 substring으로 푸는것이 더 빨리 풀 수 있는것 같습니다.

package BOJ.ETC;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.function.Function;

public class BOJ_2661 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String, Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int[] numbers = new int[n];
        System.out.println(dfs(0, numbers, n));
//        isGood(new int[] {1,2,1,2},4);
    }

    private static String INF = "9";

    private static String dfs(int depth, int[] numbers, int n) {
        if (depth == n) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(numbers[i]);
            }
            return sb.toString();
        }
        String result = INF;
        for (int i = 1; i <= 3; i++) {
            if (depth > 0 && i == numbers[depth - 1]) {
                continue;
            }
            numbers[depth] = i;
            if (!isGood(numbers, depth+1)) {
                continue;
            }
            String temp = dfs(depth + 1, numbers, n);
            if (!INF.equals(temp)) {
                result = temp;
                break;
            }
        }
        return result;
    }

    private static boolean isGood(int[] numbers, int n) {
        for (int i = 1; i <= n / 2; i++) { // 길이
            for (int j = 0; j <= n - 2 * i; j++) { // 시작 점
                boolean isPartSame = true;
                for (int k = 0; k < i; k++) {
                    if (numbers[j + k] != numbers[j + i + k]) {
                        isPartSame = false;
                        break;
                    }
                }
                if (isPartSame) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

 

 

package BOJ.ETC;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;

public class BOJ_2661_2 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        String numbers = "";
        System.out.println(dfs(0,numbers,n));
    }
    private static String INF = "9";
    private static String dfs(int depth, String numbers, int n) {
        if(depth == n){
            boolean flag = isGood(numbers,n);
            if(flag){
                return numbers;
            }
            return INF;
        }
        String result = INF;
        for(int i = 1; i <= 3; i++){
            String tempNumbers = numbers+i;
            if(!isGood(tempNumbers,depth+1)){
                continue;
            }
            String temp = dfs(depth + 1,tempNumbers,n);
            if(!INF.equals(temp)){
//                if(result.compareTo(temp) > 0){
//                    result = temp;
//                }
                result = temp;
                break;
            }
        }
        return result;
    }

    private static boolean isGood(String numbers, int n) {
        for(int i = 1 ; i <= numbers.length() / 2 ; i++){
            for(int j = 0 ; j < numbers.length() ; j++){
                if(j+2*i <= n && numbers.substring(j,j+i).equals(numbers.substring(j + i, j + 2*i))){
                    return false;
                }
            }
        }
        return true;
    }
}