Classic_Blue_Note

문제

www.acmicpc.net/problem/1874

풀이

스택을 이용하여 수열을 완성해야 하는 문제이다. 기본적인 스택 사용법을 아는지에 대해 묻는 문제로, 약간의 생각을 필요로 하는 문제였다.

해당 문제에서의 핵심은 문제의 이해이다. 필자도 처음에는 문제 자체를 이해하는데 약간의 시간이 걸렸는데, 이후 스택을 어떤 식으로 사용하라는 말인지 이해한 후에는 쉽게 문제를 풀 수 있었다.

필자는 isstackable이라는 함수를 이용하여 문제를 풀이하였는데, 그 이유는 결과값이 불가능한 경우, NO를, 가능한 경우 어떤 연산을 진행했는지 순서대로 출력해야 하기 때문에, 함수 내부에서 리턴 값을 이용하여 불가능한 경우에는 "NO"라는 원소 하나를 가진 리스트로, 가능한 경우에는 연산 리스트를 리턴하도록 했다. 그리고 해당 값을 이터레이터를 이용하여 순차적으로 출력하는 과정을 통해 출력을 용이하게 할 수 있도록 풀이하였다.

함수의 내부 동작 원리는 우선 기본 숫자 배열을 만든다. 이후 두 개의 인덱스를 이용하여 하나는 기본 숫자 배열을 가리키고, 하나는 입력값 숫자 배열을 가리키도록 이용하여 스택의 가장 위 값과 입력값 숫자 배열의 인덱스 위치의 원소가 일치하지 않을 경우 기본 숫자 배열의 값을 스택에 넣고 다음 인덱스로 넘어가는 식으로 구성하였으며, 스택이 비어 있는 경우에는 무조건 스택에 원소를 넣도록 구현하였다.

이후 과도한 오버헤드를 방지하기 위해 기본 숫자 배열의 마지막 원소까지 1차적으로 확인이 끝났으면 이제 남은 원소는 모두 스택 안에 존재하는 것이기 때문에 스택의 모든 값을 빼내고, 새롭게 만들어진 배열과 처음에 입력받은 배열이 서로 같은지 확인을 통해 스택을 통해 해당 배열을 만드는 것이 가능한지 확인하고, 결과값에 따라 리턴하였다.

해당 문제는 디버그 과정에서 약간 시간을 썼는데, 처음에는 마지막 스택을 완전히 마무리하는 과정에서 연산자 리스트에 pop했다는 내용을 넣어주지 않아서 틀린 결과가 나왔었다. 결국 디버깅이 알고리즘 연습의 시간을 좌우한다는 생각이 들었으며, 하나하나 차근차근히 디버깅하는 습관을 가지면 어떤 문제든 해결할 수 있을 것이라고 믿는다.

코드

import sys

N = int(input())

final_data = [int(sys.stdin.readline()) for i in range(N)]


def isstackable(final_data):
    data = [i for i in range(1, N + 1)]
    op_list = []
    stack = []
    my_data = []
    idx = 0
    idx2 = 0
    while idx2 < len(data):
        if len(stack) == 0:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
            continue
        if stack[-1] != final_data[idx]:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
        else:
            idx += 1
            my_data.append(stack.pop(-1))
            op_list.append("-")
    for i in stack[::-1]:
        my_data.append(i)
        op_list.append("-")
    if my_data == final_data:
        return op_list
    else:
        return ["NO"]


ans = isstackable(final_data)
for i in ans:
    print(i)

문제

www.acmicpc.net/problem/2164

풀이

큐 자료구조를 사용하는 문제이다. 선입선출의 원리를 이용한다.

자료구조는 python collections 모듈의 deque를 사용했고, 해당 자료구조를 이용하여 큐를 구현하였다.

큐 자료구조의 원리를 안다면 간단히 풀리는 문제이다.

종종 인덱스 에러가 발생하는 경우가 있는데, 인덱스 에러가 발생할 경우 경계값 부분을 디버깅 해 볼 필요가 있다. 조건을 확인하고, 해당 조건에서는 1과 500000이 경계값이므로 해당 값이 적절하게 들어가는지 확인해 볼 필요가 있다.

코드

from collections import deque

N = int(input())

queue = deque()

for i in range(N):
    queue.appendleft(i+1)

while True:
    if len(queue) == 1:
        break
    queue.pop()
    tmp = queue.pop()
    queue.appendleft(tmp)

print(queue[0])

문제

www.acmicpc.net/problem/18258

풀이

이번 문제는 큐를 구현하는 문제이다. 파이썬에서는 collections 모듈의 deque 클래스를 이용하여 큐를 이용할 수 있다.(엄밀히는 덱이지만, 덱을 큐처럼 사용하면 된다.)

앞의 스택 구현 문제와 유사하게, isempty 함수만 별도로 구현하여 사용하였고, 나머지는 바로 출력하였다.

그러나 처음에는 시간 초과 에러가 발생했는데, 이유를 처음에는 찾지 못했으나 최대한 시간을 줄이기 위해 구글링해 본 결과 입력 과정에서 오버헤드가 발생한다는 것을 확인할 수 있었다. 실제로 sys.stdin.readline() 메소드를 이용하여 입력받으니 시간 초과가 발생하지 않았으며, 문제를 정상적으로 해결할 수 있었다.

이번 문제를 풀면서 큐의 기본적인 사용 방법을 확인할 수 있었고, 파이썬의 입력 과정에서 생각보다 큰 오버헤드가 발생할 수 있다는 점을 알 수 있었다. 다음부터는 sys 모듈을 이용하여 입력받는 습관을 들이는 편이 시간 단축에 더 유리할 것 같다.

코드

from collections import deque
import sys

N = int(input())


def isempty(data):
    return len(data) == 0


queue = deque()

for i in range(N):
    cmd = sys.stdin.readline().split()
    if cmd[0] == "push":
        queue.append(int(cmd[1]))
        
    elif cmd[0] == "pop":
        if isempty(queue):
            print(-1)
        else:
            print(queue.popleft())
            
    elif cmd[0] == "size":
        print(len(queue))
        
    elif cmd[0] == "empty":
        if isempty(queue):
            print(1)
        else:
            print(0)
            
    elif cmd[0] == "front":
        if isempty(queue):
            print(-1)
        else:
            print(queue[0])
            
    elif cmd[0] == "back":
        if isempty(queue):
            print(-1)
        else:
            print(queue[-1])