문제

1874. 스택 수열

나의 성능

메모리: 123308 KB, 시간: 4960 ms(pypy 제출)

분류

자료 구조(data_structures), 스택(stack)

분석

사실 python3로 제출했을 때는 7%에서 시간 초과가 나서 pypy3로 제출하였다...
이는 로직이 좀 잘못됐...다는 느낌?

나의 로직

1. N을 입력 받는다
2. N번 만큼 숫자를 입력받는다
	1. stack이 비었거나 stack의 마지막(제일 나중에 들어온) 숫자가 num보다 작다면
		1-1. check 표시 안된 숫자들을 오름차순으로 넣고(무조건 1~) check mark를 남긴다
    	1-2. for문이 끝나면 가장 마지막 숫자(방금 입력받은 숫자)를 pop해준다
	2. 입력받은 숫자가 stack의 마지막 숫자와 같다면 pop해준다
3-1. stack에 숫자가 남아있거나 check 안 된 숫자가 존재하면 "NO" 출력
3-2. 아니라면 결과 출력

다른사람 로직

1. 한번에 입력 받았다. n, *wish = map(int, sys.stdin.read().split())		
2. 숫자 리스트의 숫자를 하나씩 꺼낸다
	1. 지정해둔 숫자 값(지금부터 num이라 칭하겠다)보다 숫자의 값이 크거나 같을 때까지 반복
		1. stack에 num추가하고 num += 1
	2. stack[-1]이 현재 숫자와 같지 않다면 결과값 "NO" break
	3. stack을 pop한다.

나와 다른 이의 차이

1. 나는 check를 두어 계속 1부터 확인하는 방법을 이용하였지만 다른 사람은 num을 칭했다.

   이 부분에 대한 연습이 필요한 것 같다. 임의의 변수를 지정하고 확인 용도로 쓰는 로직...!

2. 나는 한번에 출력을 받지 않아 실행 끝나지 못했다. 다른 사람은 즉시 NO를 만들고 break를 해서 시간 차이가 엄청 날 것이다.
    

😊What I Learned

n, *wish = map(int, sys.stdin.read().split())

*args

arguments, 여러 개의 인자를 받을 때(몇 개 받을지 모르겠을 때) 사용한다.
튜플로 받는다.

**kwargs

keyword arguments
키워드 : 특정 값
이렇게 받으면 {'keyword':'argument'} 형식인 딕셔너리 형태로 받는다.

print("\n".join(oper))
'구분자'.join(list) : 리스트의 값과 값 사이에 '구분자'에 들어온 구분자를 넣어서 하나의 문자열로 합쳐준다.

   

💻CODE

# 나의 코드
import sys

N = int(sys.stdin.readline())
stack = []
check = [False] * N
result = []
for i in range(N):
    num = int(sys.stdin.readline()) - 1
    if not stack or stack[-1] < num:
        for j in range(num + 1):
            if not check[j]:
                stack.append(j)
                check[j] = True
                result.append('+')
        stack.pop()
        result.append('-')
    elif num == stack[-1]:
        stack.pop()
        result.append('-')
if stack or check.count(False):
    print("NO")
else:
    print('\n'.join(result))

# 다른 사람 코드
import sys


def makeSeq():
    n, *wish = map(int, sys.stdin.read().split())
    server = 1
    receiver = []

    oper = []
    for w in wish:
        # push
        while server <= w:
            receiver.append(server)
            oper.append("+")
            server += 1

        if receiver[-1] != w:
            oper = ["NO"]
            break

        # pop
        receiver.pop()
        oper.append("-")

    print("\n".join(oper))


makeSeq()