[백준 - 1874][Python]스택 수열

안녕하세요. 성조입니다.

이 포스팅은 Python 3 버전을 기준으로 풀이됐습니다.

부족한 부분이나, 올바르지 부분이 있다면 언제든지 댓글 부탁드리겠습니다.

 

조금 더 효율 좋은 방향으로 지도해 주시는 피드백도 감사히 받겠습니다. 

 

 

문제 출처

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

코드

import sys

N = int(sys.stdin.readline())
input_data = []

for i in range(N):
    input_data.append(int(sys.stdin.readline()))


def sequence(N: int, input_data: list):
    """

    :param N: N번 반복할 데이터
    :param input_data: 수열을 이루는 1이상 n이하의 정수
    :return: 결과 정답 반환
    """
    stack_list = []
    stack_operator = []
    compare_index = 0

    for items in range(1, N+1):
        stack_list.append(items)
        stack_operator.append("+")

        while stack_list and stack_list[-1] == input_data[compare_index]:
            stack_list.pop()
            stack_operator.append("-")
            compare_index += 1

        if stack_list and items == N:
            return "NO"

    return "\n".join(stack_operator)


print(sequence(N, input_data))

 

풀이

[사전 지식]

이 문제를 접근하기 전에 기본 스택(LIFO)의 구조 방식을 기억한다.

(처음 들어온 것이 마지막에 나간다. 또한 마지막에 들어온 것이 처음으로 나간다.)

1부터 N까지의 수를 스택에 넣어서 주어진 수열을 만들어야 한다.

 

단, 조건이 있다. "이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자."라는 조건이 붙었기 때문에 오름차순 조건을 가져야 하며, [4, 5, 3, 1, 2]이라는 수열이 존재하는 경우. [1, 2, 3, 4, 5]의 순서로 push 해야 한다.

 

출력 부분의 조건을 확인한다.

 

아래부터는 [접근 및 풀이 방식]이다.

1. [push == +, pop == -] 연산을 진행하며, 불가능한 경우 No를 출력한다.

2. N(반복해서 연산할 값)을 입력받는다. 또한 연산할 값을 받아줄 리스트 input_list를 선언하고 N만큼 입력 받는다.

3. 입력받은 값들을 함수로 전달한다.

4. 스택의 값을 입력받을 변수 stack_list를 선언하고, 어떤 연산자인지 판별하기 위한 공간으로 stack_operator 리스트 변수를 선언한다. 또한 

5. 수열로 받은 input_list 데이터가 스택 맨 위에 있는 자료와 같은지 확인한다. 이때, 파이썬의 인덱싱 개념인 변수[-1]를 활용하여 리스트에 맨 마지막으로 들어온 값을 확인한다.

6. 현재 input_list 값을 stack_list에 추가하며, 더하기 연산자를 stack_operator에 추가한다.

7. stack_list 값이 비어있지 않고, 마지막 값[-1]이 입력 데이터의 현재 위치. 즉, compare_index 변수와 동일하기 이전까지 반복할 수 있도록 while  조건을 주며, stack_list 값의 마지막 요소가 input_list 값으로 들어온 값의 인덱스 번호를 비교하여 같은 경우 해당 값을 stack_list에서 pop() 함수를 활용하여 제외한다. 또한 "-" 연산자를 stack_operator 변수에 추가한다. input_list의 다음 위치의 인덱스를 확인하기 위해서 compare_index의 값을 1 증가시킨다.

8. 만약 반복문(for)이 끝나기 전까지 stack_list가 비어있지 않은 상태라면 items의 값이 반복할 N의 값과 같다는 의미로 더 이상 연산을 할 수 없다는 말이 된다. 그렇게 될 경우. 스택을 만들 수 없으므로 "NO"를 반환한다.

9. 8번 조건을 충족하지 않는 경우에는 수열 스택을 충족하기 때문에 개행을 위한 \n를 join으로 추가하고 반환한다. == 정상 출력

 

 

---

오타나 이해가 안 가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

 

부족한 실력이지만 언제든지 효율적으로 구현할 수 있는 피드백 방향을 주시면 많은 참고 진행하겠습니다.

 

다음 포스팅 때 뵙겠습니다.