BOJ 4383 - 점프는 즐거워

문제

BOJ 4383 - 점프는 즐거워

N개의 정수 수열에서 인접한 두 원소의 차이(절댓값)가 1부터 N-1까지 모든 값을 정확히 한 번씩 포함하는지 확인하는 문제이다. 이 조건을 만족하면 "Jolly", 그렇지 않으면 "Not jolly"를 출력한다.

입력

각 줄에 수열의 크기 N과 N개의 정수가 주어진다. EOF까지 반복된다.

출력

각 줄에 대해 Jolly 또는 Not jolly를 출력한다.

예제

풀이

1부터 N-1까지의 숫자를 집합으로 만들고, 인접 원소 차이를 계산하며 해당 값을 집합에서 제거한다. 최종적으로 집합이 비어 있으면 Jolly이다.

1. 한 줄을 읽어 첫 번째 값을 N, 나머지를 수열 data로 저장한다.
2. 목표 집합 target = {1, 2, ..., N-1}을 초기화한다.
3. 인접 원소 쌍 (data[i], data[i+1])에 대해 diff = abs(data[i] - data[i+1])를 계산한다.
4. diff가 target에 없으면 즉시 "Not jolly"로 표시한다.
5. diff가 있으면 target에서 제거한다.
6. 순회 후 target이 비어 있으면 "Jolly", 아니면 "Not jolly"를 출력한다.
7. EOF에 도달하면 except로 종료한다.

핵심 아이디어: 집합을 이용하면 1~N-1 범위 포함 여부와 중복 제거를 O(1)에 처리할 수 있다.

코드

import sys
 
input = sys.stdin.readline
while 1:
    try:
        data = list(map(int, input().split()))
        target = set([i for i in range(1, data[0])])
        answer = "Jolly"
        for i in range(1, data[0]):
            diff = abs(data[i] - data[i + 1])
            if diff not in target:
                answer = "Not jolly"
            else:
                target.remove(diff)
        if len(target) > 0:
            answer = "Not jolly"
        print(answer)
    except:
        break

복잡도

• 시간: O(N) — 수열 길이 N에 대해 한 번 순회
• 공간: O(N) — 목표 집합 크기 N-1