[파이썬, Java] 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 

7

예제 출력 1 

1213121

 

 

🐝 나의 풀이

import java.util.*;
class Main {
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dfs("1");
    }

    public static void dfs(String string) {
        for (int i = 1; i < string.length() / 2 + 1; i++) {
            int start = 0;
            int start1 = i + start;
            for (int j = 0; j < string.length() - (2 * i) + 1; j++) {
                if (string.substring(start + j, start + j + i).equals(string.substring(start1 + j, start1 + j + i))) {
                    return;
                }
            }
        }
        
        if (string.length() == N) {
            System.out.println(string);
            System.exit(0);
        }

        for (int i = 1; i < 4; i++) {
            dfs(string + i);
        }
    }
}

아래 메모리 초과를 해결했다.

이중 for문 내에서 return을 한 적이 없는 string이 출력된다.(길이가 N이라면)

좋은수열을 찾는 부분은 다른 사람의 풀이를 참고했다.

 

 

// 메모리 초과
import java.util.*;
class Main {
    static int N;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        N =sc.nextInt();
        dfs("1");
    }

    public static void dfs(String string){
        if(string.length() == N){
            for(int i=1; i<string.length()/2+1; i++){
                int start=0;
                int start1=i+start;
                for(int j=0; j<string.length()-(2*i)+1; j++){
                    if(string.substring(start+j, start+j+i).equals(string.substring(start1+j, start1+j+i))){
                        return;
                    }
                }
            }
            System.out.println(string);
            System.exit(0);
        }

        for(int i=1; i<4; i++){
            dfs(string+i);
            }
        }
    }

String은 문자열을 추가할 때 새로운 String이 생성된다.

이것 때문에 메모리 초과가 났을 것이다.

StringBuilder 써도 메모리 초과야 ㅠ

좋은수열인지 판별하는 부분이 문제인 것 같다.

N이 7일 때 좋은 수열은 1213121인데 1111111~1213121까지 이중  for문을 돌린다.

가지치기가 제대로 되지 않아 메모리 초과가 났다.

 

 

# 실패(시간초과)
import sys
input=sys.stdin.readline
N=int(input())
ans=0
lst=[1, 2, 3]


def pointer(num):
    start=0
    copy_num=str(num)
    end=len(copy_num)
    while start < end :
        for i in range(end-1, start, -1) :
            mid=(start+i)//2
            a=copy_num[start:mid+1]
            b=copy_num[mid+1:i+1]
            if a == b :     # 나쁜수열
                return False
        start+=1
    return True


def dfs(depth, num) :
    if depth == N :
        if pointer(num):  # 좋은 수열일까?
            print(num)
            sys.exit()
        return
    
    for i in lst :
        dfs(depth+1, num*10+i)


dfs(0, 0)

dfs로 풀었다.

시간초과가 나는 것은 좋은수열인지 판별하는 pointer 함수에서 났을 것이다.

리스트 슬라이싱이 시간복잡도가 O(N)이니까 ㅠ

그리고 길이가 같은 수열끼리만 비교하게 했어야 했는데..

sys.exit()로 하나만 출력하고 프로그램을 종료시킨다.

 

 

🦔 다른 사람 풀이

# https://donghak-dev.tistory.com/180?category=904697
import sys

def check(s) :
    for i in range(1, (len(s)//2)+1) :
        leng=i
        start=0
        start2=start+i
        for j in range(len(s)-(leng*2)+1) :
            if s[start+j : start+j+leng] == s[start2+j : start2+j+leng] :
                return False
    return True

def make_num(number, N) :
    if check(number) is False :
        return
    if len(number) == N :
        print(number)
        sys.exit()
    else :
        for j in range(1, 4) :
            make_num(number+str(j), N)

N=int(input())
make_num('1', N)

	j=0	j=1	j=2	j=3	j=4	j=5
i=1	1 != 2	2 != 1	1 != 3	3 != 1	1 != 2	2 != 1
i=2	12 != 13	21 != 31	13 != 12	31 != 21
i=3	121 != 312	213 != 121

1213121의 비교과정을 표로 나타냈다.

i는 수열의 길이다.

 

 

# https://sungmin-joo.tistory.com/66
def back_tracking(idx) :
    for i in range(1, (idx//2)+1) :
        if s[-i:] == s[-2*i : -i] : return -1

    if idx == n :
        for i in range(n) : print(s[i], end='')
        return 0

    for i in range(1, 4) :
        s.append(i)
        if back_tracking(idx+1) == 0 :
            return 0
        s.pop()

if __name__ == "__main__" :
    n=int(input())
    s=[]
    back_tracking(0)

백트래킹 풀이

뒤에서부터 길이가 i인 수열을 비교한다.

123123213같은 경우는 123123일 때 나쁜 수열로 판단되어 return된다.

123123으로 시작하는 수열은 다시는 방문하지 않는다.(가지치기)

 

 

// https://bellog.tistory.com/43
import java.io.*;
class Main {
    static int N;
    static StringBuilder sb=new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        backtracking("");
    }

    private static void backtracking(String result){
        if(result.length() == N){
            System.out.println(result);
            System.exit(0);
            }else{
                for(int i=1; i<=3; i++){
                    if(isGoodSequence(result+i)){
                        backtracking(result+i);
                    }
                }
        }
    }

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

isGoodSequence 메소드의 결과가 좋은수열이면 재귀호출한다.

s의 절반까지 비교한다.

 

 

 

문제 출처 👉 백준