백준 10828번 : 스택

문제 링크

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

10828번: 스택

 

 

시도1 (시간초과)

N = int(input())
stack = []
for _ in range(N) :
  content = input().split(' ')
  if content[0] == 'push' :
    stack.append(content[1])
    
  if content[0] == 'pop' :
    if len(stack) == 0 : 
      print(-1)
    else :
      pop_num = stack.pop()
      print(pop_num)

  if content[0] == 'size' :
    print(len(stack))

  if content[0] == 'empty' :
    if len(stack) == 0 :
      print(1)
    else :
      print(0)

  if content[0] == 'top' :
    if len(stack) == 0 :
      print(-1)
    else :
      print(stack[-1])

 

 

시도2 (성공)

import sys

N = int(input())
stack = []
for _ in range(N) :
  content = sys.stdin.readline().strip()
  if 'push' in content :
    method, num = content.split(' ')
    stack.append(num)
    
  if content == 'pop' :
    if not stack : 
      print(-1)
    else :
      pop_num = stack.pop()
      print(pop_num)

  if content == 'size' :
    print(len(stack))

  if content == 'empty' :
    if not stack :
      print(1)
    else :
      print(0)

  if content == 'top' :
    if not stack :
      print(-1)
    else :
      print(stack[-1])

 

- 시간 초과 문제를 해결하기 위해 한 시도

1. 시도1에서는 content가 항상 리스트가 된다. 매 조건문마다 인덱스에 접근해 탐색하는 과정

시간복잡도 증가할까봐 push인 경우만 리스트로 접근하도록 처리

+ 추가로 지금 든 생각 : 

 

2. len()함수가 O(n)으로 동작하는 줄 알고 if not stack : 표현으로 수정해서 len()을 사용하지 않도록 수정했다. 

그러나 len()은 O(1)로 동작하더라.. 왜 그렇게 되는지는 나중에 다시 알아볼 예정이다.

참고 : https://yujin-dev.tistory.com/59

 

3. 위 2가지를 했을 때도 사실 해결되지 않아 질문-답변 글을 참조했는데 핵심은 이거였다.

-> 입력량이 많은데 빠른 입력 처리를 해주지 않아 그렇다

즉 for문 내에서는 input()이 아닌 import sys 후에 sys.stdin.readline()을 사용해야한다는 것이다.

백준 알고리즘 문제를 풀다보면 수백, 수천번 이상 반복하는 for문 내에서 입력을 받는 문제가 종종 등장하는데, 이때는 반드시 후자와 같이 해주어야 한다. 두 가지의 차이점을 정리해볼 예정이다.

 

추가 의문점

1. 왜 readline()은 strip함수를 써줘야 하는가?

2. strip()과 rstrip()은 어떤 차이가 있는가?

3. stdin은 뭘까?

4. 한 변수에 대해 input().split(' ')을 하면 왜 오류가 안날까?

ex) a = input().split(' ')는 하나만 입력해도 a는 자동으로 리스트가 됨

5. 왜 한 변수에 대해 input().split(' ') 할 때만 리스트에 저장되고, 그 이상의 변수에 대해서는 str로 저장될까?

ex) a, b = input().split(' ')후에 두 개를 입력하면 a, b는 자동으로 str

6. 공식 문서 확인, 정리, 공부 필요 : stdin, readline, input, strip, rstrip, split  함수, sys모듈

참고 : reference.readthedocs.io/en/latest/docs/str/split.html

 

* 나한테 아직은 생소하지만 사용해본 개념

리스트가 비어있으면 False, 원소가 1개라도 존재하면 True 로 동작해서 이를 이용해 조건문 판별할 수 있다.

 

* 알게 된 부분

여러 개의 변수를 입력 받을 때 split을 썼다면 변수 개수만큼 입력을 할당 받아야한다. 그렇지 않으면 ValueError

ex) a, b = input().split(' ') 를 했으면 정확히 띄어쓰기를 기준으로 입력을 2개 해야함.