BOJ 4821 - 페이지 세기

문제

BOJ 4821 - 페이지 세기

총 페이지 수와 인쇄 범위 목록이 주어질 때, 실제로 인쇄되는 고유 페이지 수를 구하는 문제다. 인쇄 범위는 단일 페이지(n) 또는 범위(n-m) 형식이며, 총 페이지를 초과하는 경우 무시한다.

입력

• 여러 테스트 케이스 (총 페이지 수가 0이면 종료)
• 첫 줄: 총 페이지 수
• 둘째 줄: 쉼표로 구분된 인쇄 범위 목록 (예: 1-5,3,7-9)

출력

• 각 테스트 케이스에 대해 실제 인쇄되는 고유 페이지 수 출력

예제

풀이

인쇄 범위를 파싱하여 각 페이지의 인쇄 횟수를 배열로 관리하고, 1회 이상 인쇄된 페이지를 세는 구현 문제다.

1. 총 페이지 수가 0이면 종료한다.
2. print_page_count 배열을 크기 total_page + 1로 초기화한다.
3. 인쇄 범위 문자열을 쉼표로 분리한다.
4. -가 포함된 범위는 low~high로 분리하여 해당 범위의 모든 페이지 카운트를 증가시킨다. 총 페이지 초과는 무시한다.
5. 단일 페이지도 동일하게 카운트를 증가시킨다.
6. 카운트가 1 이상인 페이지 수를 합산하여 출력한다.

핵심 아이디어: 동일 페이지가 여러 범위에 포함될 수 있으므로 카운트 배열을 사용해 중복을 처리한다. 최종적으로 1 이상인 카운트를 세면 고유 페이지 수를 구할 수 있다.

코드

import sys
 
while True:
    total_page = int(sys.stdin.readline())
 
    if total_page == 0:
        break
 
    print_page_count = [0] * (total_page + 1)
    print_range_list = sys.stdin.readline().rstrip().split(",")
 
    for print_range in print_range_list:
 
        if "-" in print_range:
            low, high = map(int, print_range.split("-"))
 
            for i in range(low, high + 1):
 
                if i <= total_page:
                    print_page_count[i] += 1
 
            continue
 
        page = int(print_range)
 
        if page <= total_page:
            print_page_count[page] += 1
 
    print(sum([1 if 1 <= i else 0 for i in print_page_count]))

복잡도

• 시간: O(P + R) — P는 총 페이지 수, R은 인쇄 범위의 총 합산 크기
• 공간: O(P) — 페이지 카운트 배열 크기