아스

문제의 원래 의도는 최소 힙(min heap)을 구현하는 것이나, 문제를 푼 방법을 설명하는 코테 등이 아니라면 파이썬에 구현되어 있는 heapq 라이브러리를 쓰면 쉽게 풀 수 있다. 

heap으로 사용하기 위해서 heap이라는 리스트 변수를 선언했다. 

heap에 원소를 넣기 위해서는 heapq.heappush(heap변수, 추가할 원소) 를 사용한다. 

반대로 heap에서 가장 작은 원소를 빼기 위해서는 heapq.heappop(heap변수)를 사용한다. 

heapq 라이브러리는 최소 힙으로 구현되어 있지만, 최대 힙으로도 사용할 수 있다. 

앞서 heappush 연산을 할 때 추가할 원소의 값을 음수로 넣어주면 양수로는 가장 큰 원소가 가장 작은 원소로 간주되어 맨 마지막에 나오게 된다. 

import heapq
import sys
input = sys.stdin.readline

N = int(input())
heap = []
for _ in range(N):
    command = int(input())
    if command == 0:
        if heap:
            elem = heapq.heappop(heap)
            print(elem)
        else:
            print(0)
    else:
        heapq.heappush(heap, command)

몇 번째로 출력되는지 알아야 할 원소의 초기 인덱스인 M을 사용해서 해당 원소가 현재 몇 번째 인덱스에 있는지를 관찰하였다.

M의 경우 매 시행마다 앞으로 한 칸씩 당겨지므로 1씩 값을 제거하면서 그 값을 배열의 길이로 나눈 나머지를 사용하였다. 그래야 M의 값이 원소의 인덱스 범위를 벗어나지 않고 정확히 원소의 위치를 가리킬 수 있다. 

또한 cnt 변수를 사용해서 원소를 Q에서 제거하고 출력할 때마다 cnt 값을 1씩 증가시켰다. 

매 시행마다 Q(데크)에서 맨 앞의 원소를 뺀 뒤, 해당 원소의 뒤에 있는 원소들 중에서 해당 원소보다 큰 원소가 없으면 해당 원소를 제거했다.

만약 해당 원소보다 큰 원소가 뒤에 있었다면, popleft()로 제거했던 맨 앞의 원소를 다시 append()를 사용해서 배열의 맨 뒤에 넣어주었다. 

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

for _ in range(T):

    N, M = map(int, input().split())
    Q = deque(list(map(int, input().split())))
    
    if N == 1:
        print(1)
    else:
        cnt = 0
        
        while Q:
            elem = Q.popleft()
            
            if Q and max(Q) > elem:
                Q.append(elem)
            else:
                cnt += 1
                if M == 0:
                    break
            M = (M-1) % len(Q)
                    
        print(cnt)

상태 변화를 체크할 변수들을 몇 개 선언하고, 실제로 스택에 수를 넣었다가 빼는 작업을 하면 되는 문제다. 

1. queue 변수에는 스택에서 출력해야 하는 변수들을 차례대로 입력받아 넣었다. 

2. stack 변수는 실제 스택 역할을 하는 변수이다. 

3. maxNum 변수는 스택에 들어갔었던 가장 큰 숫자 값을 저장하는 변수이다. 스택에 push를 할 때는 모든 원소를 오름차순으로 넣어야 하기 때문에 이 값이 필요했다.

4. ops 변수는 스택에서 어떤 연산이 수행되었는지 그 값들을 모으기 위한 리스트 변수이다. 

queue 변수는 데크 자료형으로 선언해서, 맨 앞에서 원소를 뺄 때도 O(1) 시간에 제거할 수 있도록 했다. 

만약 현재 stack에서 출력되어야 하는 원소(queue의 맨 앞에서 빼낸 원소)가 stack의 maxNum 값보다 크다면, stack에 수를 더 넣어야 한다는 뜻이므로 for문을 사용해서 stack에 원소를 1씩 증가시키며 추가해 주었다. 또한 stack에 원소를 추가할 때마다 ops 변수에도 "+" 값을 추가해 주었다. 

만약 그렇지 않다면, queue에서 빼낸 원소와 stack의 맨 뒤의 값이 일치하는지를 확인했다. 두 값이 일치한다면 해당 값을 stack에서 빼내서 출력해야 하므로 stack에서 pop()으로 원소를 빼내고, ops 변수에도 "-" 값을 추가해 주었다. 

또한 queue와 stack에는 모두 1부터 N까지의 원소가 들어갔다 나와야 하기 때문에, 정상적으로 수행되었다면 queue가 빌 때 stack도 비어야 한다. 

만일 그렇지 않다면 중간에 queue에서 빼낸 값과 stack의 맨 뒤의 값이 일치하지 않아서 stack에서 원소를 빼낼 수 없었다는 뜻이므로, while 문을 다 돌려보면 queue는 비는데 stack에는 원소가 남게 된다. 

따라서 이 경우에만 에러를 출력한다. 

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
queue = deque([])

for _ in range(N):
    queue.append(int(input()))
    
stack = []
ops = []
maxNum = 0

while queue:
    
    elem = queue.popleft()
    
    if maxNum < elem:
        for i in range(maxNum+1, elem+1):
            stack.append(i)
            ops.append("+")
        maxNum = max(max(stack), maxNum)
    
    if stack and elem == stack[-1]:
        stack.pop()
        ops.append("-")
        
if stack:
    print("NO")
else:
    for op in ops:
        print(op)

파이썬의 딕셔너리 자료구조형은 해시 테이블(hash table)으로 구현되어 있는데, hash table의 경우 일반적인 리스트보다 내부 원소에 더 빠르게 접근할 수 있다. 

