Today's Algorithm(2019-01-29)

programmers. 순위

어려운 문제였습니다. 저도 어제 조금 생각하다가 방향이 잘 안잡혀서 답안을 봤는데 더 모르겠더라구요. 그래서 오늘 다시 도전해봤는데 오늘은 이 방법이 맞을지 안 맞을지 모르지만 일단 해보자는 생각으로 도전을 했습니다. 결국 답은 틀렸지만 시도한 가치가 있었습니다. 왜냐하면 마지막에 답을 산출하는 과정만 틀렸을 뿐 그 전에 데이터를 가공하는 과정은 의미가 있었거든요. 그럼 처음에 제가 시도한 방법부터 설명해보겠습니다.

 

답안에는 '플로이드-워셜'알고리즘으로 푸는 방법으로 풀려있습니다. 하지만 저는 bfs를 n번 도는 방법을 통해 데이터를 가공하였습니다(실제 답안에도 이렇게 2가지로 풀 수 있다고 가이드되어 있습니다). bfs를 n번 도는 이유는 다음과 같습니다.

• 만약 1이라는 숫자를 선택했고 나머지 2, 3, 4, 5 라는 숫자가 어떻게든 연결되어 있다고 가정한다면 1에서 도달할 수 있는 수를 체크해둡니다.

  • 저 같은 경우 밑에서 m이라는 2차원 배열을 만들어서 boolean값으로 체크해두었습니다.
  • 도달할 수 있느냐, 없느냐는 문제 푸는데 핵심이 됩니다.

• 각각의 숫자에 대해 갈 수 있는데까지 가서 체크해야 하기 때문에 bfs를 쓰는 것이구요. 각각의 수를 다 해야하니까 n번 시행하게 됩니다.

 

그럼 위에서 각각의 수에 대해 도달할 수 있는 수를 다 체크해두었습니다. 이제는 답을 산출만 하면 되는데요. 저는 처음에 '꼴찌부터 등수는 만들어질 수 있다'라는 가정을 두고 문제를 풀었습니다. 그랬기 때문에 위에서 m을 이용하여 각각의 수가 어느 해당 수에 도착했을 때 그 해당 수를 ++해서 몇 개의 수가 그곳에 도착하는지를 체크하였습니다. 그래서 만약 5개의 수가 주어졌는데 4개의 수가 도달했다면 그게 꼴찌, 3개의 수가 도달했따면 꼴찌 앞 이런 식으로 정답을 체크했습니다. 이 방법은 근데 어림짐작이었고 사실 그게 맞는지를 모르겠더라구요. 정확한 방법은 아니었기 때문에. 그래도 주어진 테스트 케이스는 통과했거든요.

 

여기에서 다른 사람의 코드를 참고하였습니다. m까지 만든 것을 다른 방식으로 활용하면 됩니다. 순위를 결정할 수 있다는 말은 다른 수 2개가 있을 때 어느 수는 도달할 수 있어야 합니다. 만약 a와 b라는 숫자가 있다면 a가 b에게, b가 a에게 도달할 수 있어야 한다는 것이죠. 굳이 안 붙어있어도 됩니다. 잘 생각해보면 5명 중 1등이라는 것도 알 수 있는 것이 1등과 2, 3, 4, 5등의 승패 관계를 알아야 가능한 것이라는 것을 깨달을 수 있을 것입니다.

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

        boolean[][] m = new boolean[n + 1][n + 1];
        Map<Integer, List<Integer>> map = init(results);

        for (int i = 1; i <= n; i++) {
            boolean[] visit = new boolean[n + 1];
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            visit[i] = true;
            while(!queue.isEmpty()) {
                int num = queue.poll();
                List<Integer> list = map.getOrDefault(num, new ArrayList<>());
                for (Integer integer : list) {
                    if(!visit[integer]) {
                        visit[integer] = true;
                        m[i][integer] = true;
                        queue.add(integer);
                    }
                }
            }
        }

        for (int i = 1; i < n + 1; i++) {
            boolean pass = true;
            for (int j = 1; j < n + 1; j++) {
                if(i != j && !m[i][j] && !m[j][i]) {
                    pass = false;
                    break;
                }
            }
            if(pass) answer++;
        }

        return answer;
    }

    public Map<Integer, List<Integer>> init(int[][] result) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] ints : result) {
            List<Integer> list = map.getOrDefault(ints[0], new ArrayList<>());
            list.add(ints[1]);
            map.put(ints[0], list);
        }
        return map;
    }
}