4-2. 정렬 기출문제

Speedwell🍀·2022년 4월 5일

코딩테스트

이것이 코딩 테스트다

목록 보기

8/15

Q.23 국영수

난이도: ⭐
풀이시간: 20분
시간제한: 1초
메모리제한: 256MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/10825

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

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

입력조건

첫째 줄에 학생의 수 N(1 ≤ N ≤ 100,000)
둘째 줄부터 한 줄에 하나씩 각 학생의 이름/국어/영어/수학 점수가 공백으로 구분해 주어진다.
- 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수
- 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력조건

문제에 나와 있는 정렬 기준으로 정렬한 후 첫째 줄부터 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

<내가 푼 방식>

학생의 정보를 튜플로 저장해서 파이썬 정렬 라이브러리(sorted)에서 key를 기준으로 정렬하는 방식을 사용했다.

국어 점수가 같은 학생들끼리 한 리스트를 구성하게끔 했지만 시간이 오래 걸렸고, key로 정렬하는 과정이 너무 반복되어 비효율적이라 생각한다.

def korean(students_info):
    return students_info[1]

def english(students_info):
    return students_info[2]

def math(students_info):
    return students_info[3]

n = int(input())
students_info = []
result = []
high_korean = []
high_english = []


for i in range(n):
    student = input().split()
    student[1] = int(student[1])
    student[2] = int(student[2])
    student[3] = int(student[3])
    students_info.append(tuple(student))
    
high_korean = sorted(students_info, key=korean, reverse=True)

while len(result) != n:
    for i in range(1, len(high_korean)):
        if high_korean[i][1] != high_korean[i-1][1]:
            index = i
            break
    result.append(high_korean[0:index])
    del high_korean[0:index]
    
    for x in result:
        # 리스트 안에 국어 점수가 같은 튜플끼리 한 리스트 구성

<해설>

📍 실제 코딩 테스트에서 자주 활용되는 유형

📌 파이썬에서는 튜플을 원소로 하는 리스트가 있을 때, 그 리스트를 정렬하면 기본적으로 각 튜플을 구성하는 원소의 순서에 맞게 정렬된다!

예를 들어 튜플이 3개의 원소로 구성된다면 모든 원소가 첫 번째 원소의 순서에 맞게 정렬되고, 첫 번째 원소의 값이 같은 경우 두 번째 원소의 순서에 맞게 정렬되고, 거기에 두 번째 원소의 값까지 같은 경우 세 번째 원소의 순서에 맞게 정렬된다.

📌 리스트의 원소를 정렬할 때는 sort() 함수의 key 속성에 값을 대입하여 내가 원하는 '조건'에 맞게 튜플을 정렬시킬 수 있다는 점을 기억하자!

