[Programmers] #181851 - 전국 대회 선발 고사 [Java][C++][Python]

문제 링크

---

1. 아이디어

학생의 등수를 담은 배열 rank와 참여 여부를 담은 배열 attendance가 주어진다. 참석 가능한 학생만 계산에 포함되므로 먼저 참석 가능한 학생의 등수와 위치를 배열에 담은 후 이를 정렬했다. 등수가 높은 3명이 계산에 포함되는 3명이고 3명의 위치를 같이 저장했으므로 이를 통해 계산을 수행 후 반환하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log N)$	$O(N)$

($N$ = rank의 길이 = attendance의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(int[] rank, boolean[] attendance) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < rank.length; i++) {
            if (attendance[i]) list.add(new int[]{rank[i], i});
        }
        list.sort((o1, o2) -> Integer.compare(o1[0], o2[0]));

        return 10000 * list.get(0)[1] + 100 * list.get(1)[1] + list.get(2)[1];
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> rank, vector<bool> attendance) {
    vector<pair<int, int>> v;
    for (int i = 0; i < rank.size(); i++) {
        if (attendance[i]) v.emplace_back(rank[i], i);
    }
    sort(v.begin(), v.end());

    return 10000 * v[0].second + 100 * v[1].second + v[2].second;
}

def solution(rank, attendance):
    res = sorted((r, i) for i, r in enumerate(rank) if attendance[i])
    (_, a), (_, b), (_, c) = res[:3]

    return 10000 * a + 100 * b + c

---