(그리디) 백준 2872번 _ 우리집엔 도서관이 있어 [Python]

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

2872번: 우리집엔 도서관이 있어

백준 2872번 문제

 

 

내가 생각하는 그리디 알고리즘의 핵심 키워드는 "규칙"을 것이다.

 

이 문제는 책 배열 정리의 규칙을 찾는 것이 생각보다 어려워서 풀지 못했던 것 같다.

 

또한 책을 빼는 순서까지 고려했었는데 다시 생각해보니 순서는 고려할 필요가 없다.

 

중요한 것은 "몇 권의 책을 재배열해야 하냐"이고 순서는 어차피 정해져있기 때문에 재배열 해야 할 책의 권수가 곧 정답이 될 것이다.

 

두 가지 예시를 들어보면,

1) 2 4 1 3 5

책의 배열이 다음과 같은 경우, 

2 [4] 1 3 [5] 에서 [4], [5] 는 이미 오름차순으로 정리가 되어있기 때문에 2, 1, 3만 뽑으면 된다. 어차피 3, 2, 1 순서로 뽑을 것이기 때문에 정답은 책의 권수인 3이 될것이다.

 

2) 2 1 6 8 3 7 5 4 

다음과 같은 배열의 경우,

2 1 [6] 8 3 [7] 5 4 에서 [6], [7] 는 이미 오름차순으로 정리가 되어있기 때문에 6가지만 뽑으면 된다.

 

이를 토대로 알고리즘을 생각해보면

1) 전체 배열에서 가장 큰 수를 찾고

2) 전체 리스트의 길이 - 가장 큰 수로부터 왼쪽으로 내림차순에 있는 데이터의 개수

를 찾으면 정답이 될 것이다.

 

이를 코드로 구현해보면

N = int(input(""))
book_lst = []
for i in range(N):
    book_lst.append(int(input("")))

maxbook = max(book_lst)

idx = book_lst.index(maxbook)

answer = 0
for book in book_lst[:idx][::-1]:
    if book == maxbook - 1:
        answer += 1
        maxbook = book
if (len(book_lst[idx:])) > 1:
    print(len(book_lst)-(len(book_lst[idx:])-1)-(answer))
else:
    print(len(book_lst)-(len(book_lst[idx:]))-(answer))

하지만 이를 제출해보면 '틀렸습니다'가 나온다.

 

왜 틀렸을까?

 

우선 코드를 짜면서도 마지막에 if문을 한번 더 사용하는 것이 마음에 들지 않았는데 다시 처음부터 고민해봤다.

 

N = int(input(""))
book_lst = []
for i in range(N):
    book_lst.append(int(input("")))

maxbook = max(book_lst)

idx = book_lst.index(maxbook)
answer = len(book_lst)-idx-1
for book in book_lst[:idx][::-1]:
    if book == maxbook - 1:
        maxbook = book
    else:
        answer += 1
print(answer)

다시 짠 코드.

 

왠만한 테스트 케이스를 통과해서 정답일 줄 알았지만 결과는 "시간초과"

 

파이썬 시간초과는 input() 대신 sys.stdin.readline()을 사용하면 대다수의 경우 해결 할 수 있다는 얘기가 기억나 readline으로 바꿔서했더니 

맞았다 !!

 

readline()은 주피터 노트북에서 실행시 

ValueError: invalid literal for int() with base 10: ''

이런 오류가 나오는데 이는 주피터 노트북에서만 나타나는 오류로 코드 제출 시 정상적으로 작동한다.

(이 오류에 대해서는 추후에 따로 포스팅 하겠습니다.)

 

정답코드를 보면 

import sys
N = int(sys.stdin.readline())
book_lst = []
for i in range(N):
    book_lst.append(int(sys.stdin.readline()))

maxbook = max(book_lst)

idx = book_lst.index(maxbook)
answer = len(book_lst)-idx-1
for book in book_lst[:idx][::-1]:
    if book == maxbook - 1:
        maxbook = book
    else:
        answer += 1
print(answer)

이와 같다 !!

코드를 보면 제일 처음에 적었던 알고리즘인

"2) 전체 리스트의 길이 - 가장 큰 수로부터 왼쪽으로 내림차순에 있는 데이터의 개수" 가 아닌

그냥 제일 큰 데이터 기준 리스트의 오른쪽에 있는 원소 갯수를 answer의 초기값으로 설정 한 뒤 왼쪽으로 가면서 1차이의 내림차순이 아닐 경우에 answer에 1씩 더하는 로직으로 푼 것을 알 수 있다.

([1,3,5,2,4] 면 answer의 초기값은 2이고, 5->3일때 1더하고 3->1일때 1더해서 answer는 4가 출력된다.)

 

문제의 핵심은

1. 가장 큰 값 기준 배열의 좌측에 있는 값들은 가만히 냅두면 저절로 정렬 된다는 것과

2. 책을 뽑는 순서는 정해져있으므로 신경 쓸 필요가 없고 뽑아야되는 책의 권수만 생각하면 된다

이렇게 두 가지 였던 것 같다.