문제에서 요구하는 정렬 조건에 맞게 튜플을 정렬시키는 코드하면 아래와 같다.
students.sort(key = lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

n = int(input())
students = [] # 학생 정보를 담을 리스트

# 모든 학생 정보를 입력 받기
for _ in range(n):
    students.append(input().split())

'''
[ 정렬 기준 ]
1) 두 번째 원소를 기준으로 내림차순 정렬
2) 두 번째 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
'''
students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

# 정렬된 학생 정보에서 이름만 출력
for student in students:
    print(student[0])

Q.24 안테나

난이도: ⭐
풀이시간: 20분
시간제한: 1초
메모리제한: 256MB
기출: 2019 SW 마에스트로 입학 테스트
링크: https://www.acmicpc.net/problem/18310

일직선상의 마을에 여러 채의 집이 위치해 있다. 이 중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총합이 최소가 되도록 설치하려고 한다. 이때 안테나의 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 집의 수 N이 자연수로 (1≤N≤200,000)
둘째 줄에 N채의 집에 위치가 공백으로 구분되어 1 이상 100,000 이하의 자연수로

출력 조건

첫째 줄에 안테나를 설치할 위치의 값 출력
- 단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값 출력

# 입력예시
4
5 1 7 9

# 출력예시
5

예시에 대한 설명

5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로 최소가 된다.

<내가 푼 방식>

N채의 집 위치를 정렬한 후, 중간에 위치한 집을 선택한다. (중간에 위치한 집이 2개이면 더 작은 위치 값을 가지는 집 선택!)

n = int(input())
houses = list(map(int, input().split()))
result = 0

houses.sort()

if n % 2 == 0:
    idx = (n/2)-1
else:
    idx = n/2

result = houses[int(idx)]
print(result)

<해설>

📌 정확히 중간값(Median)에 해당하는 위치의 집에 안테나를 설치했을 때, 안테나로부터 모든 집까지의 거리의 총합이 최소가 된다.

n = int(input())
a = list(map(int, input().split()))
a.sort()

# 중간값(median)을 출력
print(a[(n - 1) // 2])

Q.25 실패율

난이도: ⭐
풀이시간: 20분
시간제한: 1초
메모리제한: 128MB
기출: 2019 카카오 신입 공채 1차
링크: https://programmers.co.kr/learn/courses/30/lessons/42889

게임의 신규 사용자 수가 급감했다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 크기 때문!

해결하기 위해 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 실패율을 구하는 코드를 완성하시오.

실패율
: 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨 있는 배열을 return 하도록 solution 함수를 완성하시오.

제한 사항

스테이지의 개수 N은 1 이상 500 이하의 자연수
stages의 길이는 1 이상 200,000 이하
stages에는 1 이상 N+1 이하의 자연수가 담겨있다.
- 각 자연수는 사용자가 현재 도전 중인 스테이지 번호
- 단, N+1은 마지막 스테이지(N번째 스테이지)까지 클리어한 사용자
만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의

기본 코드

def solution(N, stages):
	answer = []
    return answer

<내가 시도한 방법>

정렬할 때 key= 사용해야 될 것 같은데, 어떻게 하지...?

def solution(N, stages):
    answer = []
    temp = []
    for i in range(1,N+1):
        total = 0
        notclear = 0
        fail = 0
        for x in stages:
            if x >= i:
                total += 1
                if x == i:
                    notclear += 1
        fail = notclear / total
        temp.append((fail,i))
    temp.sort(reverse=True)
    return answer

아래처럼 했어야 했군!

temp.sort(key=lambda t:t[0], reverse=True)
answer = [i[1] for i in temp]

<해설>

스테이지 번호(i)를 1부터 N까지 증가시키며, 해당 단계에 머물러 있는 플레이어들의 수(count) 계산
count 정보를 이용하여 모든 스테이지에 따른 실패율을 계산한 뒤에 저장
실패율을 기준으로 내림차순 정렬 수행
- 전체 스테이지의 개수는 200,000 이하이기 때문에 기본적인 정렬 라이브러리 사용해서 O(NlogN) 시간

def solution(N, stages):
    answer = []
    length = len(stages)
    
    # 스테이지 번호를 1부터 N까지 증가시키며
    for i in range(1, N+1):
        # 해당 스테이지에 머물러 있는 사람의 수 계산
        count = stages.count(i)
        
        # 실패율 계산
        if length == 0:
            fail = 0
        else:
            fail = count / length
        
        # 리스트에 (스테이지 번호, 실패율) 원소 삽입
        answer.append((i, fail))
        length -= count
        
    # 실패율을 기준으로 각 스테이지를 내림차순 정렬
    answer = sorted(answer, key=lambda t: t[1], reverse=True)
    
    # 정렬된 스테이지 번호 출력
    answer = [i[0] for i in answer]
    return answer

Q.26 카드 정렬하기

난이도: ⭐⭐
풀이시간: 30분
시간제한: 2초
메모리제한: 128MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/1715

정렬된 두 묶음의 숫자 카드를 각각 A,B라 하면 보통 두 묶음을 합쳐서 하나로 만들 때는 A+B번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 있을 때, 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다.
예) 10장, 20장, 40장 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10+20)+(30+40)=100번의 비교가 필요하다. 이는 (10+40)+(50+20)=120번의 비교보다 효율적인 방법.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 N (1 ≤ N ≤ 100,000)
이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. (≤ 1,000)

출력

첫째 줄에 최소 비교 횟수

# 입력 예시
3
10
20
40

# 출력 예시
100

<내가 푼 방식>
너무 더럽게 푼 것 같다..

일단 작은 묶음끼리 비교해나가야 비교가 최소가 된다. 그래서 올림차순 정렬을 했다.

만약 n=4, 묶음이 10,20,30,40이라고 하면 (10+20)+(30+30)+(60+40)인데 이 계산을 (10+20+30+40)+(10+20)+(10+20+30)으로 생각해서 코드를 짰다.
즉 모든 묶음 개수를 합하고, n-3번째 인덱스까지의 묶음을 n-2번 합하고, n-2번째 인덱스를 합한다.

n = int(input())
cards = []
total = 0

for _ in range(n):
    cards.append(int(input()))
cards.sort()

if n==1:
    total = cards[0]
else:
    total += sum(cards)
    for i in range(0,n-2):
        total += cards[i] * (n-2)
    total += cards[-2]
print(total)

<해설>

📌항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해 보장
➡️ 이런 경우는 우선순위 큐가 효과적!
우선순위 큐는 원소를 삽입/삭제하는 과정에서 정렬이 되기 때문이다.

우선순위 큐는 힙 자료구조를 이용해서 구현할 수 있고, 파이썬에선 heapq 라이브러리를 사용하면 된다.

import heapq

n = int(input())
cards = []
total = 0

for _ in range(n):
    card = (int(input()))
    heapq.heappush(cards, card)

while len(cards) != 1:
    a = heapq.heappop(cards)
    b = heapeq.heappop(cards)
    sum_ab = a+b
    total += sum_ab
    heapq.heappush(cards, sum_ab)

print(total)

Speedwell🍀

이전 포스트

4-1. 정렬 개념 & 실전 문제

다음 포스트

4-2. 정렬 기출문제

이것이 코딩 테스트다

Q.23 국영수

Q.24 안테나

Q.25 실패율

Q.26 카드 정렬하기

4-1. 정렬 개념 & 실전 문제

5-1. 이진탐색 개념 & 실전 문제

0개의 댓글