코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
앞서 공부한 그리디 알고리즘과 [Python] 정렬 함수(sort, sorted)을 사용해 전국 대회 선발 고사 문제를 풀어보겠다.
0번부터 n - 1번까지 n명의 학생 중 3명을 선발하는 전국 대회 선발 고사를 보았습니다. 등수가 높은 3명을 선발해야 하지만, 개인 사정으로 전국 대회에 참여하지 못하는 학생들이 있어 참여가 가능한 학생 중 등수가 높은 3명을 선발하기로 했습니다.
각 학생들의 선발 고사 등수를 담은 정수 배열 rank
와 전국 대회 참여 가능 여부가 담긴 boolean 배열 attendance
가 매개변수로 주어집니다. 전국 대회에 선발된 학생 번호들을 등수가 높은 순서대로 각각 a, b, c번이라고 할 때 10000 × a + 100 × b + c를 return 하는 solution 함수를 작성해 주세요.
rank
의 길이 = attendance
의 길이 ≤ 100rank[i]
는 i
번 학생의 선발 고사 등수를 의미합니다.rank
의 원소는 1부터 n까지의 정수로 모두 서로 다릅니다.attendance[i]
는 i
번 학생의 전국 대회 참석 가능 여부를 나타냅니다.attendance[i]
가 true라면 참석 가능, false면 참석 불가능을 의미합니다.attendance
의 원소 중 적어도 3개는 true입니다.rank | attendance | result |
---|---|---|
[3, 7, 2, 5, 4, 6, 1] | [false, true, true, true, true, false, false] | 20403 |
[1, 2, 3] | [true, true, true] | 102 |
[6, 1, 5, 2, 3, 4] | [true, false, true, false, false, true] | 50200 |
예제 1번에서 1등은 6번 학생이지만 전국 대회에 참석 불가능하므로 넘어갑니다. 2등은 2번 학생이고 전국 대회에 참석 가능하므로 1순위로 선발됩니다. 3등은 0번 학생이고 전국 대회에 참석 불가능 하므로 넘어갑니다. 4등과 5등은 각각 4번, 3번 학생이고 두 학생 모두 전국 대회에 참석 가능하므로 각각 2순위, 3순위로 선발됩니다. 3명을 선발하였으므로 6등과 7등은 확인하지 않아도 됩니다. 따라서 10000 × 2 + 100 × 4 + 3 = 20403을 return 합니다.
예제 2번에서 1, 2, 3등은 각각 0번, 1번, 2번 학생이고 세 학생 모두 전국 대회에 참석 가능하므로 각각 1순위, 2순위, 3순위로 선발됩니다. 따라서 10000 × 0 + 100 × 1 + 2 = 102를 return 합니다.
예제 3번에서 1, 2, 3등은 각각 1번, 3번, 4번 학생이지만 세 학생 모두 전국 대회에 참석 불가능합니다. 다음으로 4, 5, 6등은 각각 5번, 2번, 0번 학생이고 세 학생 모두 전국 대회에 참석 가능하므로 각각 1순위, 2순위, 3순위로 선발됩니다. 따라서 10000 × 5 + 100 × 2 + 0 = 50200을 return 합니다.
def solution(rank, attendance):
n = len(rank)
answer =0
r_a = []
for i in range(n):
if attendance[i]:
r_a.append([rank[i], i])
r_a.sort(key = lambda v : v[0])
return 10000 * r_a[0][1] + 100 * r_a[1][1] + r_a[2][1]
먼저 최적의 답을 찾는 방법(그리디 알고리즘)을 생각해본다.
내가 생각한 방법은 아래와 같다.
False인 것을 제외
한 후, 등수와 번호
을 묶어서 중첩 리스트
로 저장rank를 기준으로 오름차순
정렬하고 상위권 등수 3명의 index를 가지고 return
위의 방법으로 코드를 작성했다.
1. attendance가 True
인 학생의 경우에만 r_a 리스트에 [등수, 번호]
형태로 저장
2. sort()
를 이용해 등수를 기준으로 좌표 정렬
3. 그 결과 r_a
에 있는 학생들은 전부 참석
한 학생이며, 등수를 기준으로 오름차순으로 정렬되어 있음
4. 따라서 인덱싱을 이용해 return