실패율

코딩테스트 연습 - 실패율 | 프로그래머스 (programmers.co.kr)    

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.

- 실패율의 정의

- 실패율이 같은 스테이지가 있다면, 작은 번호의 스테이지가 먼저 오도록

- 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0

- 실패율을 내림차순으로 정리

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

- 전에 이 문제를 다른 언어(C++, Javascript)로 풀어봤었다

- 그래서 자신감을 갖고 문제에 접근할 수 있었다. 

   1) 각 단계에서 실패율을 구한다.

   2) stages와 N을 2중 for문으로 하면 최대 1억회 = 1초 

    -> 즉, 가능하다

 

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

import java.util.Map;
import java.util.Map.Entry;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        
        int total = stages.length;
        int currStage = 1;
        
        Map<Integer, Double> map = new HashMap<>();
        
        while(true){
            
            if(currStage == N+1){
                break;
            }
            
            
            int cnt = 0; 
            
            for(int i=0; i<stages.length; i++){
                if(currStage == stages[i]){
                    cnt++;
                }
            }
            
            double failureRate;
            
            if(total != 0){
                failureRate = (double)cnt/(double)total;
            }else{
                failureRate = 0; 
            }
            map.put(currStage, failureRate);
            
            total -= cnt;
            currStage++;
            
        
        }
        

		// Map.Entry 리스트 작성
		List<Entry<Integer, Double>> list_entries = new ArrayList<Entry<Integer, Double>>(map.entrySet());
        

		// 비교함수 Comparator를 사용하여 내림 차순으로 정렬
		Collections.sort(list_entries, new Comparator<Entry<Integer, Double>>() {
			// compare로 값을 비교
			public int compare(Entry<Integer, Double> obj1, Entry<Integer, Double> obj2)
			{
				// 내림 차순으로 정렬
				return obj2.getValue().compareTo(obj1.getValue());
			}
		});
		
		int pos = 0; 
		
		for(Entry<Integer, Double> entry : list_entries) {
			answer[pos++] = entry.getKey();
		}
		
        return answer;
        
    }
}

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- HashMap을 value를 기준으로 내림차순으로 정렬해야 했는데, 이 로직을 잘 몰랐다.

-> 이전에도 몰라서, 검색해서 풀었던 적이 있었는데, 숙지가 안되어서 

     다시 검색해서 풀었다. 

-> 이 부분을 숙지해야 할까? 혹은 HashMap을 사용하지 않고 더 나은 방법이 있을까?

 

- 처음 풀었을 때, 정답률이 70%가 나왔다

-> 즉, 엣지 케이스를 잡아내지 못했다.

-> '스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0'이라는 조건을 고려하지 않았다.

-> 이 조건을 다시 고려해서 문제를 해결했다.

-> 이 과정에서 5~10분정도 시간이 더 소요되었다.

 

- 왜 엣지 케이스를 잡아내지 못하는가?

-> 문제에서 주어진 테스트 케이스를 통과하면 급하게 답안을 제출하는 경향이 있다.

-> 테스트 케이스 통과 = 문제 정답이 아니다. 특히, 문제에서 주어진 테스트 케이스의 개수가 낮을수록

     나의 답이 엣지 케이스를 고려하지 못했을 확률이 높아진다. 

-> 테스트 케이스를 통과하더라도 한 번 더 엣지 케이스를 고민해보고, 고려하는 습관을 갖자.

-> 이렇게 하면 문제 풀이 시간을 문제당 최소 10%는 줄일 수 있을 것이라고 생각한다.