이전 포스팅
실전문제 1. 위에서 아래로
<문제>
하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다.
<입력 조건>
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1 <= N <= 500
- 둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수
<출력 조건>
- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분해서 출력하면된다. 동일한 수는 순서상관없다.
<입력 예시>
3
15
27
12<출력 예시>
27 25 12
사고 과정
1. 저번까지 받던 입력이 아니라 엔터로 입력을 받는다.
2. 리스트에 입력을 받고 기본 정렬 라이브러리를 사용하는게 좋을 것 같다.
내 풀이
n=int(input())
array=[]
for i in range(n):
array.append(int(input()))
array.sort(reverse=True)
print(array)해설 풀이
# 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=' ')자체 피드백
아주 기본적인 정렬 문제지만 수의 개수가 500개 이하인 것과, 수의 범위에 대해 전혀 고려하지 않았던 점은 혼나야한다. 좀더 여러가지 상황을 고려하도록 하자.
그리고 출력 예시대로 출력을 해야함을 잘 인지하도록 하자.
실전문제 2. 성적이 낮은 순서로 학생 출력하기
<문제>
N명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다.
<입력 조건>
- 첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
- 두 번째 줄 부터 N+1 번째 줄 까지 학생의 이름 그리고 성적이 공백으로 주어진다. 학생이름 길이는 100이하, 성적은 100이하 자연수로 주어진다.
<출력 조건>
- 모든 학생의 이름을 성적이 낮은 순으로 출력하면된다. 동일한 성적은 자유롭게 출력하면된다.
<입력 예시>
2
홍길동 96
이순신 78<출력 예시>
이순신 홍길동
사고 과정
1. 성적순으로 정렬을 한 다음에 학생의 이름만 출력해야 하니까 sorted() 함수에 key를 추가하면 될 것 같다.
2. 학생수는 최대 100,000고, 학생의 성적은 100이하이므로 최악이 O(N^2)이면 안될것같다. 그럼 적어도 O(NlogN)을 보장하는 방법을 채용해야 할 것 같다.
3. 성적이 낮은 순서대로니까 오름차순으로 정렬하면 될 것 같다.
내 풀이
n = int(input())
array = []
for i in range(n):
array.append(tuple(input().split()))
array = sorted(array, key=lambda x: int(x[1]))
for i in range(n):
print(array[i][0], end=" ")해설 풀이
# 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=' ')자체 피드백
최악의 경우 O(NlogN)을 보장하는 알고리즘을 사용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬해야 한다. 입력을 받은 다음에 둘을 나눠서 저장하면 된다. 기본적으로 input().split()은 리스트로 저장된다. 그걸 잘 고려하도록 하자.
sorted() key에 람다함수를 사용하는 방법을 한번 다시 숙지하도록 하자.
실전문제 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이 되며, 이보다 더 합을 크게 만들 수는 없다
<입력 조건>
- 첫 번째 줄: N, K 가 공백으로 구분되어 입력 (1 <= N <= 100,000, 0 <= K <= N)
- 두 번째 줄: 배열 A의 원소들이 공백으로 구분되어 입력 (원소 a < 10,000,000인 자연수)
- 세 번째 줄: 배열 B의 원소들이 공백으로 구분되어 입력 (원소 b < 10,000,000인 자연수)
<출력 조건>
- 최대 K번 바꿔치기 연산을 수행해서 가장 최대의 합을 갖는 A의 모든 원소 값의 합을 출력
<입력 예시>
5 3
1 2 5 4 3
5 5 6 6 5<출력 예시>
26
사고 과정
1. N의 최대는 100,000, K의 최대는 100,000이다. 모든 원소는 10,000,000이하로 존재한다. 그럼 10,000,000의 수를 100,000번 더한게 모든 원소의 합이라면 1,000,000,000,000이 답이 되는데 이러면 문제가 되는거 아닌가..?
2. A 배열의 최솟값을 찾고, B 배열의 최댓값을 찾고, 그 둘을 비교해서 B 배열의 값이 더 크다면 두 배열의 원소를 교체하는 작업을 진행하면 된다. 해당 작업을 K번 진행하면 된다. 이거 정렬이랑 관계있나..?
3.
내 풀이
n, k = map(int, input().split())
cnt = k
i = 0
arrayA = list(map(int, input().split()))
arrayB = list(map(int, input().split()))
arrayA.sort()
arrayB.sort(reverse=True)
while cnt != 0:
if i==len(arrayA):
break
if arrayA[i] < arrayB[i]:
arrayA[i], arrayB[i] = arrayB[i], arrayA[i]
i += 1
cnt -= 1
print(sum(arrayA))해설 풀이
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의 모든 원소의 합을 출력자체 피드백
배열 A와 B의 정보가 입력되면 배열 A의 원소를 오름차순으로 정렬하고 배열 B의 원소를 내림차순으로 정렬한다. 그리고 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.
여러모로 내장 함수를 잘 활용한 것 같다.
하지만 처음부터 정렬이 필요한 부분을 찾아내는 연습은 좀더 필요해 보인다.
