문제
농부 희찬이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 희찬이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다.
i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키와 같거나 큰 소가 서 있을 경우 그 소의 앞에 있는 소들의 머리 모양을 볼 수 없다.
다음 예제 (5 2 4 2 6 1)를 고려해보자: ()의 숫자는 키를 나타낸다.
1번 소는 2,3,4번소의 머리 모양을 볼 수 있다.
2번 소는 어떤 소의 머리 모양도 볼 수 없다.
3번 소는 4번 소의 머리 모양을 볼 수 있다.
4번 소는 어떤 소의 머리 모양도 볼 수 없다.
5번 소는 6번 소의 머리 모양을 볼 수 있다.
6번 소는 모든 소들의 머리 모양을 볼 수 없다!
i번 소들이 볼 수 있는 머리 모양의 수를 Ci 이라고 할 때, C1부터 CN 까지의 합을 출력하는 프로그램을 작성하라. 위의 예제의 답은 3+0+1+0+1+0=5가 된다.
입력
첫 번째 줄에는 N 이 입력된다.
그리고 그 다음 줄부터 N개의 줄에 숫자가 입력되는데, i번째 줄의 숫자는 hi를 뜻한다.
6
5
2
4
2
6
1
출력
C1 부터 CN 까지의 합을 한 줄에 하나씩 출력한다.
5
풀이
그냥 생각난 전체 탐색... 당연히 Time Limit Exceed
import sys
readl = sys.stdin.readline
N = int(readl())
cows = [int(readl()) for _ in range(N)]
sum = 0
for i in range(N):
for j in range(i + 1, N):
if cows[i] > cows[j]:
sum += 1
else:
break
print(sum)빌딩 문제랑 비슷한 것 같아서 스택에 어떤 기준으로 모르겠어서 다른 분의 코드를 참고해서 풀었다.
for 문으로 하나씩 돌리면서 그 차례의 소를 볼 수 있는 앞의 소가 얼마나 있는지를 세는데,
앞의 소가 자기보다 크면 볼 수 있음 (스택에 남아 있어야 함)
앞의 소가 자기보다 작으면 못봄 (스택에서 빼야함)
-> 그래서 스택 top 이 자기보다 크면 스택에 넣고
스택 top 이 작거나 같으면 스택 top 이 커질때까지 빼고 넣음.
5 (5는 첫번째니까 5를 볼 수 있는 소 없음)
5 2 (5는 2를 볼 수 있음 + 1)
5 (2는 4를 볼 수 없음)
5 4 (5는 4를 볼 수 있음 + 1)
5 4 2 (5와 4는 2를 볼 수 있음 + 2)
5 4 (2는 6을 볼 수 없음)
5 (4는 6을 볼 수 없음)
(5는 6을 볼 수 없음)
6 (비어있어서 넣음)
6 1 (6은 1을 볼 수 있음 + 1)
그래서 stack 에 push 하기 전의 stack 의 길이를 더한다.
import sys
readl = sys.stdin.readline
N = int(readl())
cows = [int(readl().strip()) for i in range(N)]
sum = 0
local = 0
stack = []
for cow in cows:
if not stack:
stack.append(cow)
continue
while stack:
if stack[-1] > cow:
sum += len(stack)
stack.append(cow)
break
else:
stack.pop()
if not stack:
stack.append(cow)
print(sum)2트
import sys
from collections import deque
readl = sys.stdin.readline
n = int(readl())
cows = [int(readl()) for _ in range(n)]
stack = []
cnt = 0
for cow in cows:
if len(stack) == 0:
stack.append(cow)
while stack and stack[-1] <= cow:
stack.pop()
cnt += len(stack)
stack.append(cow)
print(cnt)