[2학기 3주차] 수 정렬하기 3, 수열

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

---

 

import sys

count_list = [0] * 10001
N = int(sys.stdin.readline())

for _ in range(N):
    num = int(sys.stdin.readline())
    count_list[num] += 1

for i in range(10001):
    if count_list[i] > 0:
        for _ in range(count_list[i]):
            sys.stdout.write(str(i) + '\n')

 

1. 빠른 입출력을 위해 import sys

2. 입력받는 수의 최댓값이 10000이므로 각 숫자의 등장 횟수를 세기위해 크기가 10001인 리스트를 만들고 모든 값을 0으로 초기화한다.

3. 수의 개수를 입력을 받아서 정수형으로 N에 저장한다.

4. N번 반복문을 돌면서 하나씩 숫자를 입력받아 정수형태로 변환해 num이라한다. 그후 해당 인덱스값에 1더한다.

5. [10000]까지 반복한다. 리스트의 인덱스가 0이상이면(해당 숫자 i가 한번이라도 등장했다면) count_list[i]에 기록된 횟수만큼 해당 i를 출력한다. i를 문자열로 변환하고 줄바꿈문자와 함께 출력한다.

 

+) 메모리제한때문에 sort()는 할 수 없다.

일반적인 정렬 알고리즘(병합정렬, 퀵정렬 등)은 시간 및 메모리 제한을 초과할 수 있다.

따라서 계수 정렬로 문제를 푸는 것이 가장 적합하다.

 

---

 

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

---

import sys

N, K = map(int, sys.stdin.readline().split())
temperatures = list(map(int, sys.stdin.readline().split()))

current_sum = sum(temperatures[:K])
max_sum = current_sum

for i in range(K, N):
    current_sum = current_sum - temperatures[i - K] + temperatures[i]
    if current_sum > max_sum:
        max_sum = current_sum

print(max_sum)

 

1. 입력받은 수를 정수로 변환하여 공백을 기준으로 나눠서 N, K에 저장한다.

2. 입력받은 것을 각각 정수로 변환해 temperatures라는 리스트에 저장한다.

3. current_sum은 temperatures의 0번째부터 k번째 인덱스까지 더한 값이다.

4. current_sum을 max_sum에 저장한다.

5. K부터 N-1까지 반복한다. current_sum은 이전 current_sum에서  i-k번째 온도(가장 이전온도)를 빼고  i번째 온도(가장 최근 온도)를 더한 값이다.

6. 만약 current_sum이 max_sum보다 크면 current_sum을 max_sum이라 한다.

7. 최종적으로 max_sum을 출력한다.