위에서 아래로
조건
- 첫번 째 줄에 수열에 속해 있는 수의 개수 N이 입력 ( N은 1 ~ 500 사이의 자연수)
- 둘째 줄부터 N+1번째 줄까지 N개의 수가 입력 (수의 범위 : 1이상 100,000이하 자연수)
1
2
3
4
5
6
7
8
입력 예시
3
15
27
12
출력 예시 : 내림차순 정렬
27 15 12
수의 개수가 500개 이하고, 수의 범위도 1이상 십만 이하의 자연수이기 때문에 어떠한 정렬 알고리즘을 써도 상관은 없다.
이럴땐, 그냥 라이브러리를 사용하는 것이 제일 편하다.
1
2
3
4
5
6
7
8
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
arr = sorted(arr, reverse=True)
print(arr)
성적이 낮은 순서로 학생 출력하기
입력 조건
- 첫번째 줄에 학생의 수 N이 입력 ( N은 1~100,000 사이의 정수)
- 두번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 설정을 나타내는 정수 B가 공백으로 구분되어 입력
- 문자열 A의 길이와 학생 성적은 모두 100이하의 자연수
1
2
3
4
5
6
7
입력 예시
2
홍길동 95
이순신 77
출력 예시 : 오름차순 정렬
이순신 홍길동
학생의 정보가 최대 십만명까지 가능하다는 점을 고려하면, 최악의 경우에는 십만명의 학생에 대한 정보를 정렬해야하는 상황에 직면할 수 있다. 이러한 점을 고려한다면 퀵정렬이나 계수정렬을 쓰는 것이 바람직하다.
다만, 입력예시가 단순하게 2개만 주어졌기 때문에 굳이 그렇게 하지 않고 간편하게 라이브러리를 사용해도 무관하다.
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
arr = []
for i in range(n):
input_data = input().split()
arr.append((input_data[0], int(input_data[1])))
arr = sorted(arr, key=lambda student: student[1])
for student in arr:
print(student[0], end=' ')
이 코드의 문법적 특징은 튜플로 (이름, 점수)를 묶은 후 점수를 기준으로 정렬을 수행한다는 점이다.
그리고 sorted 함수의 key 파라메터에 lambda를 사용하여 key값을 가지고 점수에 대한 정렬을 수행하였다는 특징도 가지고 있다.
두 배열의 원소 교체
입력 조건
- 첫 번째 줄에서 N, K가 공백으로 구분되어 입력( N은 1~100,000, K는 0~N)
- 두 번째 줄에서 배열 A의 원소들이 공백으로 구분되어 입력(모든원소는 10,000,000보다 작은 자연수)
- 세 번째 줄에서 배열 B의 원소들이 공백으로 구분되어 입력(모든원소는 10,000,000보다 작은 자연수)
1
2
3
4
5
6
7
입력 예시
5 3
1 2 5 4 3
5 5 6 6 5
출력 예시
26
N개의 원소를 가진 배열 두 개를 최대 K번 바꿔치기 연산을 수행하는 문제이다.
이 문제의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.
해결 방법은 배열 A에서 가장 작은 수를 찾아서 배열 B에서 가장 큰 수와 교환하는 것이다. 종료 조건은 배열 A에서 가장 작은수가 배열 B에서 가장 큰수보다 큰 경우이다.
이를 위해 배열 A는 오름차순으로 정렬하고, 배열 B는 내림차순으로 정렬한다. 그 후 인덱스 순서대로 차례로 비교하면서 바꿔치기 연산을 수행하도록 한다.
이 문제는 두 배열의 원소가 최대 십만개까지 입력될 수 있기 때문에, 퀵정렬이나 계수정렬을 사용하는 편이 좋다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n , k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
# 첫번째 인덱스부터 확인하여 두 배열의 원소를 최대 k번 비교
for i in range(k):
# 배열 A의 i번째 원소가 배열 B의 i번째 원소보다 작으면 교환
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
break
print(sum(a))