04-5. 정렬 문제풀이

📝문제1. 백준 2751번(수 정렬하기2)

- 문제

https://www.acmicpc.net/problem/2751

문제

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

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력
5
5
4
3
2
1
예제 출력
1
2
3
4
5

- 나의 코드💻

n = int(input())
array = []
for i in range(n):
    array.append(int(input()))
array.sort()
for i in array:
    print(i)

-> 시간초과

from sys import stdin

n = int(stdin.readline())
array = []
for i in range(n):
    array.append(int(stdin.readline()))
array.sort()
for i in array:
    print(i)

-> 성공,,!

- 비교 분석📖

from sys import stdin 을 사용하니 시간초과를 해결할 수 있었다.

다른 블로그 글을 읽어보니 pypy로 바꾸는 방법, 병합 정렬을 사용하는 방법 등이 있었다. 시간복잡도 관련해서는 아직 감이 잘 오지 않는다.

---

📝문제2. 백준 10989번(수 정렬하기3)

- 문제

https://www.acmicpc.net/problem/10989

문제

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

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

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력
10
5
2
3
1
4
2
3
5
1
7
예제 출력
1
1
2
2
3
3
4
5
5
7

- 나의 코드💻

from sys import stdin

n = int(stdin.readline())
array = []
for i in range(n):
    array.append(int(stdin.readline()))
array.sort()
for i in array:
    print(i)

-> 메모리 초과

- 정답 코드💻

from sys import stdin
n = int(stdin.readline())

# 빈도를 저장하기 위한 배열
array = [0 for _ in range(10001)]

# 입력받은 수가 몇 번 들어있는지 빈도 저장
for _ in range(n):
    num = int(stdin.readline())
    array[num] += 1

# 배열의 시작부터 돌며 저장된 빈도만큼 인덱스값 출력
for i in range(1, 10001):
    count = array[i]
    for _ in range(count):
        print(i)

- 비교 분석📖

-> 첫 번째 문제인 '수 정렬하기2'과 비교해보면 n이 1,000,000에서 10,000,000으로 늘어났다. 또한 메모리 제한이 256MB에서 8MB로 줄어들었다.

메모리 제한이 있기 때문에 계수정렬을 이용해 풀어야 한다고 한다. 원소끼리 비교하는 것이 아니라 원소가 몇 번 등장하는지 개수를 세는 방법이기 때문에 다른 정렬에 비해 일반적으로 빠르다고 한다.

개념 정리
https://velog.io/@ji-vvon/04.-%EC%A0%95%EB%A0%AC#%EF%B8%8F4-%EA%B3%84%EC%88%98-%EC%A0%95%EB%A0%AC

참고 블로그
https://yuuj.tistory.com/105

---

📝문제3. 백준 1572번(중앙값)

- 문제

https://www.acmicpc.net/problem/1572

문제
중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다.

오세준은 1초에 온도를 하나씩 재는 온도계를 만들었다. 이 온도계에는 작은 디스플레이 창이 하나 있는데, 이 창에는 지금부터 최근 K초 까지 온도의 중앙값을 표시해 준다. (온도를 재기시작한지 K초부터 표시한다. 그 전에는 아무것도 출력되지 않는다.)

오세준은 온도를 N초동안 쟀다. 그 시간 동안 온도계의 디스플레이 창에 뜨는 숫자의 합을 구하는 프로그램을 작성하시오.

다른 말로 하면, 길이가 N인 수열이 주어진다. 이 수열은 N-K+1 개의 길이가 K인 연속된 부분 수열이 존재한다. 이 부분 수열의 중앙값의 합을 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 주어진다. N은 250,000보다 작거나 같은 자연수이고, K는 5,000보다 작거나 같은 자연수이다. N은 항상 K보다 크거나 같다. 둘째 줄부터 N개의 수가 한 줄에 하나씩 주어진다. 입력으로 주어지는 수는 65536보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 정답을 출력한다. 정답은 263-1보다 작거나 같다.

예제 입력
10 3
3
4
5
6
7
8
9
10
11
12
예제 출력
60

- 나의 코드💻

코드를 입력하세요

- 정답 코드💻

코드를 입력하세요

- 비교 분석📖

---

📝문제4. 백준 2108번(통계학)

- 문제

https://www.acmicpc.net/problem/2108

문제
수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

• 산술평균 : N개의 수들의 합을 N으로 나눈 값
• 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
• 최빈값 : N개의 수들 중 가장 많이 나타나는 값
• 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

• 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
• 둘째 줄에는 중앙값을 출력한다.
• 셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
• 넷째 줄에는 범위를 출력한다.

예제 입력 1
5
1
3
8
-2
2
예제 출력 1
2
2
1
10

예제 입력 2
1
4000
예제 출력 2
4000
4000
4000
0

예제 입력 3
5
-1
-2
-3
-1
-2
예제 출력 3
-2
-2
-1
2

- 나의 코드💻

from sys import stdin
n = int(stdin.readline())
array = []
many = []

for _ in range(n):
    array.append(int(stdin.readline()))
array.sort()

# 1. 산술평균
print(sum(array) / n)

# 2. 중앙값
print(array[(n - 1) // 2])

# 3. 최빈값

# 4. 범위
print(max(array) - min(array))
# print(array[n-1] - array[0])

- 정답 코드💻

from sys import stdin
from collections import Counter
n = int(stdin.readline())
array = []

for _ in range(n):
    array.append(int(stdin.readline()))
array.sort()

# 1. 산술평균
print(round(sum(array) / n))

# 2. 중앙값
print(array[(n - 1) // 2])

# 3. 최빈값
many = Counter(array).most_common() # 반환값 : (수, 횟수)
if len(many) > 1 and many[0][1] == many[1][1]: # 최빈값이 두 개 이상인 경우
    print(many[1][0])
else: # 최빈값이 한 개인 경우
    print(many[0][0])

# 4. 범위
print(max(array) - min(array))

- 비교 분석📖

• 반올림
  round(n) : n의 소수점 첫번째 자리를 반올림하여 나타낸다.
  round(n, m) : n을 소수점 m번째 자리까지만 표현하고 반올림하여 나타낸다.

• 최빈값
  from collections import Counter
  Counter(배열).most_common : 데이터의 개수가 많은 순으로 정렬된 배열을 리턴한다.
  collections.Counter(배열) : 배열에서 요소들의 개수를 세어, 딕셔너리 형태로 반환한다. ({문자 : 개수} 형태)