정렬 알고리즘 기본 문제

출처: [이것이 취업을 위한 코딩테스트다 - 나동빈 저](https://ridibooks.com/books/443000825
배너: godori님이 만드신 배너 메이커 활용

---

문제 1) 위에서 아래로

풀이 시간: 15분, 시간 제한: 1분, 메모리 제한: 128MB

입력 조건
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 <= N <= 500)
- 둘째 줄부터 N + 1 번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.

입력 예시:
3
15
27
12

출력 조건
- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.

출력 예시:
27 15 12

문제 해설

• 가장 기본적인 정렬을 수행할 수 있는지 물어보는 문제
• 수의 개수가 500개 이하, 모든 수의 범위가 1 ~ 100,000 이므로 어떤 정렬 알고리즘을 사용해도 해결 가능
• 가장 코드가 간결해지는 파이썬 기본 라이브러리를 이용하는 것이 가장 효과적

소스 코드

# N 을 입력 받기
n = int(input())

# N개의 정수를 입력받아 리스트에 저
array = []
for i in range(n):
    array.append(int(input()))

# 파이썬 기본 정렬 라이브러리를 사용해서 정렬 수행
array.sort(reverse=True)

# 정렬이 수행된 결과를 출
for i in range(n):
    print(array[i], end=' ')

문제 2) 성적이 낮은 순서로 학생 출력하기

풀이 시간: 20분, 시간 제한: 1초, 메모리 제한: 128MB

입력 조건
- 첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
- 두 번째 줄부터 N + 1 번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

입력 예시:
2
홍길동 95
이순신 77

출력 조건
- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

출력 예시:
이순신 홍길동

문제 해설

• 학생 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나, O(N)을 보장하는 계수 정렬을 이용하면 된다.
• 학생 정보를 튜플로 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬 수행
• 파이썬 기본 정렬 라이브러리를 사용하는 것이 효과적

소드 코드

# N을 입력받기
n = int(input())

# N명의 학생 정보를 입력받아 리스트에 저
array = []
for i in range(n):
    student = input().split()
    # 이름은 문자열 그대로, 점순느 정수형으로 변환하여 저장
    array.append((student[0], int(student[1])))

# 점수를 기준으로 오름차순 정렬 (Key 이용)
array.sort(key = lambda x: x[1])

# 정렬된 결과에 점수서가 낮은 순으로 이름 출력
for i in range(n):
    print(array[i][0], end=' ')

문제 3) 두 배열의 원소 교체

풀이 시간: 20분, 시간 제한: 2초, 메모리 제한: 128MB

입력 조건
- 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다.(1 <= N <= 100,000, 0 <= K <= N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예시:
5 3
1 2 5 4 3
5 5 6 6 5

출력 조건
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

출력 예시:
26

문제 해설

• 가장 기본적인 아이디어는 매번 배열 A에서 가장 작은 원소를 골라서 배열 B에서 가장 큰 원소와 교체하는 것이다. (단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체 수행)
• 따라서 배열 A의 원소를 오름차순으로, 배열 B의 원소를 내림차순으로 정렬한다.
• 그리고 두 배열의 원소를 가장 첫 번째 인덱스부터 차례대로 비교하면서 배열 A의 원소가 배열 B의 원소보다 작을 때만 교체를 수행한다. (최대 K번)
  - 반복문 수행 도중 배열 A의 원소가 배열 B의 원소보다 크거나 같을 경우 반복문 탈출
• 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.

소스 코드

n, k = map(int, input().split()) # N, K 입력받기
a = list(map(int, input().split())) # 배열 A의 모든 원소 입력받기
b = list(map(int, input().split())) # 배열 B의  모든 원소 입력받기


a.sort() # 배열 A는 오름차순 정렬
b.sort(reverse=True) # 배열 B는 내림차순 정렬

# 첫 번째 인덱스부터 시작하여, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
        # 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문 탈출
        print(i)
        break

print(sum(a)) # 배열 A의 모든 원소의 합 출력