2225. Find Players With Zero or One Losses

문제

https://leetcode.com/problems/find-players-with-zero-or-one-losses/description/

풀이

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> lostMap = new HashMap<>();
        List<List<Integer>> answer = new ArrayList<>();

        answer.add(new ArrayList<>());
        answer.add(new ArrayList<>()); 
        // 또는 List<List<Integer>> answer = Arrays.asList(new ArrayList<>(), new ArrayList<>()) - 이 경우 불변리스트이므로 크기를 변경하는 answer.add는 안되지만, 내부 요소를 변경하는 answer.get(0).add는 가능

        for(int[] arr : matches) {
            int winner = arr[0];
            int loser = arr[1];
			
            // lostMap.putIfAbsent(winner, 0)도 사용 가능
            lostMap.put(winner, lostMap.getOrDefault(winner, 0));
            lostMap.put(loser, lostMap.getOrDefault(loser, 0) + 1);
        }

        for(Map.Entry<Integer, Integer> entry : lostMap.entrySet()) {
            int player = entry.getKey();
            int lose = entry.getValue();
            if(lose == 0) {
                answer.get(0).add(player);
            } else if(lose == 1) {
                answer.get(1).add(player);
            }
        }
		
        // 내부적으로 O(NlogN) 정렬, 정렬이 문제에 등장하면 O(NlogN)을 깔고 들어간다고 보면됨. TreeSet을 써도 내부 정렬에 O(logN) * N
        Collections.sort(answer.get(0));    
        Collections.sort(answer.get(1));

        return answer;
    }
}

• 각 선수별 패배 횟수를 카운팅하여, 한 번도 안 진 선수와 1번만 진 선수를 출력하는 문제
  • 패배 횟수를 카운팅하기 위해 Map을 사용
  • Matches를 돌면서 이겼다면 그대로, 졌다면 +1 패배 횟수 카운팅
• 카운팅이 끝나면, Map을 돌면서 패배 횟수가 0인 선수와 1인 선수를 answer에 삽입
• The values in the two lists should be returned in increasing order. 이므로 정렬하여 return