99클럽 코테 스터디 25일차 TIL 순위

알고리즘

99클럽 코테 스터디 25일차 TIL 순위

ernest45 2024. 6. 14. 01:56

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

1. 문제 및 접근

1~n번까지의 권투선수, 1대1 방식으로 매치 결과를 0,1의 배열로 주어지는데 0이 이긴 선수 1이 진 선수

주어진 매치 결과 순위를 매기려고 하는데 모든 결과가 있지 않아 정확하게 순위를 매길 수 없다

결과만 보고 정확한 순위를 알 수 있는 선수의 수를 return

그~~래프로 방향성을 주고, 정답 리스트를 놓아서 [0,1,2,3,4,~ , n] 의 값중 하나만 있으면 정답으로 처리하자~~

제한사항

선수의 수는 1명 이상 100명 이하입니다.

경기 결과는 1개 이상 4,500개 이하입니다.

results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.

모든 경기 결과에는 모순이 없습니다.

2. 내 풀이(틀림)

고민한 순서대로 나열하겠다.

이긴 사람의 정보를 넣어줄 지 vs 진 사람의 정보를 넣을 지 고민했다

그래서

1. index 별 이긴 사람의 정보를 넣는다.

2. index 별 진 사람의 정보를 넣는다.

3. 양 방향은 아닌 것 같으니 1,2를 같이 적어보자!

이렇게 두개의 리스트로 둘다 순회하며 돌면 순위가 배열에 여러 값이 저장되지 않는 사람

즉 하나의 값을 가지는 index라면 그 순위를 확정할 수 있을 것 같았다.

나(Index)를 기준으로 이긴 사람의 정보를 가진 list와 진 사람의 정보를 가진 list , 총 2개

고민하다 보니, 안 풀려서 내 방식의 접근이 위상정렬이라는 키워드를 알 수 있었고,

위상정렬은 진입차수가 0인 것 부터 출발하는데 list를 두개 돌다보면 진입차수가 1위거나 n위거나 판별 후 진입할 수 있을 것만 같았다...

고민하다 클럽장님에게 물어보니, 위상정렬은 답을 내기 힘들다는 답변과

플로이드-워셜 알고리즘을 말씀해주셨다.

(위상정렬 말고 그냥 DFS로 접근해도 가능하긴 한데 거기로 돌렸음 더 빨리 풀었을 듯..)

3. 플로이드-워셜 알고리즘

O(n^3)이라 시간 복잡도를 가지며,

현재 n이 100명이 들어올 수 있으니 1,000,000의 데이터가 들어올 수 있는데 충분히 가능하다.

작은 그래프만 써야할 듯 싶다

플로이드-워셜 알고리즘의 핵심은

"거쳐가는 정점을 기준으로 최단 거리를 구하는 것"

다익스트라 vs 플로이드-워셜 ?

다익스트라는 하나의 정점에서 출발했을때 다른 모든 정점으로의 최단거리를 구하는 알고리즘이고,

프로이드-워셜은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.

다익스트라 알고리즘은 음의 가중치는 구하지 못하는데, 프로이드-워셜은 가능

더 정확하게 말해서는 음의 가중치를 가지는 간선이 존재해도 구할 수 있다 (사이클의 의미가 아님!)

탐색 방법은 문제와 엮어서 설명하겠다.

4. 풀이

 int answer = 0;


    boolean[][] graph = new boolean[n + 1][n + 1];


    
    for (int[] result : results) {
        int win = result[0];
        int lose = result[1];


        graph[win][lose] = true;
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=n ; j++) {
            for (int k = 1; k <= n; k++) {
                if (graph[j][i] && graph[i][k]) {
                    graph[j][k] = true;
                }
            }

        }
    }

    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <=n ; j++) {

            if (i != j && graph[i][j] || graph[j][i]) {
                count++;
            }
            
        }
        // 자신을 제외한 모든 선수와의 관계가 확인되면 정확한 순위를 판별할 수 있음
        if (count == n - 1) {
            answer++;

    }}


    return answer;
}

주어진 배열의 정보가 [4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 라면