문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
6198번: 옥상 정원 꾸미기 문제보기
제한시간: 1초
메모리 제한: 128 MB
문제
도시에는 N개의 빌딩이 있다.
빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.
i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.
예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우
- 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
- 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
- 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
- 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.
따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.
입력
- 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
- 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)
출력
각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.
예제 입력 1
6
10
3
7
4
12
2
예제 출력 1
5
계속해서 시간초과를 겪었다...
테스트셋은 맞는데...
일단 입력이 저렇게 주어지면 입력순서대로 입력받으면서 해결하려고 노력하자.
2493번: 탑 문제와 같다고 생각했는데 풀리지 않았다.
나는 다음과 같은 프로세스로 문제를 풀었다.
틀린 내 코드
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(sys.stdin.readline())
res=[0 for _ in range(N)]
stack=[]
for i in range(N):
x=int(sys.stdin.readline())
while stack:
if x<stack[-1][1]:
for k in range(len(stack)):
res[stack[k][0]]+=1
break
else:
stack.pop()
stack.append([i,x])
print(sum(res))
입력을 받고 다음 빌딩이면 현재 빌딩이 이전 빌딩보다 크면 큰 빌딩 위치에 +1씩 하게 만들었는데 실패...
결국 위 코드에서 index i를 append안하면 아래 코드와 같다.
틀린 내 코드 2
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(sys.stdin.readline())
res=0
stack=[]
for i in range(N):
x=int(sys.stdin.readline())
while stack:
if x>=stack[-1]:
stack.pop()
else:
for k in range(len(stack)):
res+=1
break
stack.append(x)
print(res)
그러나 여전히 시간 초과가 발생한다.
최종 정답
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(sys.stdin.readline())
builds=[]
res=0
stack=[]
for i in range(N):
x=int(sys.stdin.readline())
builds.append(x)
while stack:
if x>=stack[-1]: # 자기보다 작은게 뒤에 있으면
stack.pop() # stack에서 제거하고 큰거만 남김, 자기보다 큰게 없으면 다 제거해버림
else:
break
stack.append(x)
res+=len(stack)-1 # 자기보다 큰게 뒤에 있을때 숫자가 늘어남
print(res)
결국 틀린 내 코드 2에서 while문 안에 else에 for k in range(len(stack)): res+=1을 while 문 밖으로 빼서
res+=len(stack)-1을 했었으면... 생각의 과정은 비슷하게 찾아 갔는데 마무리가 아쉽다...
+ 업데이트
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(sys.stdin.readline())
res=0
stack=[]
for i in range(N):
x=int(sys.stdin.readline())
while stack:
if x<stack[-1]: # 현재 빌딩보다 이전 빌딩이 더 크면
res+=len(stack) # 현재 빌딩보다 큰 이전 빌딩들 수 다 더해
break
else:
stack.pop() # 큰 빌딩만 남음
stack.append(x)
print(res)
틀린 내 코드 2에서 정답코드를 봤을때 정말 코앞까지 왔는데 틀렸다는 것을 알고 틀린 내 코드 2를 좀더 손봤더니 통과를 하였다.
