[백준] 1668번 : 트로피 진열

유형 : 탐색

 

[예제]

7
1
4
2
5
3
7
1

[출력]

4
2

---

 

1. 내 풀이

예제를 우선 살펴보면,

위의 그림처럼 중간중간 변하는 max를 기준으로 보이는 개수가 달라지는 것을 알 수 있다. 그래서 max값을 기준으로 값을 비교하는 식으로 코드를 짜면 되겠다고 생각했다.

 

import sys

N = int(sys.stdin.readline())
_list = []
for _ in range(N):
    num = int(sys.stdin.readline())
    _list.append(num)

def count_trophy(_list,N):
    cnt = 1
    _max = _list[0]
    for i in range(N):
        if _max < _list[i]:
            cnt += 1
            _max = _list[i]
    return cnt

print(count_trophy(_list,N))
print(count_trophy(list(reversed(_list)),N))

▷ 왼쪽으로 볼 때는 리스트의 앞에서부터 판단하면 되지만, 오른쪽에서 볼 때는 리스트의 뒤에서부터 판단해야 했다.

   ▶ 이 때 reversed()를 이용해 리스트를 거꾸로 정렬하였다.

   ▶ 참고 : [Python] 리스트(배열) 순서 거꾸로 뒤집기

 

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

** 핵심 아이디어
1. 트로피를 왼쪽에서, 오른쪽에서 봤을 때 보이는 트로피의 수를 각각 구한다.
2. 트로피의 개수인 N의 최대는 50이므로 단순히 구현하면 된다.

 

def ascending(array):
    now = array[0]
    result = 1
    for i in range(1,len(array):
    	if now < array[i]:
            result += 1
            now = array[i]
        return result
        
n = int(input())
array = []

for _ in range(n):
    array.append(int(input()))
    
print(ascending(array))
array.reverse()
print(ascending(array))

 

 

문제 출처 : https://www.acmicpc.net/problem/1668

1668번: 트로피 진열