프로그래머스 '순위' 문제풀이 - Henry's Algorithm

 

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n     results     return

5

[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

 

 

문제푸는 방법:

1. 그래프를 사용해서 푸는 문제이다.

2. 대신 순서가 있다. 이긴 방향 그래프 / 진 방향 그래프

3. 이긴 방향 그래프를 통해 나보다 아래있는 노드의 '개수'를 파악한다.(최단 경로 이런 문제 아님)

4. 진 방향 그래프를 탐색하면서 나보다 위에 있는 노드의 '개수'를 파악한다.

5. 3번과 4번의 결과가 n-1개여야지 순서가 제대로 정해진 것이다.

6. 1~n까지 5에 해당하는 경우 result +=1 해준다.

7. result를 반환해준다.

 

 

정답 코드:

 

def solution(n, results):
    arr = {}
    arr2 = {}
    for i in results:
        if i[0] not in arr:
            arr[i[0]] = [i[1]]
        else:
            arr[i[0]].append(i[1])
        if i[1] not in arr2:
            arr2[i[1]] = [i[0]]
        else:
            arr2[i[1]].append(i[0])
    answer = 0
    for i in range(1,n+1):
        if bfs(arr,i) + bfs(arr2,i) == n-1:
            answer += 1
    return answer

def bfs(graph,start):
    queue = [[start,0]]
    visited = []
    a = -1
    while queue:
        current = queue.pop(0)
        if current[0] not in visited:
            a += 1
            visited.append(current[0])
            if current[0] in graph:
                arr = set(graph[current[0]]) - set(visited)
                queue.extend([[i,current[1]+1] for i in arr])
    return a

 

 

코드 최적화

as-is:

11줄의 코드를

arr = {}
arr2 = {}
for i in results:
    if i[0] not in arr:
        arr[i[0]] = [i[1]]
    else:
        arr[i[0]].append(i[1])
    if i[1] not in arr2:
        arr2[i[1]] = [i[0]]
    else:
        arr2[i[1]].append(i[0])

to-be:

6줄로 간결하게 만들어준다.

from collections import defaultdict
~~~~~~~

arr = defaultdict(set)
arr2 = defaultdict(set)
for i in results:
    arr[i[0]].add(i[1])
    arr2[i[1]].add(i[0])

 

 

 

 

프로그래머스를  풀면서 또 하나 느낀 점은 반드시 효율적인 코드를 짜는 것보다는 

정확한 방법이 생각나면 일단 도전해보는 것이다.

도전해보면 의외로 프로그래머스에서 정확도만 채점하는 경우도 있기 때문이다.(이 문제같은 경우 그렇다.)

 

 

 

 

 

NHN 코딩테스트를 대비하여 Java 코드로도 풀어보았다.

푸는 방식은 위의 파이썬 설명과 같다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        ArrayList<ArrayList<Integer>> win = new ArrayList<ArrayList<Integer>>();
        ArrayList<ArrayList<Integer>> lose = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<n+1; i++){
            win.add(new ArrayList<Integer>());
            lose.add(new ArrayList<Integer>());
        }
        for(int[] i: results){
            int a = i[0];
            int b = i[1];
            win.get(a).add(b);
            lose.get(b).add(a);
        }
        int ans = 0;
        for(int i=1; i<n+1; i++){
            if(BFS(win,i,n)+BFS(lose,i,n) == n-1){
                ans++;
            }
        }
        return ans;
    }
    int BFS(ArrayList<ArrayList<Integer>> graph, int start, int n){
        boolean[] visited = new boolean[n+1];
        visited[start] = true;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        int a = -1;
        while(!q.isEmpty()){
            int cur = q.poll();
            a++;
            for(int i:graph.get(cur)){
                if(!visited[i]){
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
        return a;
    }
}