14659번: 한조서열정리하고옴ㅋㅋ
첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이
www.acmicpc.net
처음 의식의 흐름대로 아래와같이 풀었다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
N = int(input())
archers = list(map(int, input().split()))
max_hunt_count = 0
for i in range(N):
mountain_height = archers[i]
hunt_count = 0
for j in range(i+1, N):
if mountain_height > archers[j]:
hunt_count += 1
max_hunt_count = max(hunt_count, max_hunt_count)
print(max_hunt_count)
|
cs |
시간초과. ㅎㅎ
더 높은 봉우리를 만났을때 용이 그대로 행동을 멈추기 때문에 break 추가
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
N = int(input())
archers = list(map(int, input().split()))
max_hunt_count = 0
for i in range(N):
mountain_height = archers[i]
hunt_count = 0
for j in range(i+1, N):
if mountain_height > archers[j]:
hunt_count += 1
else:
break
max_hunt_count = max(hunt_count, max_hunt_count)
print(max_hunt_count)
|
cs |
통과했지만, 972ms 라는 큰 시간이 소요되기도 했고, 어차피 무식하게 푼 다음 개선하려고 생각했기에 시간복잡도를 줄일 방법을 고민했다.
현재 봉우리가 이전 봉우리보다 낮은 경우, 용은 오른쪽으로만 이동할 수 있으므로 이전 봉우리보다 더 많은 적을 처치하는게 불가능하기에 순회할 필요가 없다. 또한 오른쪽에 남은 봉우리가 현재까지 최대 사냥 카운트보다 적다면, 남은 봉우리 전체를 사냥해도 기록은 바뀌지 않으므로 순회할 필요가 없다. 그래서 아래와 같이 조건문을 추가하였더니 시간이 대폭줄어 116ms
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
N = int(input())
archers = list(map(int, input().split()))
prev_mountain_height = 0
max_hunt_count = 0
for i in range(N-1):
mountain_height = archers[i]
hunt_count = 0
# 오른쪽에 남은 봉우리가 현재까지 최대 사냥 카운트보다 적다면, 남은 봉우리 전체를 사냥해도 기록은 바뀌지 않으니 비교할 필요가 없음
if N-i+1 < max_hunt_count:
continue
# 현재 봉우리가 이전 봉우리 보다 낮다면 용은 오른쪽으로만 이동할 수 있으므로 이전 봉우리보다 더 많은 적을 사냥할 수 없기 때문에 비교할 필요가 없음
if prev_mountain_height > mountain_height:
continue
else:
for j in range(i+1, N):
if mountain_height > archers[j]:
hunt_count += 1
else:
break
max_hunt_count = max(hunt_count, max_hunt_count)
prev_mountain_height = mountain_height
print(max_hunt_count)
|
cs |
그런데 이중 for 문이 영 맘에 들지 않아 좀 더 나은 방법을 고민해보니 아래와 같은 로직이 나왔다. 하지만 시간은 126ms 로 오히려 이중 for문 보다 더 많이 소요됐다.. 왜...왜지..? ;;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
N = int(input())
mountains = list(map(int, input().split()))
ans = 0
cnt = 0
max_mountain = 0
for mountain in mountains:
if mountain > max_mountain:
cnt = 0
max_mountain = mountain
else:
cnt+=1
ans = max(ans, cnt)
print(ans)
|
cs |
아주 순한맛이긴하지만 점진적으로 개선해나가는 맛이 있는 문제였다.
고수분들의 소요시간.. ㄷ ㄷ ㄷ ..
