[알고 스터디] 1. 스택(Stack) - 17162

가희의 수열놀이 (samll) - 골4

문제

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

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

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

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

입력

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

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

• 1 num : 수열 arr의 맨 뒤에 num을 추가한다. (1 ≤ num ≤ 231-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나올때마다 for문돌면서 하니 시간복잡도가 엄청 커지나보다,, 계속시간초과!

아래는 원래 짰던 것,,

## import lib
import sys

## Stack class init
class Stack:
    '''리스트 이용한 스택 구현'''
    def __init__(self):
        self.stacks = []

    def push(self, item):
        self.stacks.append(item)

    def pop(self):
        return self.stacks.pop()

    def size(self):
        return len(self.stacks)

## problem
my_stack = Stack()
query, mod = map(int, sys.stdin.readline().split())

for _ in range(query):
    input_values = sys.stdin.readline().split()

    if len(input_values) == 2:
        _, append_num = map(int, input_values)
        my_stack.push(append_num%mod)
    else:
        if int(input_values[0]) == 2:
            if my_stack.size() != 0:
                my_stack.pop()
            else:
                pass
        else:
            if my_stack.size() < mod:
                print(-1)
            else:
                check_list_set = set(list(range(0, mod)))

                for i in range(my_stack.size()-1, -1, -1):
                    check_list_set.discard(my_stack.stacks[i])
                    if len(check_list_set) == 0:
                        print(my_stack.size()-i)
                        break

 

할튼 나는 그래서 구글링하면서 보고

스터디 친구들이랑 얘기해보니 그냥 DP에 가까운거 같긴하다,,, 그래서 <DP+스택> 문제로 보면 좋겠다^^!! 휴

이 문제 만드신 조가희 선생님 블로그도 볼 예정!

 

import sys

q, mod = map(int, sys.stdin.readline().split())
# 전체 스택 리스트
arr = []

# mod 나머지 리스트
dp = [[] for _ in range(mod)]

for _ in range(q):
    query = sys.stdin.readline().split()
    # 1인 경우
    if query[0] == '1':
        # 해당 mod 리스트에 인덱스 추가
        dp[int(query[1]) % mod].append(len(arr))
        # 값도 추가
        arr.append(int(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:
            # 빈경우는 어차피 안되니까 -1
            if not x:
                print(-1)
                check = False
                break
            # 현재 mod 기준 최대 index 가져오기 , 지나가면서 최소 index로 이동
            min_count = min(x[-1], min_count)
        if check:
            print(len(arr) - min_count)

가벼운 코드 설명을 하자면

1. 우선 받기전 그냥 수를 받을 리스트, 그리고 mod개 (0~mod-1)까지 수가 나왔는지, 언제 나와서 몇번째 인덱스에 존재하는지 확인하는 이중리스트 를 생성한다
2. 1 num 이 나올 경우 mod로 나눠 나머지를 저장하고, 이 나머지의 리스트 (예를 들어 나머지가 3이면 3의 리스트)에 지금 몇번째 나온 수인지 인덱스를 저장한다.
3. 2는 그냥 pop 하면서 저장한거 빼고, 인덱스 저장한거 뺀다.
4-1. 3의 경우가 중요한데, 뒤에서부터 순서대로 다나왔는지 확인하니까 최악의 경우는 리스트 전체를 다봐야 하는 경우라 min_count = len(arr)로 설정한다.
4-2. 그리고 우선 나머지가 한번씩은 나와야 되니까 이중 리스트 돌면서 리스트가 빈경우가 있다면 -1하고 끝낸다.
4-3. 만약 모두 있다면, 어디까지가 최소로 나와야 성립하는지 알아야 하니까, 각 나머지 리스트마다 최대 인덱스 (여기서는 따라서 그 나머지 리스트의 -1번째 (마지막) 인덱스)를 뽑고, 이것과 현재 min_count 중 더 작은걸 저장한다. (최소로 나와야 하는 거니까 더 작은걸 골라야함)
4-4. 모든 나머지 리스트를 돌고, 최소 여기 인덱스까지 나와야한다 = min_count를 뽑으면 이걸 전체 길이에서 빼서 갯수를 찾는다.

휴 설명끗~

알고 스터디 재밌게 해야지. 그래도 하니까 뿌듯하다.