[BOJ] 2661 - 좋은수열 (Python, JavaScript)

 

 

아이디어

 

백트래킹으로 가장 작은 수의 좋은 수열을 찾는다.

 

 

풀이 #1 (Python)

 

좋은 수열 중 가장 작은 수는 1로 시작하게 되므로 리스트 stack에 길이 1과 문자열 1을 튜플로 저장한다.

 

while문에서 DFS로 문자열 길이 l과 문자열 s를 꺼내 슬라이싱으로 인접한 두 부분 수열 중 같은 쌍을 찾는다.

같은 쌍이 존재하면 break로 다음 값을 꺼내고, 그렇지 않으면 길이가 N인지 비교하고 N이면 출력 후 종료한다.

N이 아니면 stack에 다음 길이와 문자열을 추가하는데, stack은 마지막 값부터 꺼내므로 숫자가 큰 순서대로 넣는다.

 

가장 먼저 찾은 좋은 수열이 가장 작은 수의 좋은 수열이므로 좋은 수열을 찾으면 결과값 출력 후 while문을 종료한다.

 

N = int(input())
stack = [(1, '1')]
while stack:
    l, s = stack.pop()
    for i in range(l//2):
        if s[l-i-1:] == s[l-(i+1)*2:l-i-1]:
            break
    else:
        if l >= N:
            print(s)
            break
        stack.append((l+1, s+'3'))
        stack.append((l+1, s+'2'))
        stack.append((l+1, s+'1'))

 

 

함수를 사용하여 구현할 수도 있으나, 결과값을 찾았는지 여부를 확인하기 위해 변수 res를 사용한다.

def dfs(l, s):
    global res
    if res:
        return
    for i in range(l//2):
        if s[l-i-1:] == s[l-(i+1)*2:l-i-1]:
            return
    if l >= N:
        res = s
        return
    dfs(l+1, s+'1')
    dfs(l+1, s+'2')
    dfs(l+1, s+'3')

N = int(input())
res = ''
dfs(1, '1')
print(res)

 

exit 메서드를 사용하여 결과값 출력 후 바로 종료하는 코드가 더 빠를 것이라고 예상했으나 의외로 조금 더 느렸다.

# 더 느린 코드
def dfs(l, s):
    for i in range(l//2):
        if s[l-i-1:] == s[l-(i+1)*2:l-i-1]:
            return
    if l >= N:
        print(s)
        exit()
    dfs(l+1, s+'1')
    dfs(l+1, s+'2')
    dfs(l+1, s+'3')

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

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 같은 방식으로 동작한다.

자바스크립트에는 for else문이 없어 flag 변수로 break문으로 for문이 종료되었는지 여부를 판단한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = Number(input[0]);
let stack = [[1, '1']];
while (stack.length > 0) {
    let [l, s] = stack.pop();
    let flag = true;
    for (let i=0; i<parseInt(l/2); i++) {
        if (s.substring(l-i-1, l) === s.substring(l-(i+1)*2, l-i-1)) {
            flag = false;
            break;
        }
    }
    if (flag) {
        if (l >= N) {
            console.log(s);
            break;
        }
        stack.push([l+1, s+'3']);
        stack.push([l+1, s+'2']);
        stack.push([l+1, s+'1']);
    }
}

 

 

함수를 사용하는 코드는 while문을 사용하는 코드보다 메모리를 조금 더 적게 사용하지만 더 느렸다.

// 메모리를 더 적게 사용하나 더 느린 코드
function dfs(l, s) {
    if (res) return;
    for (let i=0; i<parseInt(l/2); i++) {
        if (s.substring(l-i-1, l) === s.substring(l-(i+1)*2, l-i-1)) return;
    }
    if (l >= N) {
        res = s;
        return;
    }
    dfs(l+1, s+'1')
    dfs(l+1, s+'2')
    dfs(l+1, s+'3')
}

const N = Number(input[0]);
let res = 0;
dfs(1, '1');
console.log(res);