백준 온라인 저지, 자료구조 / 17162번: 가희의수열놀이 (파이썬 / , 백준 골드문제)

문제

chogahui는 수열 arr을 이용해 나머지 놀이를 하고 있습니다. 조가희는 수열에 다음과 같은 연산을 할 수 있습니다.

• 수열 arr의 맨 뒤에 num을 추가합니다.
• 수열 arr의 맨 뒤에 있는 원소를 제거합니다.

chogahui가 물어보는 질문은 다음과 같습니다.

• 수열 arr의 맨 뒤에서부터 최소 몇 개의 수를 선택해야, 이들을 mod로 나누었을 때 나머지가 0, ... , mod-1인 경우가 최소 한 번 이상 나타나는가?

chogahui의 질문을 해결해 주세요.

입력

첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 2×10⁵, 1 ≤ mod ≤ 10²)

이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어집니다. 이는 맨 앞에 오는 정수의 값 (1, 2, 3)에 따라 구분됩니다.

• 1 num : 수열 arr의 맨 뒤에 num을 추가한다. (1 ≤ num ≤ 2³¹-1)
• 2 : 수열 arr의 맨 뒤에 있는 원소를 제거한다. 만약 arr이 비어있으면 무시한다.
• 3 : chogahui가 요구하는 쿼리에 대한 값을 계산한다.

처음에 수열 arr은 비어 있습니다.

출력

chogahui가 요구한 쿼리에 대한 값을 3번 쿼리가 들어올 때마다 출력합니다. 3번 쿼리는 입력에 1개 이상 존재합니다. 3번 쿼리에 대한 답이 존재하지 않는 경우에는 -1을 출력한다.

제한

예제 입력 1

6 4
1 2
1 3
3
1 1
1 4
3

예제 출력 1

-1
4

노트

 첫 번째 3번 쿼리가 들어왔을 때, 수열 arr은 다음과 같습니다.

 3을 4로 나눈 나머지는 3, 2를 4로 나눈 나머지는 2입니다. 수열의 모든 원소를 선택해도, 4로 나눈 나머지가 0인 경우, 1인 경우는 존재하지 않으므로 -1을 출력합니다.

 

 2번째 3번 쿼리가 들어온 경우입니다. 위에서부터 4개를 선택했을 때, 4를 4로 나눈 나머지는 0, 1을 4으로 나눈 나머지는 1, 3을 4로 나눈 나머지는 3, 2를 4로 나눈 나머지는 2입니다. 나머지가 0, 1, 2, 3인 경우가 최소 하나 이상 존재합니다. 그리고 이 값이 조가희가 요구하는 값임을 알 수 있습니다. 따라서 4를 출력합니다.

접근 방법

- 1이 나올 경우 주어진 값을 하나씩 stack에 저장한 뒤, 리스트를 하나 만들어 mod로 나눌 때의 나머지에 해당하는 인덱스의 값에 몇 번째에 추가됐는 지를 추가한다.
- 2가 나올 경우 스택에서 값을 빼내어 해당 인덱스에 해당하는 값을 하나 뺀다.
- 3이 나올 경우 나머지 리스트의 값을 모두 확인한 뒤, 비어있는 리스트가 있다면 0, 없다면 현재 stack의 길이와 각 인덱스에 해당하는 리스트의 마지막 값 중 가장 작은 값을 빼내어 이를 출력한다.

코드

# acmicpc.net/problem/17162
# 접근 방법
# 1이 나올 경우 주어진 값을 하나씩 stack에 저장한 뒤, 리스트를 하나 만들어 mod로 나눌 때의 나머지에 해당하는 인덱스의 값에 몇 번째에 추가됐는 지를 추가한다.
# 2가 나올 경우 스택에서 값을 빼내어 해당 인덱스에 해당하는 값을 하나 뺀다.
# 3이 나올 경우 나머지 리스트의 값을 모두 확인한 뒤, 비어있는 리스트가 있다면 0, 없다면 현재 stack의 길이와 각 인덱스에 해당하는 리스트의 마지막 값 중 가장 작은 값을 빼내어 이를 출력한다.
import sys
input = sys.stdin.readline
q, mod = map(int, input().split())
arr = []
dp = [[] for _ in range(mod)]
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        dp[query[1]%mod].append(len(arr))
        arr.append(query[1]%mod)
    elif query[0] == 2:
        if arr:
            x = arr.pop()
            dp[x].pop()
    else:
        min_count = len(arr)
        check = True
        for x in dp:
            if not x:
                print(-1)
                check = False
                break
            min_count = min(x[-1], min_count)
        if check:
            print(len(arr) - min_count)