백준 2872 우리집엔 도서관이 있어(그리디)

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

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

개인적으로 어려웠던 문제였다. 여러 케이스들을 직접 돌려보면서 규칙을 찾는데 애를 먹었다. 

여러번 시도 끝에 찾은 규칙은 list를 순차적으로 탐색하면서 std보다 작은 값은 무조껀 앞으로 빼줘야된다는 것이다.

 

ex)

3 1 4 2 5

std = 3

3보다 작은 수는 1,2인데 얘내는 무조껀 앞으로 빼줘야됨.

 

이런 규칙을 찾고 처음에 list,remove, list 이어붙이기 이런걸 썻지만 굳이 리스트를 만들지 않고

만들었다 치고 count만 계산하면 시간복잡도에 이득을 볼 것 같았다(핵심)

 

리스트의 값은 무조껀 1부터 N까지의 숫자이기 때문에 처음 std = 1로 잡아주고

std보다 큰 값을 만났을 때 계산을 해주면 되는데 std보다 +1 만큼 큰 수를 만났을 때는 이동을 안해도 되기 때문에

+1 만큼 큰 수를 std로 갱신하고 탐색을 이어가면 된다.

import sys
input = sys.stdin.readline

n = int(input())
data = []
for _ in range(n):
    data.append(int(input()))
res = 0
std = 1

for i in range(n):
    if data[i] > std:
        if data[i] == std+1:
            std = std+1
            continue
        res += data[i]-std
        std = data[i]
print(res)