(Python) - BOJ(10975번) : 데크 소트 2

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

10975번: 데크 소트 2

---

• 문제 : 

데크는 큐와 비슷하지만, 앞과 뒤 양쪽에서 자료를 넣거나 뺄 수 있는 자료구조이다.

N개의 수가 주어졌을 때, 첫 번째 수부터 마지막 수까지 순서대로 아래 세 가지 중에 한 방법을 이용해 데크에 넣어야 한다.

1. 수를 존재하는 데크중 하나의 맨 앞에 넣는다.
2. 수를 존재하는 데크중 하나의 맨 뒤에 넣는다.
3. 새로운 데크를 만들어서 그 곳에 수를 넣는다.

위의 방법을 이용해서 모든 수를 적절히 데크에 넣은 다음, 모든 데크를 적절히 이어 붙여 오름차순으로 만들려고 한다. 이때, 필요한 데크 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

덱에 넣으려는 숫자들의 배열을 nums로 저장하고 이를 오름차순으로 정렬한 배열을 sortedNums로 저장했다.

nums의 첫 번째 숫자부터 탐색을 시작하며 sortedNums의 어떤 위치(인덱스)에 있는지 찾는다.

찾은 인덱스를 통해 덱을 새로 만들어야 할지 기존의 덱을 사용해도 될 지 판단하는데 만약

정렬된 배열에서 첫 번째거나 마지막일 경우, 인접한 수가 이미 정렬되지 않았다면 그 값을 정렬하기 위해 새로운 덱이 필요하게 된다. 따라서 answer를 카운트 해주었다.

 

또한, 만약 인덱스가 0과 N-1이 아닌 중간값일 경우 양 옆 인덱스들 중 하나라도 이미 정렬되었다면 그 값이 들어있는 덱에 현재 값을 넣으면 되므로 새로운 덱은 필요하지 않다.

만약 양 옆의 값이 모두 정렬되지 않았다면 당연히 그 두 값을 넣기 위해선 새로운 덱이 필요하다.

 

 

 

 

---

• 소스코드 : 

N = int(input())
nums = [int(input()) for _ in range(N)]
sortedNums = sorted(nums)
answer = 0
if N == 1:
    print(1)
    exit()
for i in range(N):
    for j in range(N):
        if nums[i] == sortedNums[j]:
            sortedNums[j] = 10000
            break
    if j==0:
        if sortedNums[j+1] != 10000:
            answer += 1
    elif j==N-1:
        if sortedNums[j-1] != 10000:
            answer += 1
    elif sortedNums[j-1] == 10000 or sortedNums[j+1]== 10000:
        continue
    else:
        answer += 1
print(answer)