문제 바로가기

선수의 수, [이긴사람,진사람] 배열이 주어질때 순위를 정확히 알 수 있는 사람의 수를 출력하는 문제

접근방식

분명 백준에서 비슷한 문제를 풀었던 거 같은데 까먹었는지 풀이법이 기억이 안났다.

처음에는 단순위 위 예제 입출력 하나만 보고 이긴사람 진사람의 합이 n-1인 것과 이긴사람의 갯수가 1인것, 진사람의 갯수가 1인것을 answer++해주는 방식으로 접근했다가 장렬하게 틀렸다(예제는 돌아감)

이 방법이 예제에서는 통하는데 히든케이스에서 다 틀리는 것을 보고 이긴사람,진사람 관계를 단방향 관계로 집어넣어 이긴사람의 개수와 진 사람의 합이 n-1이 되면 answer++하는 방식으로 접근했다.

처음코드(틀림)

import java.io.*;
import java.util.*;

class 순위 {
    static List<Integer>[] win_lose;
    static List<Integer>[] lose_win;
    static HashSet<Integer> map;

    public int solution(int n, int[][] results) {
        int answer = 0;
        int m=results.length;
        win_lose=new ArrayList[n+1];
        lose_win=new ArrayList[n+1];
        map=new HashSet<>();
        for(int i=1;i<n+1;i++){
            win_lose[i]=new ArrayList<>();
            lose_win[i]=new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            int a=results[i][0];
            int b=results[i][1];
            win_lose[a].add(b);
            lose_win[b].add(a);
        }
        for(int i=1;i<n+1;i++){
            if(win_lose[i].size()+lose_win[i].size()==n-1){
                map.add(i);
                if(win_lose[i].size()==1){
                    map.add(win_lose[i].get(0));
                }
                if(lose_win[i].size()==1){
                    map.add(lose_win[i].get(0));
                }
            }
        }
        answer=map.size();

        return answer;
    }
}

정답코드

import java.io.*;
import java.util.*;

class 순위2 {
    static List<Integer>[] win_lose;
    static List<Integer>[] lose_win;
    static boolean[] visited;
    static int cnt;

    public int solution(int n, int[][] results) {
        int answer = 0;
        int m=results.length;
        win_lose=new ArrayList[n+1];
        lose_win=new ArrayList[n+1];

        for(int i=1;i<n+1;i++){
            win_lose[i]=new ArrayList<>();
            lose_win[i]=new ArrayList<>();
        }

        for(int i=0;i<m;i++){
            int a=results[i][0];
            int b=results[i][1];
            win_lose[a].add(b);
            lose_win[b].add(a);
        }

        for(int i=1;i<n+1;i++){
            visited=new boolean[n+1];
            cnt=0;
            dfs(i,win_lose);
            int win=cnt;

            visited=new boolean[n+1];
            cnt=0;
            dfs(i,lose_win);
            int lose=cnt;

            if(win+lose==n-1){
                answer++;
            }
        }

        return answer;
    }

    static void dfs(int node, List<Integer>[] list){
        for(int i:list[node]){
            if(!visited[i]){
                visited[i]=true;
                cnt++;
                dfs(i,list);
            }
        }
    }
}

후기

예제만 맞다고 바로 코드를 적지 말고 좀 더 생각이란걸 하고 풀기 시작하자