https://school.programmers.co.kr/learn/courses/30/lessons/131704

---

1. 코드

from collections import deque


def solution(order):
    answer = 0
    length = len(order)

    sub = deque([])
    main = deque(range(1, length + 1))
    empty = False  # main 이 비어있을 경우 FLAG

    for i in range(len(order)):
        target = order[i]

        if not main:
            empty = True
            break

        while main[0] < target:
            sub.appendleft(main.popleft())

        if main[0] == target:
            answer += 1
            main.popleft()
        elif sub[0] == target:
            answer += 1
            sub.popleft()
        elif main[0] != target and sub[0] != target:
            break

    if empty:
        while sub:
            if order[i] == sub.popleft():
                i += 1
                answer += 1
            else:
                break

    return answer

---

2. 후기

1 ≤ order의 길이 ≤ 1,000,000 조건을 봤다면 O(nlogn)은 사용할 수 없고 O(n)으로 풀어야겠다는 생각을 해야한다.