프로그래머스 LEVEL 3(순위)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-12-27

  • 해결 방법 :

    • graph 초기화
    • results를 돌며 graph에 승, 패 update
      • 이 때 승리한 경우는 양수, 패배한 경우는 음수로 update
    • 1부터 n까지 돌며
      • graph[i]에서 0보다 작은 경우(i를 이긴 선수들) winI와, 0보다 큰 경우(i한테 진 선수들) loseI를 filter
      • i를 이긴 선수는 i를 진 선수를 무조건 이기고, i한테 진 선수는 i가 이긴 선수한테 무조건 지므로 이 로직을 update
    • 각 i 별 이기고 진 선수의 수가 n - 1인 경우(본인 제외 나머지가 다 0이 아닌 경우) answer 증가

  • 회고 :

    • x

  • 코드

    function solution(n, results) {
  let answer = 0;
  const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

  for (const [w, l] of results) {
    graph[w][l] = l;
    graph[l][w] = -w;
  }

  for (let i = 1; i <= n; i++) {
    const winI = graph[i].filter((node) => node < 0);
    const loseI = graph[i].filter((node) => node > 0);

    for (const w of winI) {
      for (const l of loseI) {
        graph[-w][l] = l;
      }
    }
    for (const l of loseI) {
      for (const w of winI) {
        graph[l][-w] = w;
      }
    }
  }

  for (let i = 1; i <= n; i++) {
    if (graph[i].filter((node) => node !== 0).length === n - 1) answer += 1;
  }

  return answer;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges