Ch6 Sorting 6-2

⚡ [문제 1] 위에서 아래로

• 난이도: 🌕
• 풀이시간: 15분
• 시간 제한: 1초
• 메모리 제한: 128MB
• 기출: T 기업 코딩 테스트

[문제]

수열을 내림차순으로 정렬하는 프로그램을 만드시오.

[입력 조건]

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

[출력 조건]

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

# 입력 예시
3
15
27
12

# 출력 예시
27 15 12

[문제 해설]

1. 가장 기본적인 정렬을 할 수 있는지 물어보는 문제

2. 수의 개수가 500개 이하로 매우 적으며, 모든 수는 1 이상 100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 가능

파이썬의 기본 정렬 라이브러리 사용하는 것이 효과적

# 교재 풀이

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

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

# 파이썬 기본 정렬 라이브러리를 이용해 정렬 수행
array = sorted(array, reverse=True)

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

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

• 난이도: 🌕
• 풀이시간: 20분
• 시간 제한: 1초
• 메모리 제한: 128MB
• 기출: D 기업 프로그래밍 콘테스트 예선

[문제]

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 성적으로 구분된다.

각 학생의 이름과 성적이 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

[입력 조건]

• 첫 번째 줄에 학생의 수 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):
  input_data = input().split()
  # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
  array.append((input_data[0], int(input_data[1])))

# 키(Key)를 이용하야, 점수를 기준으로 정렬
array = sorted(array, key=lambda student: student[1])

# 정렬이 수행된 결과 출력
for student in array:
  print(student[0], end=' ')

⚡ [문제 3] 두 배열의 원소 교체

• 난이도: 🌕
• 풀이시간: 20분
• 시간 제한: 1초
• 메모리 제한: 128MB
• 국제 알고리즘 대회

[문제]

두 배열 A, B는 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.

N, K, 배열 A & B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

[입력 조건]

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

[출력 조건]

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

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

# 출력 예시
26

[문제 해설]

• 핵심 아이디어: 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체한다
• 가장 먼저 배열 A와 B가 주어지면 A에 대하여 오름차순 정렬하고, B에 대하여 내림차순 정렬한다
• 이후에 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 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의 원소보다 크거나 같을 때, 반복문을 탈출
        break

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

🍀 회고

건강이 안좋아져 깊게 파지는 못했지만 기본 라이브러리 정렬은 자주 써서 익숙했으며, 다른 퀵정렬과 특별한 상황인 계수정렬까지는 문제를 풀면서 가져가야 한다고 생각한다.