[Python] 2661번 : 좋은 수열

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

2661번: 좋은수열

 

문제 3줄 요약

1. 숫자 1, 2, 3 으로만 이루어져 있는 수열이 있다.

2. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 나쁜 수열. 아니라면 좋은 수열

3. N자리의 좋은 수열 중에서도 가장 작은 좋은 수열을 구하여라. 

 

 

---

 

문제만 읽어봤는데도 정신이 혼미해졌다.

 

단순히 연속되는 숫자가 아닌

연속되고 인접한 '수열'을 걸러내야 하면서

N의 자리 수열 중 가장 작아야한다.

 

 

일단 통과한 코드를 기반으로 설명해보겠다.

 

만일 1, 2가 리스트에 들어있다면,

그 다음에 들어올 수 있는 정수는 1, 3 일 것이다.

즉, [1, 2, 3] 중 마지막 원소를 제외한 1, 3이 들어올 수 있는 가지가 되는 것이다.

 

 

때문에 스택에 숫자를 역순으로 넣고

pop연산을 하며 정답 리스트에 넣는다.

 

pop 1. ) num_list = ['3', '2'],       answer_list = ['1']

push 1.) num_list = ['3', '2', '3', '2'],       answer_list = ['1']

pop 2.) num_list = ['3', '2', '3'],          answer_list= ['1', '2']

 

●

●

●

 

이런 방식으로 진행될 것이다.

 

from sys import stdin

if __name__ == "__main__":
    N = int(stdin.readline())
	
    # 스택, 정답 리스트, 백트레킹 체크변수 선언
    num_list, answer_list, pass_chk  = ['3','2','1'], [], 0
    
    # 스택의 원소가 없을 때 까지 반복
    while(len(num_list) != 0):
    
        # 마지막 원소 pop하여, 정답 리스트에 삽입
        num = num_list.pop()
        answer_list.append(num)
        
        # 마지막 원소와 넣은 원소가 같은 경우는 pop
        if len(answer_list) > 1 and answer_list[-1] == answer_list[-2]:
            answer_list.pop()
            
        # 넣은 원소 외에 정수 스택에 push
        for next in ['3','2','1']:
            if next != num:
                num_list.append(next)

	 # 주어진 자리수와 같은 수열이 완성되면 print
        if len(answer_list) == N:
            print(''.join(answer_list))
            break

 

---

 

하지만

N이 7 이후가 된다면, 문제가 생긴다.

 

N이 7일 때, 1213121이 완성된다.

다음에 1이 올 경우, 마지막 원소와 중복이라 x

2가 올 경우, 마지막 4개의 원소가 1212로 12가 중복

3이 온다면, 1213 1213가 중복된 8자리 수열이 되므로 x

 

어떤 정수가 와도

좋은 수열이 성립되지 않는다.

 

따라서

우린 다시 가지(부모 원소)를 올라가 갈랫길에서 다른 가지(부모 원소)를 타야한다.

즉, 백트래킹이 필요하다.

 

앞서 선언해주었던

pass_chk를 백트래킹 체크 변수로 사용하겠다.

 

한 자리 정수 당 2개의 정수를 스택에 넣어주었다.

만약 두 번 pop을 하여 값을 넣었는데

중복되는 수열이 생긴다면,

그 위의 가지 원소를 바꿔준다.

 

        if len(answer_list)>3:           
        
        # 중복 수열이 있는지 탐색(2개 ~ 길이/2)
            for rec in range(2, len(answer_list)//2+1):
                chk = 1
                for rep in range(1,rec+1):
                    if answer_list[-rep] != answer_list[-rep-rec]:
                        chk, pass_chk = 0, 0
                        break
                
                # 중복이 있는 경우, pop
                # 위의 가지를 패스할 경우까지 고려, pass_chk+1
                if chk:
                    answer_list.pop()
                    pass_chk += 1
                    break
			
            # 가지(부모 원소)가 잘못된 경우,
            # 가지(부모 원소)를 pop하고 카운트 초기화
            if pass_chk == 2:
                answer_list.pop()
                pass_chk = 0
                continue
            elif pass_chk > 0:
                continue

 

---

종합하여 작성하면

아래와 같다.

 

from sys import stdin

if __name__ == "__main__":
    N = int(stdin.readline())

    num_list, answer_list,pass_chk  = ['3','2','1'], [], 0

    while(len(num_list) != 0):
        num = num_list.pop()
        answer_list.append(num)
        if len(answer_list) > 1 and answer_list[-1] == answer_list[-2]:
            answer_list.pop()
            pass_chk += 1

            if pass_chk == 2:
                answer_list.pop()
                pass_chk = 0
                continue
            elif pass_chk > 0:
                continue

        if len(answer_list)>3:           
            for rec in range(2, len(answer_list)//2+1):
                chk = 1
                for rep in range(1,rec+1):
                    if answer_list[-rep] != answer_list[-rep-rec]:
                        chk, pass_chk = 0, 0
                        break
                
                if chk:
                    answer_list.pop()
                    pass_chk += 1
                    break

            if pass_chk == 2:
                answer_list.pop()
                pass_chk = 0
                continue
            elif pass_chk > 0:
                continue

        for next in ['3','2','1']:
            if next != num:
                num_list.append(next)

        if len(answer_list) == N:
            print(''.join(answer_list))
            break

 

코드의 효율이 좋지 않다고 느껴지지만,

바꾸니 계속 오류가 생겨 놓아주었다...

 

조금 더 고민해보고

개선할 부분을 개선해봐야겠다.

 

끝!