[백준/알고리즘/python/java] 1874번 - 스택 수열

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

[1874번 - 스택 수열]

맨 처음에 문제를 이해하는데 시간이 좀 걸렸다.

이해한 바로는 이렇다.

「첫 줄에 n 이 입력되면,

둘째 줄 부터는 1부터 n 까지의 수를 차례로 입력한다.

그렇게 입력된 n 개의 수가 수열을 형성하도록 push 연산은 +, pop 연산은 - 로 표현하도록 출력하면 된다.」

이해가 안되면, 힌트를 보면 된다.

첫 번째 예제입력은 [4,3,6,8,7,5,2,1] 순으로 입력되었다.

이렇게 수열을 이루려면(출력이 예제입력처럼 되려면), 빈 stack = []에 차례로

push(1) → push(2) → push(3) → push(4) → pop() → pop() → push(5) → push(6) → pop() → push(7) → push(8)

→ pop() → pop() → pop() → pop() → pop() 순으로 계산이 되어야 한다.

그림으로 표현해보자면, 이렇다.

 

예제 입력 1 표현

 

(코드는 아래와 같다.-python : Pypy3 로 통과 )

import sys
input = sys.stdin.readline

n = int(input())
stack = [0]       # stack[-1] 과 같이 맨 처음 시작할 때, IndexError를 처리하기 위해 초기 stack에 0을 담아놓는다.
number_list = []
used_number = [0]  # stack에 push했던 숫자들을 담는 리스트
answer_list = []  # '+'와 '-' 가 담긴다.
answer_possible = True  # 표현이 가능한 경우를 체크하는 변수 초기값을 True 로 설정한다.

for i in range(n):		
    number_list.append(int(input()))
for num in number_list:   
    start = used_number[-1]+1  # 다음번에 push 할 숫자는 현재 used_number 리스트에 담겨진 맨 끝 원소보다 1이 커야 한다.

    if num in stack:       # num 이 stack 안에 담겨져 있는 숫자라면 
        while(stack[-1] != num):		# 꺼내야 하므로, stack의 맨 끝 원소가 num이 될 때 까지
            answer_list.append("-")  # print("-") -> pop 표현 역할	
            stack.pop(-1)			# stack에서 하나씩 뺀다.
        answer_list.append("-")  # print("-") 역할
        stack.pop()				 # stack 맨 끝 숫자가 num이 되면 while문을 탈출하므로, 마지막으로 pop()을 해줘야 그 num이 나온다.
        answer_possible = True   

    elif num not in stack:		# num 이 stack 안에 없는 숫자라면
        if num < used_number[-1]: 		# used_number의 맨 끝 숫자가 num 보다 큰 숫자라면
            answer_possible = False		# 그 리스트는 표현 불가능
            print("NO")					# 바로 "NO"를 출력하고 프로그램 종료
            break
        while(stack[-1] != num):	# 꺼내야 하므로, stack의 맨 끝 원소가 num이 될 때 까지
            stack.append(start)		# 우선, start(used_number[-1]+1)을 push 하고
            used_number.append(start)
            answer_list.append("+")  # print("+") -> push 표현 역할
            start += 1		# start를 1씩 증가해준다 계속
        answer_list.append("-")  # print("-")  
        stack.pop(-1)	# 마지막은 역시 pop을 해줘야 그 num이 나온다.
        answer_possible = True


if (answer_possible == True):   # answer_possible 이 True 라면, 표현 가능한 것이므로
    for answer in answer_list:
        print(answer)			# 여태 answer_list 에 담았던 "+" 나 "-"를 차례로 출력해주면 된다.
        

코드를 위에서부터 차근차근 곱씹어 보면서 풀다보면 로직을 이해할 수 있다.

그런데, 이렇게 풀어서 답은 잘 나왔는데, 시간초과 문제에 직면했었다.

그래서 input 대신에 

import sys 

input = sys.stdin.readLine

을 사용했는데도 반복문이 너무 많아서 그런지 시간초과 문제를 해결할 수 없었다.

물론, Pypy3 으로 제출하면 통과되긴 하는데, Python3로도 통과될 수 있는 코드로 수정해봤다.

 

(코드는 아래와 같다.-python: Python3 로도 통과 )

import sys
input = sys.stdin.readline

n = int(input())
number_list = []
stack = []
answer_list = []
cnt = 1
answer_possible = True

for i in range(n):
    number_list.append(int(input()))
for num in number_list:
    while(cnt <= num):
        stack.append(cnt)
        answer_list.append("+")
        cnt += 1
    if stack.pop() != num:
        print("NO")
        answer_possible = False
        break
    else:
        answer_list.append("-")

if (answer_possible == True):
    for answer in answer_list:
        print(answer)

cnt 라는 변수를 초기값을 1로 설정해주어 cnt 변수가 기존 코드에서의 used_number[] 리스트에 들어갈 값을

대신하도록 설정해주었다.

(즉, 1부터 차례대로 증가하는 방식은 굳이 숫자열로 만들어 줄 필요가 없다. 단순히 반복문안에서

cnt 라는 변수를 1씩 증가하는 코드로 그 기능을 대체하도록 구현 가능했다.)

 

마지막에 answer_possible 이라는 변수를 굳이 안쓰고 싶다면,

이러한 코드를 함수로 구현해서 표현 불가능한 입력들은 바로 "NO"가 나오도록(return "NO" 와 같이)

하고 프로그램을 바로 종료하게 할 수도 있다.

시간을 줄이는 것도 개발자의 숙명이다.

 

(아래는 이전에 풀었던 자바 코드이다. -java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main{
	public static void main(String[] args)throws IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Stack<Integer> stack = new Stack<>();
		boolean isAble = true;
		int num=1;
		StringBuilder sb = new StringBuilder();
//		for(int i=1;i<=n;i++) {
//			stack.push(i);
//		}
		int [] bottle = new int[n];
		for(int i=0;i<n;i++) {
			bottle[i]=Integer.parseInt(br.readLine());
			if(isAble) {
				if(num<=bottle[i]) {
					while(num<=bottle[i]) {
						stack.push(num++);
						sb.append("+ \n");
					}
				}
				if(stack.isEmpty()) isAble = false;
				else {
					// 스택의 top 이 bootle[i]보다 작을 때 까지 pop
					while(stack.peek()>=bottle[i]) {
						stack.pop();
						sb.append("- \n");
						if(stack.isEmpty()) {
							break;
						}
					}
				}
			}
		}
		if(isAble) {
			System.out.println(sb.toString());
		}
		if(!isAble) {
			System.out.println("NO");
		}
	}
}