[BOJ] 15805 - 트리 나라 관광 가이드 (Python, JavaScript)

 

 

아이디어

 

차례로 도시를 방문하며 새로 방문하는 도시의 부모 도시를 이전 도시 번호로 저장한다.

 

 

풀이 #1 (Python)

 

루트 도시는 0번 도시가 아니라 첫 번째로 방문하는 도시이고, 루트 도시에는 -1을 저장한다.

 

def solution():
    N = int(input())
    numbers = tuple(map(int, input().split()))
    M = len(set(numbers))
    parents = [-1]*M
    for i in range(1, N-1):
        if parents[numbers[i]] == -1:
            parents[numbers[i]] = numbers[i-1]
    parents[numbers[0]] = -1
    print(M)
    print(' '.join(map(str, parents)))

solution()

 

 

 

풀이 #2 (JavaScript)

 

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

function solution() {
    const N = Number(input[0]);
    const numbers = input[1].split(' ').map(Number);
    const numbersSet = new Set(numbers);
    const M = numbersSet.size;
    let parents = Array(M).fill(-1);
    for (let i=1; i<N-1; i++) {
        if (parents[numbers[i]] === -1) parents[numbers[i]] = numbers[i-1];
    }
    parents[numbers[0]] = -1;
    console.log(M);
    console.log(parents.join(' '))
}

solution();