따라서 never_listen 변수를 리스트로 선언하지 않고 딕셔너리로 선언해서 M번의 루프를 돌 때 해당 이름이 never_listen 내부에 있는 값인지 더 빨리 확인할 수 있도록 하였다.

import sys
from collections import defaultdict
input = sys.stdin.readline

N, M = map(int, input().split())
never_listen = defaultdict(lambda: False)
never_listen_and_see = []

for _ in range(N):
    name = input().strip()
    never_listen[name] = True

for _ in range(M):
    name = input().strip()
    if never_listen[name]:
        never_listen_and_see.append(name)
        
never_listen_and_see.sort()

print(len(never_listen_and_see))
for nlas in never_listen_and_see:
    print(nlas)

import sys
input = sys.stdin.readline

N = int(input())
S = set()

for _ in range(N):
    command = input().strip()
    
    if command == "all":
        S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
    elif command == "empty":
        S = set()
    else:
        cmd, elem = command.split()
        elem = int(elem)
        
        if cmd == "add":
            S.add(elem)
        elif cmd == "remove":
            if elem in S:
                S.remove(elem)
        elif cmd == "check":
            if elem in S:
                print(1)
            else:
                print(0)
        else:
            if elem in S:
                S.remove(elem)
            else:
                S.add(elem)

배추밭과 심어진 배추 위치 정보를 배열에 저장한 뒤, 배열을 BFS로 탐색하면 된다.

BFS나 DFS로 탐색하면 한 위치에서 출발해서 갈 수 있는 모든 점을 탐색할 수 있기 때문에 인접한 배추를 모두 한 번에 구할 수 있다. 

다른 문제에서는 이미 탐색한 지점을 구분하기 위해 visited라는 배열을 선언하기도 하지만, 여기서는 이를 구분하기 위해 이미 탐색한 배열 값을 1에서 0으로 바꿔 주었다. 

import sys
from collections import deque
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(start_x, start_y):
    queue = deque([[start_x, start_y]])
    arr[start_x][start_y] = 0
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            if arr[nx][ny] == 1:
                queue.append([nx, ny])
                arr[nx][ny] = 0


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    arr = [[0] * N for _ in range(M)]
    for _ in range(K):
        a, b = map(int, input().split())
        arr[a][b] = 1
    
    cnt = 0
    for i in range(M):
        for j in range(N):
            if arr[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

DP(dynamic programming)을 이용해서 풀 수 있는 문제였다. 

예를 들어 피보나치 함수는 f(i) = f(i-1) + f(i-2) 라는 점화식이 적용되는데, 이는 피보나치 수의 값 뿐만 아니라 문제에서 나오는 0과 1의 출력 횟수에도 동일하게 적용된다. 

import sys
input = sys.stdin.readline

dp = [[0, 0] for _ in range(41)]
dp[0][0], dp[0][1] = 1, 0
dp[1][0], dp[1][1] = 0, 1

for i in range(2, 41):
    dp[i][0] = dp[i-1][0] + dp[i-2][0]
    dp[i][1] = dp[i-1][1] + dp[i-2][1]
    
T = int(input())
for _ in range(T):
    N = int(input())
    print(str(dp[N][0]) + " " + str(dp[N][1]))

배열을 선언하고 명령어에 따라 뒤집거나 앞의 원소를 빼면 값은 맞게 나오지만 시간 초과가 걸리는 문제였다. 

1. 전처리

- 배열을 두 번 뒤집는 것은 아무 일도 하지 않는 것과 같기 때문에 명령어에 "RR"이 들어간 경우 이를 제거해주었다. 

- 배열이 빈 배열인데 명령어에 "D"가 들어가면 배열을 순회하기 전에 오류로 판단하였다. 

2. 배열 순회

- "D"가 나올 때마다 뒤집으면 deque를 사용해도 시간초과가 나는 것 같았다. 따라서 reverse라는 변수를 추가하고, 현재 D가 몇 번 나왔는지를 기록하는 데 사용했다. 

(D가 홀수 번 나왔으면 reverse=True로 배열이 뒤집혀야 하는 상태이고, 짝수 번 나왔으면 reverse=False로 배열이 원래 상태이다.)

- "R"이 나올 때는 reverse의 변수 값만 바꿔주었다. "D"가 나오면 reverse의 값에 따라 맨 앞의 원소를 뺄지(배열이 그대로 있는 상태), 맨 뒤의 원소를 뺄지(배열이 뒤집힌 상태)를 결정하였다.

배열은 리스트가 아니라 데크(deque)를 사용했기 때문에 원소를 빼는 작업은 O(1)이 걸렸다. 

- 마지막에는 배열을 그대로 출력해야 했기 때문에 reverse=True일 때만 마지막으로 한 번 뒤집어 주었다. 

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    is_error = False
    arr = deque([])
    commands = input().strip().replace("RR", "")
    length = int(input())
    string = input().strip()
    reverse = False
    if not string == "[]":
        arr = deque(string.replace("[", "").replace("]", "").split(","))
    if len(arr) == 0 and "D" in commands:
        is_error = True
    if not is_error:
        for command in commands:
            if command == "R":
                reverse = not reverse
            else:
                if len(arr) == 0:
                    is_error = True
                    break
                if not reverse:
                    arr.popleft()
                else:
                    arr.pop()
                     
    if is_error:
        print("error")
    else:
        if reverse:
            arr.reverse()
        print("[", end="")
        print(",".join(arr), end="")
        print("]")