[python] 백준 4821. 페이지 세기

문제

https://www.acmicpc.net/problem/4821

 

워드, 한글, 메모장과 같은 워드 프로세서에서 인쇄를 할 때, 페이지 범위를 직접 입력하여 지정할 수 있다. 예를 들면, 다음과 같이 입력할 수 있다.

10-15,25-28,8-4,13-20,9,8-8

사용자는 위처럼 인쇄하고자 하는 범위를 콤마로 구분하여 입력할 수 있다.

각 인쇄 범위는 양의 정수 하나 또는 하이픈(-)로 구분된 두 양의 정수이다. 수 두 개로 이루어진 범위에서 앞의 수를 low, 뒤의 수를 high라고 한다. 만약, low > high인 경우에는 이 범위는 인쇄하지 않는다. 또, 인쇄 범위가 문서의 범위를 넘어가는 경우에는 출력할 수 있는 페이지만 출력한다. 페이지 번호는 1부터 시작한다.

인쇄 범위는 겹칠 수 있다. 겹치는 페이지는 여러 번 인쇄하는 것이 아니고, 한 번만 인쇄해야 한다. (위의 예제에서 13, 14, 15는 두 범위에 포함된다)

인쇄 범위가 주어졌을 때, 출력해야 하는 페이지의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 문서의 총 페이지 수가 주어진다. 둘째 줄에는 인쇄 범위가 문제 설명에 나온 형식과 같이 주어진다. 입력의 마지막에는 0이 하나 주어진다. 문서는 많아야 1000페이지이고, 인쇄 범위의 길이는 1000글자를 넘지 않는다.

출력

각 테스트 케이스에 대해서, 출력해야 하는 페이지의 수를 출력한다.

---

풀이

이 문제는 나중에 좀 알아보고 풀 수 있었는데 그 이유가 바로 split() 를 잘 사용하지 못해서 였다. split를 통해 ','와 '-'를 분리할 수 있었는데 그걸 알지 못했달까... 외에는 자잘한 코드 자체에 실수가 있었다. 그건 이제 차차 뒤에 설명을 하도록 하고 먼저 풀이 코드를 올려보자면...

 

import sys

while True:
    n = int(sys.stdin.readline().strip())
    if n == 0:
        break
    else:
        data = sys.stdin.readline().rstrip().split(',')
        printed_page = [0]*(n+1)
        pages = 0

        for page_num in data:
            if '-' in page_num:
                low, high = map(int, page_num.split('-'))
                if high > n:
                    high = n
                if low <= high:
                    for i in range(low, high+1):
                        if printed_page[i] == 0:
                            printed_page[i] += 1
                elif low>high:
                    continue
            else:
                one_page = int(page_num)
                if one_page <= n:
                    if printed_page[one_page] == 0:
                        printed_page[one_page] += 1

    for i in range(1, n+1):
        pages += printed_page[i]
    sys.stdout.write(str(pages)+"\n")

 

1. 0이 나올때까지 반복하는 것이므로, While문 True를 이용해 먼저 시작을 한다.

2. 이후에는 ,를 기준으로 나눈 내용들을 data에 저장을 해두고,

3. 중복 확인과 인쇄되는 페이지 수를 세기 위한 printed_page 배열도 선언을 해준다. 이때, 페이지 시작은 1부터 시작이므로, 배열의 크기는 (n+1)로 선언을 해준다.

4. 이후에는 들어온 data 배열에서 각각의 값(page_num)들을 비교해서 printed_page 배열에 영향을 준다.

• '-'가 page_num에 있을 경우
  • low, high로 값을 나눠서 받은 다음 (10-15라면, low = 10, high = 15)
  • high가 n보다 클 경우, n으로 바꿔준다.
  • low가 high보다 작거나 같을 경우, 반복문을 통해서 low부터 high까지 해당하는 printed_page의 값이 0일 경우 1을 더해준다. 만약 printed_page의 값이 1일 경우에는 이미 인쇄를 하기로 결정된 즉, 중복이 되므로 넘어간다.
• '-'가 page_num에 없을 경우 (즉 하나의 페이지 값만 들어왔을 경우. (ex: 9))
  • n보다 작거나 같다면 이 역시도 중복 여부를 확인하고 중복이 없다면 1을 더해주도록 하였다.
• 마지막으로, 그렇게 모든 과정을 거친 printed_page 배열의 값들 (1페이지 부터 n+1페이지까지)을 pages라는 변수에 저장하고 이후에 이를 출력하는 방식으로 코드를 작성하였다. 
  •  

---

시행 착오

이 문제를 풀면서 어려웠던 점은... 내가 split에 대해 잘 모른다는 점과 신경써야할 조건들이 많아 사소한 실수들이 잦았다는 점이었다. 

 

1. split()

data = sys.stdin.readline().rstrip().split(',')
low, high = map(int, page_num.split('-'))

항상 사용하던 split 코드가 ()에서 끝났기 때문에, 이 용도로만 사용이 가능한 줄 알았으나... 알고보니 그냥 () 이것일 때는 공백, 외에 다른 것이 들어간다면 그걸 기준으로 나눠주는 것이었다. 앞으로 관련으로 문제가 나온다면 헷갈리지 않고 바로 이 방법을 떠올릴 수 있었음 좋겠다.

 

2. 사소한 실수

조건이 많았다는 말 처럼... page 출력 관련으로 오류가 자꾸 떠서...스트레스를 받았었다. 그만큼 좀 범위 조절과 관련으로 예민하게 풀었어야 했던 것 같다.

 

내가 문제가 됐던 것은,

• 페이지 범위 조절(0 페이지는 포함이 되면 안된다)
• 하나의 페이지만 들어왔을때, n보다 크다면 그냥 출력이 되면 안된다. 
  • 그치만.. 나는 ㅎㅎ 사실 그냥 n으로 바꿔버리는 이상한 코드를 짰던 것이다.

해결한 방법은 질문게시판에서 다른 질문들을 참고해서 사람들이 문제였던 반례들을 사용해보는 것! 확실히 사람은 다 비슷하다고 다 비슷하게 틀렸더라.. 그래서 결과적으로는 반례를 통해서 무사히 문제를 해결할 수 있었다.

 

그렇지만... 문제 해결은 문제 해결이고... 이거 시간 복잡도가 너무 오래 걸렸다. 아무래도 다른 사람들의 코드들을 살펴보니 확실히 내 코드가 복잡한 것 같다는 생각을 했다. 개선해야할 부분이 많이 보인다.

 

성공!!