스파르타코딩클럽 알고리즘 강의

스택

한쪽 끝(top)으로만 자료를 넣고(push) 뺄(pop) 수 있는 자료구조. (LIFO)

큐

한쪽 끝(back)으로 자료를 넣고(push), 반대쪽(front)에서 자료를 뺄(pop) 수 있는 선형구조. (FIFO)

페어 프로그래밍

문제풀이

1. 스택 수열

문제를 이해하는 데까지 조금 걸리긴 했는데 이해하고 나서는 큰 어려움 없이 풀 수 있었다.
알아낸 조건들은:
n: 입력받은 숫자
top: 현재 스택의 가장 위에 있는 값
max: 지금까지 입력받은 숫자 중 가장 큰 숫자
1. n이 top보다 큰 경우: 스택에 max+1부터 n+1까지 삽입. (같은 횟수만큼 '+'를 문자열에 추가 후 '-' 하나 추가)
2. n이 top과 같은 경우: top 삭제. (문자열에 '-' 추가)
3. n이 top보다 작은 경우: 오류

그리고 조건과 상관없이 top과 max를 구하면 끝.

전체 코드

import sys

a = int(sys.stdin.readline())
stack = []
top = 0
max = -1
s = ""

for i in range(a):
    n = int(sys.stdin.readline())

    if n > top:
        stack.extend(range(max+1 if max != -1 else max + 2, n))
        s += '+\n' * (n - (max+1 if max == -1 else max)) + '-\n'

    elif n == top:
        stack.pop()
        s += '-\n'
    else:
        s = 'NO'
        break

    max = n if n > max else max
    top = stack[-1] if len(stack) != 0 else 0

print(s)

2. 회전하는 큐

이 문제 역시 문제 이해하는 게 어렵지, 이해만 하면 어렵지 않게 풀 수 있는 문제이다.

우선 deque이라는 클래스를 가져와서 사용했다. 문제에서 요구하는 오른쪽/왼쪽으로 한 칸씩 이동하는 rotate 함수 덕분에 간단하게 해결할 수 있다.
rotate 함수의 매개변수가 음수라면 해당 숫자만큼 왼쪽으로, 양수라면 오른쪽으로 이동한다.

풀이:
n: 입력받은 수
i: 위치(인덱스)
count: 왼쪽/오른쪽으로 이동하는 횟수

1. 덱에서 n의 i 검색
2. i가 0이 아니고 덱의 왼쪽(i < 덱의 길이의 절반)에 위치하는 경우 i만큼 왼쪽으로 이동 후 count를 i만큼 증가
3. i가 0이 아니고 덱의 오른쪽(i >= 덱의 길이의 절반)에 위치하는 경우 (덱의 길이 - i)만큼 오른쪽으로 이동 후 count를 (덱의 길이 - i)만큼 증가
4. 0번째 숫자 삭제

전체 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
count = 0

deque = deque(range(1, N+1))

input = list(map(int, sys.stdin.readline().split()[:M]))

for n in input:
    i = deque.index(n)
    if i < len(deque) / 2 and i != 0:
        deque.rotate(-i)
        count += i
    elif i >= len(deque) / 2 and i != 0:
        deque.rotate(len(deque) - i)
        count += len(deque) - i

    deque.popleft()

print(count)

3. 괄호

오늘 문제들 중 이해는 가장 쉬웠지만 조건들이 충돌해서 풀이는 조금 걸렸던 문제다.

s: 입력받은 문자열
stack: 여는 괄호를 담는 스택
c: 문자열의 각 문자

1차 시도:
1. 우선 s의 시작이 ')'이거나 s의 끝이 '('이면 바로 VPS가 아니기 때문에 바로 'NO' 출력 후 다음 s 받기
2. s를 순회하며 c 비교 후 stack에 추가 혹은 삭제
3. c가 '('인 경우 stack에 추가
4. c가 '('이 아니고 stack이 비어있다면 'NO' 출력 후 다음 c 받기
5. c가 '('이 아니고 stack이 비어있지 않다면 stack.pop()
6. 문자열의 끝에 왔을 때 stack이 비어있지 않다면 'NO', 아니면 'YES' 출력

위 방법대로 제출을 했을 때 4번과 6번에서 조건들이 충돌하기 때문에 'NO\nYES'가 동시에 출력이 된다.

is_valid: s가 VPS인지 판별하는 변수

