[PCCP] 스택 · 큐 · 정렬 · 그리디 알고리즘 [8]

▼ Why ?

이번엔 정렬과 관련된  문제를 풀어서 정렬하는 것에 어느정도 익숙해졌는지 체크해보려고 한다

---

▼ 전국 대회 선발 고사

 

문제 정보

0번부터 n - 1번까지 n명의 학생 중 3명을 선발하는 전국 대회 선발 고사를 보았습니다. 등수가 높은 3명을 선발해야 하지만, 개인 사정으로 전국 대회에 참여하지 못하는 학생들이 있어 참여가 가능한 학생 중 등수가 높은 3명을 선발하기로 했습니다.

각 학생들의 선발 고사 등수를 담은 정수 배열 rank와 전국 대회 참여 가능 여부가 담긴 boolean 배열 attendance가 매개변수로 주어집니다. 전국 대회에 선발된 학생 번호들을 등수가 높은 순서대로 각각 a, b, c번이라고 할 때 10000 × a + 100 × b + c를 return 하는 solution 함수를 작성해 주세요.

 

제한 사항

• 3 ≤ rank의 길이 = attendance의 길이 ≤ 100
• rank[i]는 i번 학생의 선발 고사 등수를 의미합니다.
• rank의 원소는 1부터 n까지의 정수로 모두 서로 다릅니다.
• attendance[i]는 i번 학생의 전국 대회 참석 가능 여부를 나타냅니다.
  • attendance[i]가 true라면 참석 가능, false면 참석 불가능을 의미합니다.
• attendance의 원소 중 적어도 3개는 true입니다.

 

입출력 예

 

어떻게 해결해야 할까?

1. 일단 등수가 높은 순서대로(오름차순) 정렬한다
2. 해당 등수(key)에 해당하는 사람이 대회에 참석 가능한지(value) 확인할 수 있는 HashMap 객체 하나를 생성한다
3. 그리고 등수에 해당하는 사람(key)이 몇 번째 사람(value)인지를 찾기 위한 HashMap 객체 하나를 생성해주면 될 것 같다
4. 이 객체들을 이용해서 전국 대회에 참여할 수 있는 사람들 중  등수가 높은 순서대로 3명을 뽑아 ArrayList에 넣어주고, ArrayList에서 값을 뽑아 문제에 맞는 결과로 계산하여 반환하도록 하자

 

해결 코드 0

import java.util.*;

class Solution {
    public int solution(int[] rank, boolean[] attendance) {
        HashMap<Integer, Boolean> rankAtd = new HashMap<>();
        HashMap<Integer, Integer> rankWho = new HashMap<>();
        
        for(int i = 0; i < rank.length; i++) {
            rankAtd.putIfAbsent(rank[i], attendance[i]);
            rankWho.putIfAbsent(rank[i], i);
        }
    
        Arrays.sort(rank);
        
        ArrayList<Integer> select = new ArrayList<>();
        
        for(int r : rank) {
            if(rankAtd.get(r) == true && select.size() <= 3) select.add(rankWho.get(r));
        }
        
        return select.get(0) * 10000 + select.get(1) * 100 + select.get(2);
    }
}

 

해결 코드 1

• 굳이 HashMap을 안쓰고 좀더 간결한 코드로 해결할 수 있는 방법이 있을 것 같아서 다르게 생각해보았다
• int배열로 하는 ArrayList 객체(참조변수 - rankList)를 하나 생성하여 int[0]에는 등수를, int[1]에는 등수에 해당하는 사람의 번호를 저장하자
• 그리고 참석 가능한 사람만 골라내기 위해 HashMap을 또 하나 생성했던 것인데, 생각해보면 참석 가능한 사람만  앞서 생성한 ArrayList에 저장하면 되는 것이기 때문에, 저장하기 전에 참석 여부를 체크해주면 될 것 같다
• 이렇게 저장된 ArrayList를 오름차순으로 정렬하고, 등수가 가장 높은 3명(get(0), get(1), get(2))을 추출해서 int[1](번호)에 해당하는 값으로 계산해서 반환한다

import java.util.*;

class Solution {
    public int solution(int[] rank, boolean[] attendance) {
        int answer = 0;
        ArrayList<int[]> rankList = new ArrayList<>();
        
        for(int i = 0; i < rank.length; i++)
            if(attendance[i]) rankList.add(new int[]{rank[i], i});
        
        rankList.sort((a, b) -> a[0] - b[0]);
        
        return = rankList.get(0)[1] * 10000 + rankList.get(1)[1] * 100 + rankList.get(2)[1];
    }
}

 

---

▼ 정리

 

• ArrayList 같이 컬렉션의 지네릭 타입으로 'Wrapper class' 뿐만 아니라 배열, 컬렉션도 가능하다는 것을 기억해두면 코드를 좀더 간결하고 효율적으로 작성하는데 큰 도움이 될 것 같다