📝문제1. 위에서 아래로
- 문제
하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.
입력 조건
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 <= N <= 500)
- 둘째 줄부터 N+1 번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.
출력 조건
- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.
입력 예시
3
15
27
12
출력 예시
27 15 12
- 나의 코드💻
n = int(input())
array = []
for i in range(n):
array.append(int(input()))
array.sort(reverse=True)
for i in array:
print(i, end=" ")-> 맞았다!
- 정답 코드💻
n = int(input())
array = []
for i in range(n):
array.append(int(input()))
array = sorted(array, reverse=True)
for i in array:
print(i, end=" ")- 비교 분석📖
이 문제는 가장 기본적인 정렬을 할 수 있는지 물어보는 문제이다. 수의 개수가 500개 이하로 매우 적으며, 모든 수는 1 이상 100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 문제를 해결할 수 있다. 정렬을 아무거나 이용해도 상관없지만 가장 코드가 간결해지는 파이썬의 기본 정렬 라이브러리를 이용하는 것이 효과적이다.
📝문제2. 성적이 낮은 순서로 학생 출력하기
- 문제
N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
입력 조건
- 첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
- 두 번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.
출력 조건
- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의순서는 자유롭게 출력해도 괜찮다.
입력 예시
2
홍길동 95
이순신 77
출력 예시
이순신 홍길동
- 나의 코드💻
n = int(input())
array = []
for i in range(n):
array.append(list(input().split()))
def setting(data):
return data[1]
array = sorted(array, key=setting)
for i in array:
print(i[0], end=" ")- 정답 코드💻
n = int(input())
array = []
for i in range(n):
input_data = input().split()
# 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
array.append((input_data[0], input_data[1]))
# 키를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key = lambda student: student[1])
for i in array:
print(i[0], end=" ")- 비교 분석📖
이 문제에서는 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. 그뿐만 아니라 입력되는 데이터는 학생의 이름과 점수지만 출력할 때는 학생의 이름만 출력하면 되므로 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 한다. 따라서 이런 경우에도 마찬가지로 파이썬의 기본 정렬 라이브러리를 사용하는 것이 효과적이다.
lambda 문법이 나는 아직 미숙한 것 같다. 좀 더 잘 활용할 수 있도록 공부해야겠다.
📝문제3. 두 배열의 원소 교체
- 문제
동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다.
N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라.
예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자
- 배열 A = [1, 2, 5, 4, 3]
- 배열 B = [5, 5, 6, 6, 5]
이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다.
- 연산 1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
- 연산 2) 배열 A의 원소 '2'와 배열 B의 원소 '6'을 바꾸기
- 연산 3) 배열 A의 원소 '3'과 배열 B의 원소 '5'를 바꾸기
세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다.
- 배열 A = [6, 6, 5, 4, 5]
- 배열 B = [3, 5, 1, 2, 5]
이때 배열 A의 모든 원소의 합은 26이 되며, 이보다 더 합을 크게 만들 수는 없다. 따라서 이 예시의 정답은 26이 된다.
입력 조건
- 첫 번째 줄에 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
- 나의 코드💻
[첫 번째 코드]
n, k = map(int, input().split())
array_one = list(map(int, input().split()))
array_two = list(map(int, input().split()))
array_one.sort()
array_two.sort(reverse=True)
for i in range(k):
array_one[i], array_two[i] = array_two[i], array_one[i]
print(sum(array_one))[두 번째 코드]
n, k = map(int, input().split())
array_one = list(map(int, input().split()))
array_two = list(map(int, input().split()))
array_one.sort()
array_two.sort(reverse=True)
for i in range(k):
if array_one[i] < array_two[i]:
array_one[i], array_two[i] = array_two[i], array_one[i]
print(sum(array_one))
- 정답 코드💻
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
break
print(sum(a))- 비교 분석📖
문제를 해결하기 위한 기본 아이디어는 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다. 단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행해야 한다. 이러한 과정을 K번 반복하면 원하는 정답을 얻을 수 있다.
따라서 A와 B의 정보가 입력되면 배열 A의 원소를 오름차순으로 정렬하고, 배열 B의
원소를 내림차순으로 정렬한다. 그리고 두 배열의 원소를 가장 첫 번째 인덱스부터 차례대로 비교하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다. 이때 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.
-> 입출력 예시가 하나밖에 없고, 문제를 제대로 읽지 않아서
"단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행해야 한다."
이 조건을 미처 파악하지 못했다. 해설을 보다 잘못된 것을 깨닫고 다시 수정하였다. 그런데 다시 수정한 코드에서는 else와 관련된 문장을 놓쳤다.
-> 또한 시간 복잡도와 관련된 이런 조건들을 어떻게 파악해야 할 지 아직 잘 모르겠다.
"이때 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다."
'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 이코테 유튜브 강의 영상을 기반으로 작성한 글입니다.
안녕하세요, 김덕우입니다. 꼼꼼한 포스팅 항상 잘 읽고 있습니다. 내 풀이와 답안을 비교분석하는 거 정말 좋은 것 같아요. 수고하셨습니다!!