2차 시도:
1. YES/NO를 조건이 성립할 때마다 바로바로 출력하는 게 아니라 is_valid 변수를 둬서 문자열을 다 순회했을 때 is_valid 최종값에 따라 YES/NO 출력
2. 1차 시도의 1~3번까지는 동일 (print('NO')를 is_valid = False로 수정)
3. c가 '('이 아니고 stack이 비어있는 경우 is_valid를 False로 바꿔주고 바로 문자열 빠져나오기
4. c가 '('이 아니고 stack이 비어있지 않은 경우 stack.pop()
5. 문자열 순회를 마쳤을 때 stack이 비어있지 않은 경우 is_valid = False
6. is_valid가 True면 'YES', False면 'NO' 출력

전체 코드

import sys

T = int(sys.stdin.readline())

for i in range(T):
    s = sys.stdin.readline().rstrip()

    is_valid = True
    stack = []

    if s[0] == ')' or s[-1] == '(':
        is_valid = False
    else:
        for c in s:
            if c == '(':
                stack.append(c)
            else:
                if len(stack) == 0:
                    is_valid = False
                    break
                stack.pop()
        if len(stack) != 0:
            is_valid = False
    print('YES' if is_valid is True else 'NO')

4. 균형잡힌 세상

앞의 문제와 거의 동일한데 몇 가지 조건이 추가가 되었다.
1. (), [] 두 괄호가 들어온다.
2. 괄호 외의 다른 문자들도 들어온다.
3. '.'이 입력될 때까지 계속해서 문자열을 입력 받는다.

전체적인 흐름은 앞의 문제와 동일한데, 두 종류의 괄호가 사용되기 때문에 편리성을 위해 open( [ '(', '[' ] )과 close( [ ')', ']' ] ) 스택을 만들어 ch를 각각 스택과 비교했다.

풀이:
1. ch가 open에도 없고 close에도 없으면 무시
2. ch가 open에 있는 경우 stack에 추가
3. ch가 close에 있는 경우
3-1. stack이 비어있으면 is_valid는 False, 반복문 종료
4. stack의 맨 위를 popped에 저장 후 삭제
5. ch와 popped의 괄호 짝이 안 맞는 경우 is_valid는 False, 반복문 종료
6. 문자열 순회를 마쳤는데 stack이 비어있지 않다면 is_valid는 False
7. is_valid의 값에 따라 'yes' 혹은 'no' 출력

전체 코드

import sys

s = ""

open = ['(', '[']
close = [')', ']']

while True:
    s = sys.stdin.readline().rstrip()

    if s == ".":
        break

    stack = []
    is_valid = True

    for ch in s:
        if ch not in open and ch not in close:
            continue
        elif ch in open:
            stack.append(ch)
        elif ch in close:
            if len(stack) == 0:
                is_valid = False
                break
            popped = stack.pop()
            if (popped == '[' and ch == ')') or (popped == '(' and ch == ']'):
                is_valid = False
                break

    if len(stack) != 0:
        is_valid = False
    print('yes' if is_valid is True else 'no')

5. 최대 힙

문제를 이해하는 건 문제가 안 됐지만 힙이라는 자료구조를 list로 구현하려고 했는데 이게 너무 오래 걸렸다. 1시간을 넘도록 고민을 했는데 진전이 없어서 구글링을 해봤는데 heapq 클래스를 가져와서 간단하게 푼 경우가 대부분이었다.

heapq라는 클래스에는 heappop(heap)이라는 함수와 heappush(heap, x)라는 함수가 있다.
말 그대로 heap 자료구조에 push/pop 연산을 하는데, heapq의 디폴트는 최소 힙이라 문제에서 요구하는 최대 힙과는 정반대였다. 해결방법으로는 x(입력받은 수)를 음수로 바꾸어 삽입하는 것이다. 양수로 가장 큰 값이 음수로는 가장 작은 값이기 때문이다. 마찬가지로 pop할 때 우리는 양수의 값이 필요하기 때문에 최소값을 꺼내어 양수로 만들어주면 끝이다.

나중에 시간이 나면 꼭 직접 힙 자료구조를 구현해보기로 하자.

전체 코드

import sys
import heapq

N = int(sys.stdin.readline())

heap = []

for i in range(N):
    x = int(sys.stdin.readline())
    if x == 0 and heap:
        print((-1) * heapq.heappop(heap)) # 최소 힙의 최소값을 양수로 만들어 출력
    elif x == 0 and not heap:
        print(0)
    else:
        heapq.heappush(heap, (-1) * x) # 기존 heapq는 최소 힙만 지원하기 때문에 삽입하려는 숫자를 음수로 만들어 삽입