프로그래머스 - 순위

순위 (2021. 07. 05) Graph (BFS)

문제 및 풀이 주소

Programmers
Git Solution

문제 설명

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	vertex	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 설명

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

문제 해결

이슈 케이스

초반 문제 해결 설계시, 승자에 대한 리스트와 패배에 대한 리스트를 따로 저장을 해야할 것 같았다. 각각의 리스트를 만든 후 필터링을 하면 원하는 답을 구할 수 있을 것같았다. 초반 생각한 설계는 다음과 같다.

• 노드별 승리 데이터 셋이 없으면 마지막 순위 확정이다.
• 노드별 패배 데이터 셋이 없으면 1순위 확정이다.
• 1순위 또는 마지막 순위를 알 수가 없는 상황이면 어떠한 노드도 정확한 순위를 구할 수 없다고 판단되어서 0값을 반환한다.

단, 조건에 해당하는 노드의 개수가 2개 이상이면 해당 노드들은 전부 순위를 알수 없으므로 제외한다.

예제에서 주어진 데이터 셋에서 5번 노드가 승리셋이 없으므로 5위가 확정이며, 승리 데이터 셋에서 패배가 없는 1, 4번 노드들은 개수가 2개이므로 제외한다.
즉, 1, 4 노드는 제외 대상, 5번 노드는 확정 대상이다.

이후 남은 노드인 2, 3노드에 대해서 확정 노드에서 탐색알고리즘을 통해서 원하는 결과를 찾으면 되리라 생각되었다.
하지만 여기서 문제점이 발견되었는데, 확정 5번 노드에 의해서 2번 노드의 순위가 4위인것을 알게 되었지만, 2번 노드와 3번 노드에 대해 단순히 연결값으로는 순위에 대한 부분을 알 수가 없게 되었다. 추가적인 조건이 필요한데 방식이 점점더 산으로 가게 되었다.

해결 케이스

승리, 패배 데이터셋을 만드는 부분은 큰 문제가 없다고 판단되었는데, 문제에서 다음과 같은 지시문을 처리하지 않았음을 깨달았다.

만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다

• A > B가 성립하고, B > C가 성립한다면, A > C는 성립합니다.

해당 말이 무슨말인고 하니, 초기 만들었던 데이터 셋에서 주어진 vertex를 가지고만 데이터셋을 만드는것이 아닌, 위의 조건에 해당하는 노드들을 추가로 만들면 될까? 하는 생각이 들었다. 종이에 끄적이면서 실제 주어지는 데이터는 아니지만, A > C의 조건이 되는 노드들은 탐색을 통해서 내용이 포함되어있으면 성립함을 알게 되었다.

[1, 2], [2, 5]에 대해서

• 1은 2에 승리한다.
• 2는 5에 승리한다.
• 즉, 1은 2와 5에 승리한다.

가상의 결과셋을 승리와 패배로 나뉘어 수행하고 비교를 해보았더니, 승리셋과 패배셋을 병합하였더니 순위 대상이 되는 노드는 모든 노드들이 포함되어 있었다. (Set으로 하였기 때문에 중복은 제거 된다.)

코드 - 1차 승패 데이터

/*
[1차] 노드별 승리 데이터 셋
1 = [2]
2 = [5]
3 = [2]
4 = [2, 3]
5 = []

[1차] 노드별 패배 데이터 셋
1 = []
2 = [1, 3, 4]
3 = [4]
4 = []
5 = [2]
*/

// 맵 초기화 (주어진 데이터셋을 모두 가지기 위함)
IntStream.rangeClosed(1, nodeCount).forEach(node -> {
    winnerMap.put(node, new HashSet<>());
    loserMap.put(node, new HashSet<>());
});

// [1차] 승리, 패배 데이터 셋 구축
for(int[] arr : results){
    //승리 arr[0] 패매 arr[1]
    winnerMap.merge(arr[0], new HashSet<>(){{add(arr[1]);}}, (e, i) -> new HashSet<>(){{addAll(e);addAll(i);}});
    loserMap.merge(arr[1], new HashSet<>(){{add(arr[0]);}}, (e, i) -> new HashSet<>(){{addAll(e);addAll(i);}});
}

코드 - 2차 승패 데이터 (가상의 승패 노드 추가)

