K. Milking Order

- iknoom1107

문제 설명

정해진 규칙으로 우유를 마실 때 1번 소가 가장 빨리 마실 수 있는 순서를 정해야 합니다.

규칙은 다음과 같습니다.

1. M마리의 소의 순서는 분명하게 지켜져야 한다.

2. K마리의 소의 위치는 정해져있다.

예를 들어 [예제입력 1]에서는 K마리의 위치는 정해져 있으므로

3 X 5 X X X 에서 4 -> 5 -> 6 의 순서를 지키면

3 4 5 1 2 6 / 3 4 5 1 6 2 / 3 4 5 2 1 6 / 3 4 5 2 6 1 / 3 4 5 6 1 2 / 3 4 5 6 2 1

이 올바른 순서가 될 수 있겠죠.

문제 풀이

(case 1) cow 1이 K마리에 포함될 경우

- 이미 정해져 있으므로 cow1의 위치를 출력하면 됩니다.

(case 2) cow 1이 M마리에 포함되지 않을 경우

- cow1의 자리를 가장 앞으로 확보하기 위해서 M마리를 가능한 가장 뒤로 보냅니다.

그러고나서 cow1의 자리를 확보하면 됩니다.

(case 3) cow 1이 M마리에 포함될 경우

- cow1의 자리를 가장 앞으로 확보하기 위해서 M마리를 가장 앞으로 보내면 됩니다.

소스코드

<Python>

N, M, K = map(int, input().split())
stack = list(map(int, input().split()))
A = [0] * N
for _ in range(K):
    a, b = map(int, input().split())
    A[b - 1] = a

if 1 in A:
    print(A.index(1) + 1)

elif 1 in stack:
    stack.reverse()
    i = 0
    while stack:
        k = stack.pop()
        if k in A:
            while k != A[i]: i += 1
        else:
            while A[i]: i += 1
        A[i] = k
        i += 1
    print(A.index(1) + 1)

else:
    i = N - 1
    while stack:
        k = stack.pop()
        if k in A:
            while k != A[i]: i -= 1
        else:
            while A[i]: i -= 1
        A[i] = k
        i -= 1
    print(A.index(0) + 1)