코딩 테스트/Baekjoon

[백준] 1668. 트로피 진열

배기니어 2021. 4. 15. 16:16

문제

민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열고 들어가자마자 선반의 왼쪽이 보인다. 다른말로 하자면, 뒤의 트로피가 앞의 트로피에 가려져 있다는 말이다.

안타깝게도, 높이가 큰 트로피가 높이가 작은 트로피의 왼쪽에 있다면, 높이가 작은 트로피는 큰 트로피에 가려서 보이지 않게 된다. 트로피는 자기의 앞에 (보는 사람의 관점에서) 자기보다 높이가 작은 트로피가 있을 때만 보이게 된다. 민식이는 선반을 180도 회전시켜서 트로피가 보이는 개수를 변하게 할 수도 있다.

선반위에 올려져 있는 트로피의 높이가 주어졌을 때, 왼쪽에서 봤을 때 보이는 개수와, 오른쪽에서 봤을 때 보이는 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 트로피의 개수 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 왼쪽의 트로피부터 차례대로 높이가 주어진다. 트로피의 높이는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 왼쪽에서 봤을 때 보이는 개수, 둘째 줄에 오른쪽에서 봤을 때 보이는 개수를 출력한다.

 


왼쪽과 오른쪽에서 보이는 트로피의 개수를 각각 구하는 문제이다.

예제 입출력은 다음과 같다.

 

CASE INPUT OUTPUT
1 5
1
2
3
4
5
5
1

 

보이는 트로피 개수를 구하는 방법은 다음과 같다.

 

1. 첫 번째 트로피부터 차례대로 검사한다.

2. 트로피 높이가 증가하면 보이는 개수가 1 증가한다.

3. 트로피 높이가 최대가 되면 그 뒤의 트로피는 보이지 않으므로 검사하지 않는다.

 

왼쪽과 오른쪽에서 위의 과정을 진행한다. 왼쪽과 오른쪽 모두 최대 높이에 도달하면 검사를 종료하면 된다.

 

작성 코드

n = int(input())
trophy = []
left, right = 0, 0  # 보이는 트로피 개수

for _ in range(n):
    trophy.append(int(input()))

max_height = max(trophy)    # 최대 트로피 높이
left_max, right_max = 0, 0    # 현재 최대 트로피 높이
i = 0   # 검사 인덱스

while left_max < max_height or right_max < max_height:
    if trophy[i] > left_max:    # 왼쪽 검사
        left += 1
        left_max = trophy[i]
    if trophy[-i-1] > right_max:    # 오른쪽 검사
        right += 1
        right_max = trophy[-i-1]
    i += 1

print(left)
print(right)

 

'코딩 테스트 > Baekjoon' 카테고리의 다른 글

[백준] 1236. 성 지키기  (0) 2021.04.15
[백준] 1302. 베스트셀러  (0) 2021.04.15
[백준] 1568. 새  (0) 2021.04.14
[백준] 1543. 문서 검색  (0) 2021.04.14
[백준] 11004. K번째 수  (0) 2021.04.14