[boj] 스택(stack)

https://www.acmicpc.net/problemset?sort=ac_desc&algo=71 

 

q2504

'''
열린괄호: (, [ / 닫힌괄호: ), ]
1. 열린괄호가 나오면 push, 닫힌괄호가 나오면 pop
2. 괄호가 아무리 짝이 있더라도 이 문제에서는 짝과 짝사이에 있는 요소들x이 중요 -> (xx) -> 변수를 사용해서 x값을 저장해놓자
3. stack에는 괄호, 숫자가 존재 / 짝괄호가 나오면 숫자가 stack에 push
4. 닫힌괄호가 나오는 순간, 열린짝괄호가 나올 때까지 하나씩 pop(=top)을 함

while stack:
tmp = 0 //tmp가 0이면 (), 0이 아니면 (xx)
if top == '(' //짝괄호이면 +2 or tmp*2
stack.append(2 if tmp == 0 else 2*tmp)
break
elif top == 숫자
tmp += top
else: //잘못된 문자
exit()

5. 마지막 처리
  stack에 숫자만 있으면 perfect -> print(sum)
  괄호가 섞여있으면 짝이 안맞는 경우 -> print(0)
'''

아래 블로그의 그림 참고함

https://reakwon.tistory.com/175

입력(s)
stack = []
for ele in s:
	if ele == ')':
		tmp = 0 //(x)에서 x값들을 더함
		while stack: //새로배움. list에 원소가 있으면 while list == true임
 			top = stack.pop()
			if top == ')':
				stack.append(2 if tmp == 0 else tmp*2)
				break
			elif str(top).isdigit():
				tmp += top
			else:
				print(0)
				exit(0)

	elif ele == ']':
		tmp = 0
		while stack:
			top = stack.pop()
			if top == ')':
				stack.append(3 if tmp == 0 else tmp*3)
				break
			elif str(top).isdigit():
				tmp += top
			else:
				print(0)
				exit(0)
	else:
		stack.append(ele)

p = True if '(' in stack or ']' in stack else False
if p:
	print(0)
else:
	print(sum(stack))

 

q1874

 

1. top의 역할: 1~n에서 중복되는 숫자가 있으면 안되므로 증가할 idx를 정해줌(idx그자체)
2. 예제2를 보면, 이 문제의 핵심을 알 수 있음
       5/12534에서 34에 주목하면, stack에서 꺼내려는 숫자(tmp)와 pop한 숫자가 다른 순간 실패한 경우임
3. max와 같이 선형시간이 걸리는 숫자를 쓰면, 시간초과
4. 다음에는 입력값을 한 번에 받는 걸로 해봐야겠음