22. [백준] 스택과 AC문제

먼저 문제풀이를 하고 스택과 큐, 덱 개념도 같이 살펴보자!!

 

1. 스택

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

10828번: 스택

 

스택 문제는 문제를 잘 읽고.. 이걸 코드로 잘 구현해주면 된다!

import sys; 
input = sys.stdin.readline

stack = []

for _ in range(int(input())):
    inputstr = input().split()
    order = inputstr[0]
    
    if order == 'push':
        stack.append(inputstr[1])
    
    if order == 'top' and len(stack)!=0:
        print(stack[-1])
    elif order == 'top' and len(stack) ==0:
        print(-1)
    
    if order == 'size':
        print(len(stack))
    
    if order == 'empty':
        print(1) if len(stack)==0 else print(0)
        
    if order == 'pop' and len(stack) != 0:
        print(stack.pop())
    elif order == 'pop' and len(stack) ==0:
        print(-1)

 

try-except로 표현해줄 수도 있다.

if order == 'pop':
      try:
          print(stack.pop())
      except IndexError:
          print(-1)

 

코드의 길이를 간략하게 정리한다면,

import sys
input = sys.stdin.readline

stack =[]
for _ in range(int(input())):
	inputstr = input().split()
    order = inputstr[0]
    
    if order == "push":
       stack.append(inputstr[1])
    elif order == "top":
       print(stack[-1] if len(stack) else -1)
    elif order == "size":
        print(len(stack))
    elif order == "empty":
        print(0 if(len(stack)) else 1)
    else: # order == 'pop'
        try:
            print(stack.pop())
        except IndexError:
            print(-1)

 

 

 

2. AC문제 - 시간초과때문에 고생했던 문제..

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

5430번: AC

휴.. 시간초과때문에 3번이나 빠꾸당함 ㅜㅜ

 

먼저 풀이를 공개하겠다..!

import sys; 
input = sys.stdin.readline
from collections import deque

N = int(input().rstrip())

for _ in range(N):
    order = list(input().rstrip())
    n = int(input())
   
    
    if n == 0:
        input()
        arr = deque()
    else:
        arr = deque(map(int, input().rstrip().lstrip('[').rstrip(']').split(',')))
        
    
    noterror = True
    direction = 0
    for i in order:
        if i == 'R':
            if direction == 1:
                direction = 0
            else:
                direction = 1
        elif i == 'D':
            try:
                if direction == 0:
                    arr.popleft()
                else:
                    arr.pop()
            except:
                noterror = False
                print('error')
                break
            
    if noterror:
        if direction == 0:
            print("["+ ",".join(map(str, list(arr))) +"]")
        else:
            print("["+ ",".join(map(str, reversed(list(arr)))) +"]")

 

시간초과가 떴던 이유는, R(순서뒤집기)를 구현하는 과정에서 reverse를 사용했는데, 이렇게 하면 시간복잡도가 O(n)이라서 시간초과가 떴던 것이다.

 

해결방법은, direction이라는 변수를 이용해서 R을 표현했다. 

direction = 0이 정방향, direction =1 이 한 번 순서 뒤집은 상태로 했고, 각 상황에 맞게 D(첫 숫자 버리기)와 리스트 구하는 걸 구현했다. 

 

마지막에 리스트를 구하는 것에서 주의할 점은, 리스트 형태가 아니라 str 문자열로 구해야한다는 것..!!! 

print(",".join(map(str, list(arr)))) # 3,4
print(type(",".join(map(str, list(arr))))) # <class 'str'>
print("["+ ",".join(map(str, list(arr))) +"]") # [3,4]