[JS] 순위 - 권투 선수 왜싸워요... 싸움 멈춰 제발

아니 왜 경기 결과 잃어버리고 난리임?

일단 이 문제는 레벨 3 문제 답게 풀이를 위해선 약간의 아이디어가 필요합니다.

그리고 효율적으로 풀 수 있는 약간의 아이디어도 필요하죠.

 

아무튼 같이 한 번 보죠!

---

문제 요약

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 문제는 문제를 읽으면 "아 일단 이렇게 푸는 거구나" 이런 직관적인 풀이가 먼저 떠오르는데

레벨 3 문제는 그냥 막막합니다. 실제로 이런 아이디어 떠올릴 수 있는 몇 가지 접근법을 정리해보는게 중요하겠어요.

(정렬을 한다던가, 수열 관계가 있는지 등...)

 

입출력 설명을 보면 2번 선수가 [1, 3, 4] 선수에게 패배했고, 5번 선수에게 승리했기 때문에 4위, 그 2번에게 진 5번은 5위라고 합니다. 이게 일단 이해가 안가시는 분은

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

 

이걸 잘 생각해보는게 좋겠습니다. 모든 정보가 공개된 순간 패배한 수 + 1이 자신의 순위가 됩니다.

 

Q. 5번은 정보가 공개되지 않았는데 순위가 정해진걸 어떻게 확인하나요?

역순으로 한 번 가볼까요?

5번은 2번에 졌습니다. 따라서 2번을 이긴 모든 사람은 5번에 이깁니다. 결론적으론 2번에 공개된 [1, 3, 4]번에 진 정보가 5번에게 그대로 적용되면서 모든 정보를 조합해낼 수 있습니다.

 

전 이렇게 한 번 접근해보겠습니다.

1. 어떤 선수에게 진 모든 선수의 배열을 엮어 object로 만든다.(winResult)
2. 진 선수에게 이긴 모든 선수의 배열을 엮어 object로 만든다.(loseResult)
3. 1차적인 정보를 바탕으로 계층정보를 확장한다.
(예를 들어, 4가 3에 이겼으니, 3에게 진 선수를 찾고, 그 선수에게 진 선수를 찾고.. 반복)
4. 계층정보가 정리된 winResult, loseResult에서 각 선수의 정보 조합의 합이 n - 1이면 순위 확정!

 

정답 코드

function makeArrMap(Map, key, val) {
    if (Map.has(key)) {
        const arr = Map.get(key);
        Map.set(key, [...arr, val]);
    } else {
        Map.set(key, [val]);
    }
    return Map;
}

function makeHierarchy(Map, n) {
    for (const [key, value] of Map) {
        const result = [];
        result.push(...value);
        const stack = value;
        const visited = [true, ...Array(n).fill(false)];
        while(stack.length > 0) {
            const currKey = stack.pop();
            if (visited[currKey]) continue;
            else visited[currKey] = true;
            const values = Map.get(currKey);
            if (values) {
                result.push(...values);
                stack.push(...values);
            }
        }
        Map.set(key, [...new Set(result)]);
    }
    return Map;
}

function solution(n, results) {
    let winResult = new Map();
    let loseResult = new Map();
    
    results.forEach((v) => {
        const [winner, loser] = v;
        winResult = makeArrMap(winResult, winner, loser);
        loseResult = makeArrMap(loseResult, loser, winner);
    });
    
    winResult = makeHierarchy(winResult, n);
    loseResult = makeHierarchy(loseResult, n);
    
    let answer = 0;
    for (let i = 1; i <= n; i++) {
        const openInfos = [];
        if (winResult.has(i)) {
            openInfos.push(...winResult.get(i));
        }
        if (loseResult.has(i)) {
            openInfos.push(...loseResult.get(i));
        }
        if (openInfos.length >= n - 1) answer++;
    }
    
    return answer;
}

 

결과

팁 1. 계층 구조 생성에서 시간 초과를 피하는 법

const result = [];
result.push(...value);
const stack = value;
const visited = [true, ...Array(n).fill(false)];
while(stack.length > 0) {
    const currKey = stack.pop();
    if (visited[currKey]) continue;
    else visited[currKey] = true;
    const values = Map.get(currKey);
    if (values) {
        result.push(...values);
        stack.push(...values);
    }
}

 

visited 배열을 만들어서 이미 방문한 선수의 정보라면 탐색을 안해야 시간초과가 나지 않습니다.

최대한 반복을 줄여줍시다!

 

팁 2. 생각해보면 좋을 테스트 케이스

n = 5
result = [[1, 2], [4, 5], [3, 4], [2, 3]]
return 5

출처: https://school.programmers.co.kr/questions/20129

프로그래머스

처음 실행 때 2, 7, 8, 9번이 안되더라구요. 이유는 계층 구조가 아니라 단순히 index 반복으로 처리해줬기 때문입니다.

저 꼬리물기를 도와주는 makeHierarchy 함수를 넣어주는게 이 문제의 킥이네요.

 

점점 아이디어 찾는게 힘드네요. 그냥 능지가 떨어지는 거 같기도하고.. 하하

창의력도 주입식이 되지 않습니까? 그냥 모든 접근법 다 정리해두고 하나하나 체크리스트 처럼 적용해보려고 합니다.

다들 화이팅!

 

그럼 이만!