https://www.acmicpc.net/problem/3015
문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
스택 문제만 주구장창 풀고 있으니 대충 스택 문제는 어떻게 접근해야하는지 윤곽이 보이는 듯 합니다. 큐랑 DFS,BFS는 언제 봐야할지 ㅋㅋㅋ…. 한달 빡 집중하면 코테 끝낼 수 있다고 했던거 같은데 그냥 저는 매일 고민하면서 조금씩 해야 겠습니다.
예시의 숫자인 2,4,1,2,2,5,1을 봅시다.
일단 스택에는 아무것도 없으니 2를 넣어봅시다. 그리고 4와 비교를 합시다.
[2] - 4 쌍을 이룰 수 있습니다. 하지만 2보다 4는 큰 숫자입니다. 4 다음에 어떤 숫자가 오더라도 2보다 크기 때문에 더는 짝지을 수 없습니다. 2를 pop하고 4를 넣습니다. 이 과정에서 +1을 합니다.
그 다음 1을 비교합니다.
[4] - 1 쌍을 이룰 수 있습니다. 역시 +1을 해줍니다.
[4,1] - 2 두개의 쌍을 이룰 수 있습니다. 하지만 1보다 2는 큰숫자이니 마찬가지로 pop하고 2를 넣습니다.
[4,2] - 2 두개의 쌍을 이룰 수 있습니다. 계속해서 봅시다.
[4,2,2] - 5 3개의 쌍을 이룰 수 있습니다. 하지만 5 이후로 오는 숫자는 앞의 [4,2,2]중 어떤 것과도 쌍을 이룰 수 없습니다. 모두 빼고 5를 넣습니다
[5] -1 1개의 쌍을 이룰 수 있습니다.
지금까지 말로 적었던 숫자를 다 더해보면 1+1+2+2+3+1 총 10의 결과를 얻을 수 있습니다. 말로 적은 것을 코드로 옮겨봅시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
num = int(input())
stack=[]
count = 0
for i in range(num):
pe = int(input())
print(stack)
if stack:
if stack[-1] < pe:
count += len(stack)
stack.pop()
while stack:
if stack[-1]<pe:
stack.pop()
else:
break
elif stack[-1] == pe:
count += len(stack)
else:
count += 1
stack.append(pe)
print(count)
코드가 좀 복잡해졌는데… 제 생각에는 총 3가지의 경우의 수가 있다고 보았습니다.
스택 제일 위에 있는 수와 크거나 같거나 작거나 입니다.
다음에 오는 수가 클 경우에는 이전에 있는 길이만큼 쌍을 이룰 수 있고 이후에 오는 수와는 쌍을 이룰 수가 없으니 들어올 수보다 큰 값이 나올때까지 다 빼버립니다.
만약 같다면 길이만큼 더해주고 넘어가면 됩니다. 422 라고 했을때 두 쌍을 이룰 수 있고 뒤에 오는 숫자 역시 마찬가지 입니다.
그리고 작다고 하면 바로 앞에 있는 숫자와 쌍을 이룰 수 있으니 1을 더하고 넘어 갑니다.
다만 틀렸다고 나오네요
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
num = int(input())
stack=[]
ans = 0
for i in range(num):
pe = int(input())
count = 1
while stack and stack[-1][0]<=pe:
ans += stack[-1][1]
if stack[-1][0] == pe:
count += stack[-1][1]
stack.pop()
if stack:
ans+=1
stack.append([pe,count])
print(ans)
파이썬으로는 시간초과가 나오고 pypy로 풀어야 합니다. 한번 봅시다.
ans와 count를 따로 관리를 합니다. count를 관리하는 이유는 연속된 숫자 때문입니다.
2 - 4 - 1 - 2 - 2 - 5 - 1 에서 중간에 나오는 2 - 2 를 따로 넣는것이 아니라 count를 사용해서 연속해서 확인하게 됩니다. 순서대로 가봅시다.
첫번째 2를 삽입 ans는 0에서 시작을 합니다.
[2,1] ans:0
다음 4를 넣게 됩니다. 4는 조건에 따라서 while문을 들어가게 되는데 ans에는 스택에가장 위에 있는 count 1을 넣게 되고 빼게 됩니다.
[4,1] ans: 1
다음 1을 넣습니다. while조건을 만족하지 않으니 바로 삽입합니다.
[4,1] [1,1] ans: 2
다음 2를 넣습니다.
[4,1], [2,1] ans: 4
다음 2를 넣습니다. 이때 조건문에 따라서 count의 값이 변합니다.
[4,1] [2,2] ans: 6
다음 5를 넣습니다.
[5,1] ans: 9
그리고 마지막 1을 넣고 끝나게 됩니다.
Comments powered by Disqus.