https://www.acmicpc.net/problem/14659
14659번: 한조서열정리하고옴ㅋㅋ
첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 N이 100,000이기 때문에 이중 for문을 이용해서 풀게 되면 O(N^2) = 10,000,000,000 번의 연산을 최악의 경우 수행하게 됩니다. 따라서 이 문제의 경우 python3으로 이중 for문을 이용하면 제한시간 2초내에 풀 수 없습니다. (다만 pypy3로 제출하면 정답판정을 받게 되는데 데이터의 추가가 필요해 보입니다.) 따라서 이 문제는 O(N)으로 해결해야 하는 문제 입니다. 따라서 한번의 반복문으로 해결할 수 있는 방법을 찾아야 합니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
n = int(input())
data = list(map(int, input().split()))
height = data[0]
ans = []
count = 0
for i in range(1, n):
if data[i] < height:
count += 1
else:
height = data[i]
ans.append(count)
count = 0
ans.append(count) # 내림차순으로 정렬된 경우
print(max(ans))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 14499번: 주사위 굴리기(Python) (0) | 2022.01.10 |
|---|---|
| 백준 알고리즘 2941번: 크로아티아 알파벳(Python) (0) | 2022.01.07 |
| 백준 알고리즘 1080번: 행렬(Python) (0) | 2022.01.06 |
| 백준 알고리즘 1946번: 신입 사원(Python) (0) | 2022.01.06 |
| 백준 알고리즘 11866번: 요세푸스 문(Python) (0) | 2022.01.06 |