[프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 실패율

2019 KAKAO BLIND RECRUITMENT - 실패율

---

< 문제 정의 >

---

< 문제 접근 >

stages 배열의 크기는 전체 유저의 수를 나타내며, 각 원소는 플레이어가 묶여있는(클리어를 못 하고 있는) 스테이지를 의미한다. solution 함수의 첫 번 째 매개변수인 N은 현재 유저들이 위치한 스테이지 중에서 가장 높은 스테이지가 N+1 임을 의미한다. 즉, 가장 많이 클리어 한 유저가 현재 6레벨에서 클리어를 못 하고 있다면 N은 5가 된다.

 

우선 각각의 레벨에서 묶여있는 유저가 몇 명인지 세기 위해서, 이전 포스팅에서 사용했던 map과 getOrDefault 로 배열에서 중복되는 값이 몇 개 씩 있는지 Key-Value 쌍으로 정리하는 것이 첫 번째 할 일이고,

 

1부터 입력 받은 N 스테이지 까지 반복하며 각 스테이지 별 실패율을 계산하여 새로운 Key-Value 쌍을 만든다. 즉 최종으로 구해야 할 HashMap은 Key(스테이지) - Value(실패율) 이다. 실패율은 0~1이하이므로, 나눗셈을 수행할 때 정수형끼리 나눗셈을 하여 0 또는 1만 나오는 실수를 피해야 한다. double 형을 사용하자.

 

또한 1부터 N스테이지 까지 돌면서, 처음 만들었던 HashMap에 키가 존재하지 않으면(==스테이지에 도달한 유저가 없으면) 해당 스테이지의 실패율은 0 으로 정의한다.

 

그렇게 만들어 진 HashMap을 sortByValue로 내림차순 정렬을 한 뒤, KeySet의 모든 원소를 추출하여 정수형 배열 형태로 return한다.

 

---

< 문제 해결 >

public static int[] solution(int N, int[] stages) {
        HashMap<Integer, Integer> s_count = new HashMap<>();
        HashMap<Integer, Double> f_rate = new HashMap<>();

        for (Integer key : stages) {
            s_count.put(key, s_count.getOrDefault(key, 0)+1); // 중복 값 세기
        }

        int denominator = stages.length;
        for (int i = 1; i <= N; i++) {
            if(s_count.containsKey(i)){
                int count = s_count.get(i);
                f_rate.put(i, (double) count / denominator);
                denominator = denominator - count;
            }
            else {
                f_rate.put(i, 0.0);
            }
        }

        List<Integer> keySetList = new ArrayList<>(f_rate.keySet());
        Collections.sort(keySetList, (o1, o2) -> (f_rate.get(o2).compareTo(f_rate.get(o1)))); // 내림차순
        //Collections.sort(keySetList, (o1, o2) -> (result.get(o1).compareTo(result.get(o2)))); // 오름차순

        int[] result_arr = new int[keySetList.size()];
        int index = 0;
        for(Integer key : keySetList) {
            result_arr[index] = key;
            index++;
        }
        return result_arr;
    }

위 문제를 해결하기 위해 2개의 HashMap을 사용했다.

1. stages 배열에서 중복된 값을 정리하기 위한 HashMap. // Key(스테이지)-Value(중복데이터 수)

2. 위의 HashMap을 바탕으로 1부터 N까지 반복하여 각 스테이지별 실패율을 저장 // Key(스테이지)-Value(실패율)

 

// input = 5, {2, 1, 2, 6, 2, 4, 3, 3}

for (Integer key : stages) {
	s_count.put(key, s_count.getOrDefault(key, 0)+1); // 중복 값 count
}

// {1=1, 2=3, 3=2, 4=1, 6=1}

input으로 들어온 정수형 배열의 중복 값을 count하여 HashMap에 put 해준다.  # map.put( key, value )

이 때, s_count.put(key, s_count.getOrDefault( key, 0 ) + 1); 을 사용하여 key를 넣고, key가 존재 할 경우 기존 Value에 +1을 해 주거나 key가 맵에 존재하지 않을 경우 default인 0에 1을 더한 1을 초기화 해 준다. 참고로 HashMap에서 중복된 키 값이 들어올 때, 기존의 Key-Value 쌍은 새로운 Key-Value 쌍으로 덮어쓰기 된다. 해당 반복문이 끝난 후, s_count를 출력해보면 다음과 같이 각 스테이지 별 묶여있는 유저의 수를 알 수 있다.

 

 

int denominator = stages.length;

for (int i = 1; i <= N; i++) {
	if(s_count.containsKey(i)){
		int count = s_count.get(i);
		f_rate.put(i, (double) count / denominator);
		denominator = denominator - count;
	}
	else {
		f_rate.put(i, 0.0);
	}
}

// {1=0.125, 2=0.42857142857142855, 3=0.5, 4=0.5, 5=0.0}

위에서 만든 s_count를 바탕으로 스테이지-실패율 쌍을 저장할 f_rate 를 구하기 위해 다음 작업을 수행한다.

우선 반복은 1스테이지 부터 N 스테이지 까지 시작하며, 최초 1스테이지에서 부터의 분모는 stages 배열의 길이와 같다.

i (스테이지) 를 순회하면서, s_count가 i 스테이지를 포함하고 있는지를 확인한다. map.containsKey( Key ) HashMap에 키로 포함되어 있다면, 실패한 사람이 몇 명인지 count를 s_count.get( Key ) 로 가져오고, f_rate에 Key(스테이지)-Value(실패율) 쌍을 추가해준다. 추가가 끝나면 다음 연산 부터는 이미 연산이 끝난 유저의 숫자는 빼줘야 하기 때문에 분모를 count 만큼 감소시켜준다. 만약 Key를 포함하지 않는다면 해당 스페이지는 실패율 0으로 취급한다.

 

 

List<Integer> keySetList = new ArrayList<>(f_rate.keySet());
Collections.sort(keySetList, (o1, o2) -> (f_rate.get(o2).compareTo(f_rate.get(o1)))); // 내림차순
//Collections.sort(keySetList, (o1, o2) -> (result.get(o1).compareTo(result.get(o2)))); // 오름차순

int[] result_arr = new int[keySetList.size()];

int index = 0;
for(Integer key : keySetList) {
	result_arr[index] = key;
	index++;
}

마지막으로 f_rate를 sortByValue 해 주기 위해서. f_rate.keySet( ) 로 f_rate의 키 값을 모두 가져와 List에 넣는다. 다음으로

Collections.sort( keySetList, (o1, o2) -> (f_rate.get( o2 ).compareTo( f_rate.get(o1) )));

코드를 실행하여 f_rate.get( Key ), 즉, f_rate의 키 값에 매핑된 Value를 기준으로 keySetList를 내림차순 정렬한다. 위에서 o1과 o2를 바꾸면 오름차순 결과값을 얻을 수 있다.

 

이제 실패율을 기준으로 Key값(스테이지)가 내림차순 정렬 된 List를 얻었기 때문에 이 List를 정수형 Array로 바꿔주어야 한다. keySetList.size() 만큼에 정수형 배열을 만들고 keySetList를 순회하면서 result_arr에 하나씩 삽입하여 최종 산출물을 만들 수 있다.

 

※ Collections.sort ~ 를 해도 keySetList 의 Key들만 원본 map을 참조하여 map의 Value들를 기준으로 순서가 정렬되는 것 이기 때문에 원본 map인 f_rate는 아무 변화가 없다.