[Python] 백준 2782번 - 우리집엔 도서관이 있어

1. 문제정보

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

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

 

 

2. 해결전략

리스트의 원소가 있을 때 적절한 수를 선택하여 최 상단으로 올리면서 몇 번만의 정렬시킬 수 있는지 묻고있다. 이런 경우에 실제 정렬을 수행하면서 결과를 구하려고 할텐데.. 이러한 방식으로는 정답을 구하기 어렵다. 이중 포문을 돌면서 결과값을 구할 수 있겠지만 n이 30만이기 때문에 30만 * 30만의 연산을 수행하면 시간 초과가 나올 것이 뻔하다.

 

 이 문제는 최소한의 조건만 찾는다면 나머지는 알아서 결과가 구해지는 문제이다. 여기서 최소한의 조건은 현재 리스트에서 최대 값을 기준으로 좌측의 원소가 몇개나 정렬 되었는지 찾는 것이다. 1~10중에서 3개가 잘 정렬된 상태(8..9..10..)라면 나머지 7개는 잘 선택해서 정렬하면 되기 때문이다.

 

3. 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))

# 가장 큰 값을 찾은 후 정렬된 갯수를 구함
maxValue = max(arr) 
maxIndex = arr.index(maxValue)
sortCnt = 1
for i in range(maxIndex-1, -1, -1):
    if arr[i] == maxValue-sortCnt:
        sortCnt += 1

# 정렬된 갯수를 뺸 나머지를 '알아서' 뽑아서 정렬함
print(n - sortCnt)