BOJ 1280 - 나무 심기

문제

BOJ 1280 - 나무 심기

여러 테스트 케이스가 주어지며, 각 케이스에서 N명의 이름과 2N-1개의 값이 주어진다. 값들 중 짝이 없는 유일한 값을 찾아 해당 인덱스의 이름을 출력하라.

입력

각 테스트 케이스마다 N, N개의 이름, 2N-1개의 값이 주어진다. N이 0이면 입력 종료.

출력

각 테스트 케이스의 케이스 번호와 짝이 없는 값에 해당하는 이름을 출력한다.

예제

풀이

2N-1개의 값을 정렬하여 인접한 쌍을 비교하면, 짝이 없는 유일한 값을 찾을 수 있다.

1. N명의 이름과 2N-1개의 값을 입력받는다
2. 값을 정렬한 뒤, 인덱스 0, 2, 4, ... 순서로 인접한 값을 비교한다
3. 인접한 값이 다르거나 마지막 원소이면 짝이 없는 값이다
4. 해당 값을 인덱스로 하여 names 배열에서 이름을 출력한다

핵심 아이디어: 정렬 후 2개씩 묶으면, 짝이 없는 원소는 인접한 값과 다르므로 O(N log N)에 식별 가능하다.

코드

n = 1
result = []
 
while n:
    n = int(input())
    names = [input() for i in range(n)]
    values = []
 
    for i in range(2 * n - 1):
        a = int(input().split()[0])
        values.append(a)
 
    values.sort()
    for i in range(0, len(values), 2):
        if i == (len(values) - 1) or values[i] != values[i + 1]:
            result.append(names[values[i] - 1])
            break
 
for i in range(len(result)):
    print(i + 1, result[i])

복잡도

• 시간: O(N log N)
• 공간: O(N)