[이것이 코딩 테스트다] 정렬 - 국영수

YEAh·2021년 3월 16일

이것이 코딩 테스트다

목록 보기

20/39

정렬
데이터를 특정 기준에 따라서 순서대로 나열

선택 정렬 : 가장 작은 데이터를 선택

삽입 정렬 : 특정한 데이터를 적절한 위치에 삽입

퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈. 피벗(기준) 사용(ex. 리스트에서 첫 번째 데이터를 피벗으로 정한다)

계수 정렬(count sort) : 특정한 값을 가지는 데이터의 개수를 카운트하는 방법 (모든 범위를 담을 수 있는 크기의 리스트를 선언)

별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음

가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용

✅ 문제

학생 N명의 이름과 국어, 영어, 수학 점수가 주어집니다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하세요.

국어 접수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 옵니다.

입력 예시

12
Junkyu 50 60 100
SangKeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taewhan 50 60 90

출력 예시

Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Haebin
Junkyu
Soong
Taewhan

내가 작성한 파이썬 코드

(잘못된 코드..)
key 속성으로 여러 조건을 만족할 수 있다는 것을 모르고 짠 코드, 예시는 만족하는 데 어디에서 틀렸는지는 잘 모르겠다.

N = int(input())

array = []

for i in range(N):
    input_data = input().split()
    array.append((input_data[0], int(input_data[1]), int(input_data[2]), int(input_data[3])))

def setting_ko(data):
    return data[1]

def setting_en(data):
    return data[2]    

def setting_ma(data):
    return data[3]

def setting_name(data):
    return ord(data[0][0])

def sort_func(array,start_index, last_index, i):
    if i == 1:
        return sorted(array[start_index:last_index+1], key=setting_en)
    elif i == 2:
        return sorted(array[start_index:last_index+1], key=setting_ma, reverse=True)
    elif i == 3:
        return sorted(array[start_index:last_index+1], key=setting_name)

array = sorted(array, key=setting_ko, reverse=True)

start_index = 0
last_index = 0

for j in range(1, 4):
    if j == 1 or j == 2:
        for i in range(len(array)):
            if array[start_index][j] == array[i][j]:
                last_index = i
            else:
                array[start_index:last_index+1] = sort_func(array, start_index, last_index, j)
                start_index = last_index + 1
                last_index = start_index
        array[start_index:last_index+1] = sort_func(array, start_index, last_index, j)
    else:
        for i in range(len(array)):
            if array[start_index][1] == array[i][1] and array[start_index][2] == array[i][2] and array[start_index][3] == array[i][3]:
                last_index = i
            else:
                array[start_index:last_index+1] = sort_func(array, start_index, last_index, j)
                start_index = last_index + 1
                last_index = start_index
        array[start_index:last_index+1] = sort_func(array, start_index, last_index, j)
    start_index = 0
    last_index = 0

for i in range(len(array)):
    print(array[i][0])

설계

for문으로 조건을 하나씩 맞춰나간다. 그 전 조건을 만족한 범위를 알아내기 위해 start_index, last_index를 변수로 두었고, 그 범위 내에서 다음 조건을 만족시킨다.

➕ 문제 해설

N = int(input())

array = []

for i in range(N):
    input_data = input().split()
    array.append((input_data[0], int(input_data[1]), int(input_data[2]), int(input_data[3])))

array = sorted(array, key = lambda x: (-x[1], x[2], -x[3], x[0]))

for data in array:
    print(data[0])