이런식으로 왼쪽부터 오른쪽으로 중복없이 쌍을 찾아가는 것을 생각했다. 그러나 스텍을 이용해서는 방법을 찾을 수 없었다.
생각 2 2 -> x 4 -> 2 1 -> 4 2 -> 1,4 2 -> 2,4 5 -> 2,2,4 1 -> 5 총 10개
처음 2는 stack에 넣고 4부터 stack을 뽑아보며 자기 자신과 비교해서 증가시키면 된다고 생각했다.
+ 추가
생각 2와 같은 방식은 옳은 방향이다. 내가 코드 구현을 못하였던거였다.
틀린 내 코드
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(input())
stack=[]
res=[0]*N # 내 생각과 맞게 돌아가는지 보기 위해
for i in range(N):
x=int(input())
while stack:
res[i]+=1
if x>stack[-1]:
stack.pop()
else:
break
stack.append(x)
# i를 넣을지, x를 넣을지, 아님 둘다 넣을지 고민
print(res)
print(sum(res))
[0,1,1,2,1,3,1] 9 뭔가 아슬아슬하게 답이 나오지 않았다. 원하는 답은 [0,1,1,2,2,3,1] 10 이어야 하는데 답이 안나온다.
정답 코드
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(input())
stack=[]
res=[0]*N
for i in range(N):
x=int(input())
while stack:
if x>stack[-1][0]: # 현재 키가 이전 사람 키보다 크면
res[i]+=stack.pop()[1] # 현재 사람에게 한쌍 주어줌
else:
break
if not stack: # stack이 비어있을때, 제일 먼저 이뤄질 코드
stack.append([x,1]) # 현재 사람이 이전 사람보다 키가 컸을때도
elif stack[-1][0]==x: # stack에 마지막 사람 키가 현재 사람 키와 같으면
cnt=stack.pop()[1]
res[i]+=cnt
if stack: # 키가 같은 사람끼리는 자기보다 작은 사람 통과해서 쌍이룰 수 있음
res[i]+=1
stack.append([x,cnt+1])
else: # stack에 마지막 사람 키가 현재 사람 키와 다르면
stack.append([x,1]) # 일단 쌓아두고
res[i]+=1 # 쌍은 추가
# print(res)
print(sum(res))
