[브론즈 1] 14659번: 한조서열정리하고옴ㅋㅋ

Original Source: https://www.acmicpc.net/problem/14659

14659번: 한조서열정리하고옴ㅋㅋ

---

문제

“반갑다. 내 이름은 반고흐#31555! 조선 최고의 활잡이지. 오늘도 난 금강산 위에서 적들을 노리고 있지. 내 앞에 있는 적들이라면 누구도 놓치지 않아! 좋아, 이제 곧 월식이 시작되는군. 월식이 시작되면 용이 적들을 집어삼킬 것이다. 잘 봐두어라! 마장동 활잡이 반고흐#31555님의 실력을-!”

반고흐#31555는 자기 뒤쪽 봉우리에 덩기#3958이 있음을 전혀 모르고 있었다. 덩기#3958도 반고흐#31555와 마찬가지로 월식이 시작되면 용을 불러내어 눈앞에 있는 다른 활잡이들을 모두 처치할 생각이다. 사실, 반고흐#31555와 덩기#3958 뿐만 아니라 금강 산맥의 N개 봉우리에 있는 모든 활잡이들이 같은 생각을 가지고 있다.

반고흐#31555가 있는 금강 산맥에는 총 N개의 봉우리가 있고, 모든 봉우리마다 한 명의 활잡이가 서서 월식이 시작되기만을 기다리고 있다. 다만, 애석하게도, 천계에 맥도날드가 생겨 용들이 살이 찐 탓에 용들은 자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있게 되었다. 또한 용들은 처음 출발한 봉우리보다 높은 봉우리를 만나면 그대로 공격을 포기하고 금강산자락에 드러누워 낮잠을 청한다고 한다. 봉우리의 높이는 모두 다르고 모든 용들은 오른쪽으로만 나아가며, 중간에 방향을 틀거나, 봉우리가 무너지거나 솟아나는 경우는 없다.

“달에 마구니가 끼었구나.”

드디어 월식이 시작됐다! 과연 이들 활잡이 중 최고의 활잡이는 누구일까? 최고의 활잡이가 최대 몇 명의 적을 처치할 수 있는지 알아보자.

입력

첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 유일하다.

출력

최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력한다.

---

사고의 흐름

• 리스트로 Input을 받은 다음 순회하면서 오른쪽 봉우리가 더 낮으면 처치 카운트를 올리고, 더 높으면 카운트를 초기화한 후 다시 세면 되겠다.
• 정렬 알고리즘을 작성할 때처럼 최댓값 변수를 따로 만들어서, 카운트와 최댓값을 비교하면서 카운트가 최댓값보다 더 높으면 최댓값 변수를 업데이트하면 되겠다.

 

• 바로 오른쪽 봉우리와 값을 비교하면 인접한 두 봉우리의 높이만 비교하게 되니까, 이건 틀린 접근이네. 높은 봉우리의 값을 저장해 놓고 비교하는 게 맞는 방법이다.
• 높은 봉우리의 값을 저장하는 게 아니라, 높은 봉우리의 인덱스를 저장해야겠다. N의 값이 작으니까 이중 반복문을 써도 될 것 같다.
• 이중 반복문이 아니지. 높은 봉우리의 인덱스는 리스트를 순회하는 게 아니니까. 더 높은 봉우리가 나오면 그 위치의 인덱스로 업데이트만 해 주면 되겠지.

 

• 왜 틀렸지? 리스트 끝을 순회할 때 무언가 오류가 생겼나?
• 최댓값 변수를 오른쪽에 더 높은 봉우리가 나올 때만 업데이트하면, 끝까지 더 낮은 봉우리만 나올 때 업데이트가 안 되어서 문제가 생긴다. 그냥 반복문을 반복할 때마다 업데이트를 해줘야겠다.
• 그런데 반복문을 반복할 때마다 업데이트를 하면, 더 높은 봉우리가 나왔을 때 킬 카운트가 초기화되면서 최댓값에 킬 카운트가 반영되지 않는 문제가 발생한다. 그러면 더 높은 봉우리가 나왔을 때랑 리스트 끝에 도달했을 때 두 경우를 나눠서 다뤄줘야 하는 건가?
• 그러면 반복문을 탈출한 후 조건문을 한번 더 써서 최댓값을 업데이트해줘야겠다.

내가 작성한 소스코드

import sys

n = int(sys.stdin.readline().rstrip())
peaks = list(map(int, sys.stdin.readline().split()))

kill_cnt = 0; max_kill = 0; high = 0
for i in range(1, n):    
    if peaks[high] > peaks[i]:
        kill_cnt += 1
    elif peaks[high] < peaks[i]:
        if max_kill < kill_cnt: max_kill = kill_cnt
        kill_cnt = 0
        high = i

if max_kill < kill_cnt: max_kill = kill_cnt
    
print(max_kill)

남이 작성한 소스코드

bconfiden2 님:
https://www.acmicpc.net/source/47740483

피드백

• 파이썬에서는 in 연산자를 사용해 배열 안의 원소를 인덱싱하지 않고 직접 순회할 수 있다.
• max() 메서드를 이용하면 조건문을 사용하지 않고도 최댓값을 뽑아낼 수 있다.