/*
[2차] 노드별 승리 데이터셋을 기준으로 가상 승리 노드셋 계산 ( 자기 자신은 항상 포함, 괄호는 가상으로 만들어진 노드셋 )
1 = [1, 2, (5)]
2 = [2, 5]
3 = [2, 3, (5)]
4 = [2, 3, 4, (5)]
5 = [5]

[2차] 노드별 패배 데이터셋을 기준으로 가상 패배 노드셋 계산 ( 자기 자신은 항상 포함, 괄호는 가상으로 만들어진 노드셋 )
1 = [1]
2 = [1, 2, 3, 4]
3 = [3, 4]
4 = [4]
5 = [(1), 2, (3), (4), 5]
*/

// [2차] 승리, 패배 가상 데이터 셋 구축 ( 각자 for 문에서 리팩토링 )
for(Map scoreMap : new Map[]{winnerMap, loserMap}){
    for(Object  key : scoreMap.keySet()){
        bfs((Integer)key, scoreMap);
    }
}

// BFS 메소드
public void bfs(Integer node, Map<Integer, Set<Integer>> scoreMap){
    Set<Integer> tempSet = new HashSet<>();                     // BFS 내에서 사용되는 임시 셋
    boolean[] isVisit = new boolean[nodeCount];                 // 방문 배열 초기화 (예전 속도 이슈로 방문리스트 -> 방문 배열로 변경)
    Queue<Integer> queue = new LinkedList<>(){{add(node);}};    // BFS 큐

    //Queue loop
    while(!queue.isEmpty()){
        int queueNode = queue.poll();
        // 노드 추가
        tempSet.add(queueNode);
        for(int iNode : scoreMap.get(queueNode)){
            // 방문 체크
            if(!isVisit[iNode - 1]){
                isVisit[iNode - 1] = true; //방문 추가
                queue.add(iNode);
            }
        }
    }
    scoreMap.put(node, tempSet);            // 승리 또는 패배 데이터 셋 신규 데이터 추가
}

코드 - 승패 데이터 ( 데이터 병합 )

/*
[3차] 승리 데이터 셋과 패배 데이터 셋을 합쳤을 경우 노드셋 계산
1 = [1, 2, (5)]
2 = [1, 2, 3, 4, 5]
3 = [2, 3, 4, (5)]
4 = [2, 3, 4, (5)]
5 = [(1), 2, (3), (4), 5]
*/

// [3차] 승리데이터 와 패배 데이터를 머지
IntStream.rangeClosed(1, nodeCount).forEach(node ->
mergeMap.put(node, new HashSet<>(){{addAll(winnerMap.get(node));addAll(loserMap.get(node));}}));

코드 - 결과 데이터 반환

// 승리데이터셋과 패배데이터셋을 합쳤을때, 모든 노드들이 표현되는 노드 개수 반환
return (int)mergeMap.values().stream().filter(value -> value.size() == n).count();

테스트 결과

테스트 번호	통과여부	메모리 및 시간	테스트 번호	통과여부	메모리 및 시간
테스트 1	통과	(10.46ms, 54MB)	테스트 6	통과	(12.47ms, 54.7MB)
테스트 2	통과	(12.18ms, 52.5MB)	테스트 7	통과	(48.39ms, 57.2MB)
테스트 3	통과	(9.40ms, 52.9MB)	테스트 8	통과	(64.00ms, 64.3MB)
테스트 4	통과	(10.26ms, 53.4MB)	테스트 9	통과	(100.88ms, 69.8MB)
테스트 5	통과	(11.91ms, 53.4MB)	테스트 10	통과	(144.90ms, 83.6MB)

후기

나름 이번에는 바로 무작정 개발하지 않고, 설계를 오랫동안 하였는데, 결국 1차는 무난히 실패해버렸다. 혼자서 하는 생각의 설계는 여러가지 예외케이스를 찾아내지 못하였고, 오랜 개발시간을 들였는데 다시 롤백하게되었다. ( 이번에는 부분 롤백이였지, 전체 롤백이면... )
시간의 제한을 두지 않고 오랜시간 생각하고 테스트 하였기에 해결했지, 실제 시간제한 있는 코딩테스트를 보게되면
한문제나 맞출까 싶다... 아직 멀었다.