[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter6(2). 정렬

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

 지난번 정렬 소스코드를 소개한 Chapter6(1)에 이어 코딩 테스트에서 출제되는 유형을 만나보겠습니다.

2021.05.21 - [Coding Test & Algorithm] - [이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter6(1). 정렬

[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter6(1). 정렬

 코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형을 나타낼 수 있다.

1. 정렬 라이브러리로 풀 수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬. 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택, 삽입, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

이 책에서는 이 3가지 유형을 모두 다룰 것이다. 이번 Chapter에서는 가장 기본적인 3문제를 풀어보자.

 

본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

6-10. 위에서 아래로

 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다.

이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

n = int(input()) # 3
cand_list = []
for i in range(n) :
    cand_list.append(int(input())) # 15 27 12

answer = sorted(cand_list, reverse=True)

for i in answer :
    print(i, end=' ') # 27 15 12

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

수의 개수가 500개 이하로 매우 적으며, 모든 수는 1 이상 100,000 이하이므로 앞서 공부한 정렬 중 어떠한 것을 사용해도 상관없지만, 코드가 간결해지는 기본 정렬 라이브러리를 이용하는 것이 효과적이다.

---

6-11. 성적이 낮은 순서로 학생 출력하기

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

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

n = int(input()) # 2
ans_list = [[] for _ in range(n)]
for i in range(n) :
    input_data = input().split() # 홍길동 95 이순신 77
    ans_list[i] = input_data[0], int(input_data[1])

ans_list = sorted(ans_list, key=lambda x : x[1])

for student in ans_list :
    print(student[0], end = ' ') # 이순신 홍길동

 이 문제에서는 학생의 정보가 최대 100,100개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하거나 O(N)을 보장하는 계수 정렬을 사용하면 된다. 그뿐 아니라 입력되는 데이터는 학생의 이름과 점수지만 출력할 때는 학생의 이름만 출력하면 되므로 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 한다.

 이 경우에도 마찬가지로 파이썬의 기본 정렬 라이브러리를 사용하는 것이 효과적이다.

 요즘 sort에 key, lambda를 이용한 문법을 잘 이용 중이다. 꽤 많은 도움이 된다.

---

6-12. 두 배열의 원소 교체

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

 

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

# 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1<=N<=100,000, 0<=k<=N)
n, k = map(int, input().split()) # N과 K를 입력받기
A = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기
B = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기

A = sorted(A) # 배열 A는 오름차순 정렬 수행
B = sorted(B, 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의 모든 원소의 합을 출력

---

 위와 같이 정렬 알고리즘을 이용한 문제들을 해결해보았습니다. 누군가에게 조금의 도움이 되는 글이었길 바랍니다.

Chapter7. 이진 탐색에서 뵙겠습니다. :)