99클럽 코테 스터디 25일차 TIL + 순위 (java)

 

💡 문제

• 순위
• https://school.programmers.co.kr/learn/courses/30/lessons/49191

권장 시간

• 1시간 30분

소요 시간

• 2시간

나의 풀이 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;

        // 내가 패배한 선수
        Map<Integer, HashSet<Integer>> map1 = new HashMap<>();
        
        // 내가 이긴 선수
        Map<Integer, HashSet<Integer>> map2 = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            map1.put(i, new HashSet<>());
            map2.put(i, new HashSet<>());
        }

        for (int[] result : results) {
            map1.get(result[1]).add(result[0]);
            map2.get(result[0]).add(result[1]);
        }

        bfs(map1, n);
        bfs(map2, n);
        
        for (int i = 1; i <= n; i++) {
            // 내가 패배했거나 이긴 선수들의 합
            int total = map1.get(i).size() + map2.get(i).size();
            if (total == n-1) { // 나를 제외한 모든 선수와의 관계가 결정된 경우
                answer++;
            }
        }
        
        return answer;
    }
    
    private void bfs(Map<Integer, HashSet<Integer>> map, int n) {
        for (int i = 1; i <= n; i++) {
            Queue<Integer> q = new LinkedList<>(map.get(i)); // 처음 선수들의 집합을 큐에 추가
            
            while (!q.isEmpty()) {
                int player = q.poll();
                HashSet<Integer> set = map.get(player);
                for (int s : set) {
                    if (map.get(i).add(s)) { // 새로 추가된 선수만 큐에 삽입
                        q.add(s);
                    }
                }
            }
        }
    }
}

주요사항

어제 문제에서 HashMap을 사용해도 풀 수 있겠다는 생각을 했었는데 이번 문제에 적용할 수 있었다!

다만 저장까지는 괜찮았는데 그 이후 깊게 깊게 파고 들어야할 때는 HashMap으로만 하려니 3중 for문까지 가서 이건 아니구나 싶었다.

방법은 bfs/dfs로 푸는거였고, ‘파고들어야한다’는 로직을 구현하려면 다른거말고 bfs/dfs를 떠올려야한다는 것을 알게 됐다.