데크 소트 2

• 데크 소트의 쉬운 버전. n의 값이 줄어든 것도 있지만, 중복된 숫자가 없다는 조건때문에 풀이가 매우 쉬워진다.
• 간단한 풀이는 실제로 데크 소트를 하는 과정을 시뮬레이션해보는 것이다. 먼저 각 숫자들이 정렬되었을때 순서가 몇번째에 오게되는지를 계산해놓는다. 앞에서부터 숫자를 읽으면서, 현재 숫자의 순서와 인접한 순서의 숫자가 들어있는 데크가 있다면 그 데크에 현재 숫자를 붙이고, 그런 데크가 없다면 현재 숫자를 포함한 새 데크를 만든다. 다 끝난 다음에 데크가 몇개나 만들어졌는지 확인하면 된다.
• 이 방법은 우선 정렬하는데에 O(nlogn)이 걸린다. 그리고, 각 숫자들에 대해서, 인접한 순서의 숫자가 끝에 있는 데크가 있는지를 확인해야 하는데, 데크가 최대 O(n)개 존재할수 있으므로, 일일히 비교해서 찾으려면 각 숫자마다 O(n), 총 O(n^2) 이 걸린다.
• 데크의 양 끝에 해당되는 숫자들을 따로 저장해두면, 인접한 순서의 숫자가 끝에 있는 데크가 있는지를 확인하는 것을 O(1)에 처리할수 있다, 갱신하는 것도 역시 O(1). 따라서 O(n^2)의 작업을 O(n)으로 줄일수 있고, 그러면 총 시간복잡도는 정렬 부분에서 제일 오래 걸리게 되어 O(nlogn)이 된다.

"""Solution code for "BOJ 10975. 데크 소트 2".

- Problem link: https://www.acmicpc.net/problem/10975
- Solution link: http://www.teferi.net/ps/problems/boj/10975
"""


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]

    order_by_num = {num: i for i, num in enumerate(sorted(set(nums)))}
    can_add = [False] * N
    answer = 0
    for num in nums:
        order = order_by_num[num]
        if not can_add[order]:
            answer += 1
        if order > 0:
            can_add[order - 1] = True
        if order < N - 1:
            can_add[order + 1] = True

    print(answer)


if __name__ == '__main__':
    main()