[Greedy] 16288번 - Passport Control (11일차)

#실행시간 단축을 위한 sys 모듈 import
import sys
input = sys.stdin.readline
#사람 수 n과 창구 수 k를 입력받음
n,k = map(int, input().split())
#빠져나온 사람의 순서를 입력받아 리스트로 만듦
ex = list(map(int, input().split()))
#k개 만큼의 창구를 리스트로 생성(해당 창구를 이용하는 사람을 저장하기 위한 큐(FIFO))
gate = [0]*k

#빠져나온 순서대로 큐에 넣으면서 최초에 창구를 이용할때 들어갔던 순서를 파악
for i in range(n):
    #i번째로 나온 사람이 큐에 들어갈 수 있는지를 검사하는 변수 (0 = X, 1 = O)
    temp = 0
    #모든 큐에 대해 i번째로 나온 사람이 들어갈 큐가 있는지 검사
    for j in range(k):
        #해당 큐에 있는 사람 뒤에 i번째로 나온 사람이 올 수 있는 경우
        if(gate[j] < ex[i]):
            #해당 큐에 있던 사람을 큐에서 빼고, i번째로 나온 사람으로 업데이트
            gate[j] = ex[i]
            #i번째로 나온 사람이 큐에 들어갈 수 있으므로 1로 변경
            temp = 1
            #이미 큐에 들어갔으므로 더이상 탐색은 무의미, for(j) 반복문 종료
            break
    #모든 큐에 대해 검사를 했지만, 큐의 값이 업데이트가 안되는 경우,
    if(temp == 0):
        #해당 i번째로 나오는 사람이 해당 순서로 나올 방법이 없다는 뜻이기에 for(i) 반복문 종료
        break
#28줄이 실행된 경우, 정상적 방법으로 제 순서에 나올 수 없는 사람이 존재하므로
if(temp == 0):
    #불가능한 순서에 대해 NO를 출력
    print('NO')
#28줄이 실행되지 않은 경우, 모든 사람들이 제 순서에 나올 수 있으므로
else:
    #해당 순서에 대해 YES를 출력
    print('YES')

#인사이트
#모든 순서를 리스트 안에 담으려하지 않고 최신값으로 업데이트하면 적은 리스트 요소로도 연산이 가능
#큐 = FIFO. 먼저 들어간 사람이 먼저 나오므로 필연적으로 증가하는 수열의 형태
#따라서 먼저 들어간 사람의 순번 < 나중에 들어간 사람의 순번이어야 한다
#input과 output에 대해 순서가 정해져 있는 경우에는 FIFO 큐나 LIFO 스택을 고려하자