스택으로 쌓아놓은 수열에서 조건을 만족하는 값들이 언제부터 다 나오는가?

17162번: 가희의 수열놀이 (Small)

 

여러개의 쿼리가 주어지는데,

 

1. 스택의 맨 뒤에 숫자를 추가

 

2. 스택이 비어있지 않으면 맨 뒤의 원소를 제거

 

3. 맨 뒤에서부터 최소 몇개의 수를 선택해야, 이들을 mod로 나누었을때 0,1,2,..,mod-1이 최소 1개 이상 나타나는가?

 

예를 들어 [2,3]인 경우 4로 나누면 나머지는 [2,3]인데, 여기서 0,1이 없으므로 -1

 

[2,3,1,4]인 경우 4로 나누면 나머지는 [2,3,1,0]인데 여기서 0,1,2,3이 모두 나왔으므로 4

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

스택에 숫자를 쌓아나가는데, 핵심은 mod로 나눈 나머지를 쌓아나가고

 

0,1,2,..,mod-1이 각각 언제 마지막으로 나오는지 인덱스를 저장해둔다

 

그러면 이 인덱스들의 최솟값을 이용하면 O(mod)만에 3번 쿼리의 정답을 찾을 수 있다

 

[0,1,2,3,2,1,0,3,1,3,2,1,3] 이렇게 되었을때 mod = 4이면

 

0은 마지막에 나온 인덱스가 6번

 

1은 마지막에 나온 인덱스가 11번

 

2는 마지막에 나온 인덱스가 10번

 

3은 마지막에 나온 인덱스가 12번

 

따라서 뒤에서부터 인덱스 6번까지 원소를 선택해야 0,1,2,3이 모두 1번씩 나오게된다

 

이렇게 하면 1번 쿼리는 O(1)에 넣기만 하면 되는데 0,1,2,..,mod-1값이 어느 인덱스에 나오는지

 

나올때마다 인덱스를 저장해두면 배열은 마지막 인덱스값을 가지게 된다

 

from sys import stdin

q,mod = map(int,stdin.readline().split())

A = []

visited = [-1]*mod

for _ in range(q):
    
    Q = stdin.readline().rstrip().split()

    if Q[0] == '1':
        
        m = int(Q[1]) % mod
        A.append(m)
        visited[m] = len(A)-1

 

2번 쿼리는 원소를 제거하면, 스택을 뒤에서부터 순회해서 제거된 원소가 처음으로 나온 위치를 찾고

 

마지막으로 나오는 인덱스 위치를 그것으로 갱신하면 된다

 

mod = 100까지이므로, 그냥 순회해도 괜찮다

 

    elif Q[0] == '2':
        
        if len(A) == 0:
            
            continue
            
        x = A.pop()
        
        find = False

        for i in range(len(A)-1,-1,-1):
            
            if A[i] == x:
                
                visited[x] = i
                find = True
                break
        
        if find == False:
            
            visited[x] = -1

 

3번 쿼리는 마지막으로 나온 인덱스 위치들의 최솟값을 찾으면

 

맨 뒤에서부터 거기까지 개수를 세는건 쉽다

 

그러면 최대 2*10^7에 문제를 해결할 수 있다

 

    else:
        
        i = min(visited)
        
        if i == -1:
            
            print(-1)
        
        else:
            
            print(len(A) - i)

 

 

 

1번 쿼리를 처리할 때 마지막에 나오는 위치를 저장하기 위해 visited의 원소를 배열로 저장해두는 것도 괜찮을듯?

 

visited[0] = []

visited[1] = []

...

 

visited[mod-1] = []

 

이렇게 해두고 매 원소를 저장할때마다 인덱스를 append해두면 마지막 위치에는 마지막에 저장된 위치가 저장

 

그러면 2번 쿼리를 O(1)에 처리할 수 있을 것

 

from sys import stdin

q,mod = map(int,stdin.readline().split())

A = []

visited = [[] for _ in range(mod)]

for _ in range(q):
    
    Q = stdin.readline().rstrip().split()

    if Q[0] == '1':
        
        m = int(Q[1]) % mod
        A.append(m)
        visited[m].append(len(A)-1)
        
    elif Q[0] == '2':
        
        if len(A) == 0:
            
            continue
            
        x = A.pop()
        
        visited[x].pop()

    else:
        
        no = False
        j = len(A)+10
        
        for i in range(mod):
            
            if len(visited[i]) == 0:
                
                no = True
                break
            
            else:
                
                if j > visited[i][-1]:
                    
                    j = visited[i][-1]
                    
        if no:
            
            print(-1)
        
        else:
            
            print(len(A) - j)