Classic_Blue_Note

문제

www.acmicpc.net/problem/2504

풀이

해당 문제는 스택을 이용한 연산을 진행하는 문제이다.

문제 자체를 구현하는데는 시간이 많이 걸리지는 않았으나, 예외 처리 과정에서 디버깅 시간이 많이 걸린 문제였다.

식 자체가 틀린 경우 0을 출력해야 하기 때문에, 리턴을 이용하여 한번에 끝낼 수 있도록 함수를 만들어서 사용하였고, 다양한 조건식을 이용해야 했다.

코드 흐름을 간단히 해설해 보면, 우선 식을 입력받은 뒤, for문을 이용하여 차례대로 탐색을 진행한다.

이 과정에서, try-except 문을 통째로 넣어서, 스택의 크기가 0인데 pop하는 상황이 발생하면 에러가 발생하기 때문에, 해당 에러가 발생할 시 식에 오류가 있다고 판단하고, 바로 0을 리턴할 수 있도록 했다.

이후 정상적인 식일 경우 조건문을 살펴보자.

우선 스택에 아무 값이 없는데 ) 또는 ]가 입력되었을 경우 비정상 식이라고 판단한다.

그리고 비정상 식이 아닌 경우, [나 (가 입력되면 우선 스택에 넣어 둔다.

그리고 이렇게 스택에 쭉 넣어가다가, ]나 )가 입력되는 경우를 확인해 보자.

]나 )가 입력되면, 그 순간부터 스택의 값들을 pop해나가면서 그에 대응되는 반대쪽 괄호가 나올때까지 연산을 진행해 주면 된다.

예를 들어 생각하면, ([]) 라는 식이 있을 때, 해당 식을 (3)으로 만들고, 해당 식을 다시 6으로 만드는 과정인 것이다.

이때 스택에서의 상황을 보면, "(, ["가 들어있다가, ]를 만나면서 [가 pop되고, []이 3으로 변환되어 다시 스택에 들어가면, "(, 3"이 된다.

이러한 형태로 반복 연산을 진행하고, 이때 괄호가 ]를 만나면서 pop을 진행하면 다음 [를 만나기 전까지 스택 내부에는 숫자만 존재해야 하기 때문에 int 형태의 값이 아닌 경우 잘못된 식으로 판단했다.

이런 상황에서 [이후에 바로]을 만나거나, (이후 바로 )를 만나는 경우의 예외처리를 위해 loop_flag라는 값을 이용하여 해당 경우에는 기존 값들을 더하는 것이 아니라, 3또는 2가 바로 스택에 들어갈 수 있도록 처리해 주었다.

이후 마지막에 연산이 모두 끝난 후, 스택의 값들을 확인하여 모두 숫자일 경우 더하고, 숫자가 아닌 값이 하나라도 존재할 경우 식에 오류가 존재한다고 판단하였다.

코드

exp = input()


def cal(expression):
    stack = []
    loop_flag = False
    for i in expression:
        try:
            if len(stack) == 0 and i in "])":
                return 0
                
            if i in "[(":
                stack.append(i)
                
            elif i == "]":
                tmp = stack.pop(-1)
                tmp_num = 0
                while tmp != "[":
                    loop_flag = True
                    if type(tmp) == int:
                        tmp_num += tmp
                    else:
                        return 0
                    tmp = stack.pop(-1)
                if not loop_flag:
                    tmp_num = 1
                loop_flag = False
                tmp_num *= 3
                stack.append(tmp_num)
                
            else:
                tmp = stack.pop(-1)
                tmp_num = 0
                while tmp != "(":
                    loop_flag = True
                    if type(tmp) == int:
                        tmp_num += tmp
                    else:
                        return 0
                    tmp = stack.pop(-1)
                if not loop_flag:
                    tmp_num = 1
                loop_flag = False
                tmp_num *= 2
                stack.append(tmp_num)

        except:
            return 0
            
    val = 0
    
    for i in stack:
        if type(i) == int:
            val += i
        else:
            return 0
    return val


print(cal(exp))

문제

www.acmicpc.net/problem/10799

풀이

스택을 사용하는 문제이다. 스택 개념을 이용하되, 예외 처리를 충분히 해 줘야 한다.

처음에는 해당 문제를 풀 때 플래그를 사용하지 않고, )를 만나면 바로 스택의 길이만큼 더해 주었다. 하지만 그렇게 진행했을 경우, )를 2회 연속으로 만났을 때 문제가 발생했다. ) 이후에 )가 오는 상황은 레이저가 존재하는 상황이 아니고, 항상 막대가 끝나는 부분이기 때문에 이때 막대 전체를 자르는 것이 아니라, 막대가 끝난다는 의미로 코드를 진행시켜야 한다. 따라서, (다음에 )가 오는 경우는 레이저로 자르는 경우이기 때문에 그 때 존재하는 막대의 개수인 스택의 크기만큼 조각 개수를 추가해 주고, )다음에 )가 오는 경우는 막대가 끝나는 경우이기 때문에 마지막 조각이라는 의미로 1만큼 조각 개수를 추가해 주었다. 해당 부분은 플래그 변수를 이용해서 구성했다.

코드

exp = input()


stack = []
piece = 0
flag = False

for i in exp:
    if i == "(":
        stack.append(i)
        flag = False
    else:
        if flag:
            stack.pop(-1)
            piece += 1
        else:
            stack.pop(-1)
            piece += len(stack)
            flag = True

print(piece)

문제

www.acmicpc.net/problem/1935

풀이

후위 표기식을 스택을 이용하여 연산하는 문제이다.

우선 알파벳을 인식하기 위해, 파이썬의 in 연산을 사용하였으며, 인덱스 값을 통해 알파벳에 해당하는 숫자를 확인하였다.

이후 스택에 값을 넣어 가면서 연산자가 나오면 스택의 값을 빼내서 연산하는 과정을 반복하였다.

출력 시 소수 아래 2번째 자리까지 출력하기 위해 % 서식을 이용하여 문자열 포매팅을 진행하였다.

코드

N = int(input())

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

stack = []
exp = input()
data = []

for i in range(N):
    data.append(int(input()))

for i in exp:
    if i in alphabet:
        stack.append(data[alphabet.index(i)])
    else:
        stack.append(float(eval(str(stack.pop(-2)) + i + str(stack.pop(-1)))))
print("%0.2f" % stack[0])

문제

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])