BOJ (2827) - 우리집엔 도서관이 있어 Python

아이디어

1. 모든책을 현재 순서대로 bks 리스트에 입력받음
2. bks 리스트에서 제일 큰 수 찾음 = _max
3. _max의 위치를 기준으로 up과 down으로 리스트를 나눔
4. up에 있는지 확인, 만약 있으면 
5. _max의 위치를 기준으로 다음 큰 수가 up 에 없으면 down에서 찾고 count
6. 반복

3(up)

9(up)

7(up)

10(기준)

6(down)

4(down)

5(down)

1(down)

2(down)

8(down)

소스코드1

#https://www.acmicpc.net/problem/2872
#input
import sys
N = int(sys.stdin.readline())
bks = []
_max = 0
cnt = 0
for _ in range(N):
    item = int(sys.stdin.readline())
    bks.append(item)
    if _max < item:
        _max = item
        _max_index = cnt
    cnt += 1
#algorithm
up = bks[:_max_index]
down = bks[_max_index+1:]
if len(up) > 0 and len(down) >0:
    _max = max(up)
    cnt = len(up)
else:
    cnt = 0
while len(down) > 0:
    if not _max-1 in down:
        _max -= 1
    else:
        down.remove(_max-1)
        _max = _max-1
        cnt+=1
    
#print
print(cnt)

 

하지만 시간초과 발생

 

소스코드2

#https://www.acmicpc.net/problem/2872
import sys
N = int(sys.stdin.readline())
bks = []
cnt = 0
for _ in range(N):
    bks.append(int(sys.stdin.readline()))

_max = bks[0]

for i in range(1,N):
    if _max < bks[i]:
        if _max+1 != bks[i]:
            cnt+=1
        _max = bks[i]
    else:
        cnt+=1

print(cnt)

 

문제 없음