Portfolio

🔎 문제

school.programmers.co.kr

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

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

그래프

플루이드 알고리즘

코드


const solution = (n, results) => {
  let answer = 0;
  // 2차원 배열 그래프 생성
	const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(false));
	results.map((value) => {
		const [win, lose] = value;
		graph[win][lose] = 1;
		graph[lose][win] = -1;
		graph[win][win] = 0;
		graph[lose][lose] = 0;
	});
	const players = [...Array(n).keys()].map((e) => e + 1);
  // 플루이드-워셜 알고리즘
	for (const mid of players) {
		for (const a of players) {
			for (const b of players) {
				// a, b, mid 승패 결정
				if (graph[a][mid] === 1 && graph[mid][b] === 1) graph[a][b] = 1;
				if (graph[a][mid] === -1 && graph[mid][b] === -1)
					graph[a][b] = -1;
			}
		}
	}
    
	// false가 하나도 없는 선수만 answer+1
	for (const player of players) {
		let hasFalse = false;
    // false 체크
		for (const otherPlayer of players) {
			if (graph[player][otherPlayer] === false) {
				hasFalse = true;
				break;
			}
		}
		answer += hasFalse ? 0 : 1;
	}
	return answer;
};

정은

구현

그래프 구현- 이차원 배열 : 이긴 경우 1

처음에 이긴 경우 1을 할당

삼단 논법 처럼 i > k, k>j 이면 i>j 이다를 사용

최종적으로 같은 행과 열의 1합이 n-1이라면 파악이 다 됐다는 걸로 판단하고 answer+1

코드


function solution(n, results) {
    let answer = 0;
    let record = new Array(n).fill(0).map(val => new Array(n).fill(0));    
    
    for (const result of results) {
        const [winner, looser] = result;
        
        record[winner-1][looser-1] = 1;
    }
        
    for (let i=0; i<n; i++) {
        for (let j=0; j<n; j++) {
            for (let k=0; k<n; k++) {
                if (record[j][i] && record[i][k]) {
                    record[j][k] = 1;
                }
            }
        }
    }
    
    for (let i=0;i<n;i++) {
        let sum = 0;
        for (let j=0; j<n; j++) {
            sum += record[i][j]+record[j][i];
        }
        if (sum === n-1) {
            answer++;
        }
    }
            

    return answer;
}

종혁

구현

선수의 수가 최대 100명이기 때문에, 이차원 배열로 각 승패를 1 / -1로 초기화

정확하게 순위를 알 수 있다는 말은 곧 다른 선수들과의 경기 결과를 모두 알아야 한다는 의미

bfs를 통해 구현

코드


function solution(n, results) {
   const ranking = Array.from(Array(n+1),() => Array(n+1).fill(0))
   for(const [win,lose] of results){
       ranking[win][lose] = 1
       ranking[lose][win] = -1
   }
   //a가 b를 이겼다 => b가 c를 이겼으면 a의 입장에서는 c를 이김
    const checkWinCase = (target,total) => {
        const isUsed = Array(n+1).fill(0)
        isUsed[target] = 1
        total[target] = 1
        const queue = [target]
        while(queue.length){
            const linkedPlayer = queue.shift()
            for(let i=1;i<=n;i++){
                const status = ranking[linkedPlayer]
                if(isUsed[i]){continue}
                if(status[i] === 1){
                    isUsed[i] = 1
                    queue.push(i)
                    total[i] = 1
                }
            }
        }
    }
  //a가 b를 이겼다는 소리는 -> a는 b에게 진 사람들을 다 이겼다는 소리이기 때문에 , b의 전적을 조사하면서 b가 진 사람들을 표시해줌
    const checkLoseCase = (target,total) => {
        const isUsed = Array(n+1).fill(0)
        isUsed[target] = 1
        total[target] = 1
        const queue = [target]
        while(queue.length){
            const linkedPlayer = queue.shift()
            for(let i=1;i<=n;i++){
                const status = ranking[linkedPlayer]
                if(isUsed[i]){continue}
                if(status[i] === -1){
                    isUsed[i] = 1
                    queue.push(i)
                    total[i] = 1
                }
            }
        }
        }
    
    let count = 0
    for(let i=1;i<=n;i++){
        const total = new Array(n+1).fill(0)
        checkWinCase(i,total)
        checkLoseCase(i,total)
        // console.log(total) -> 각 선수당 경기 결과가 담기고 0이 하나라도 있다면 정확히 순위를 모름, 
        total.filter((v) => v === 0).length === 1 ? count ++ : null
    }
    //[4,3] [3,2] [2,5]
    //4의 경우 3번에게 이김 -> 3번은 2번에게 이겼기 떄문에 4번은 2번에게 무조건 이김 -> 2번은 5번에게 이겼기 때문에 4번은 5번에게 무조건 이김 ...
    return count
}

재웅

구현

정확하게 선수를 매긴다? 승리를 했던, 패배를 했던 n개 만큼의 간선을 갖고 있어야 함 + 단방향 그래프

일단 노드별 간선 정보를 담은 인접리스트가 필요할 듯 함

승리와 패배 리스트를 각각?

만약 순위를 낼 수 있는 선수 (나, 승, 패 전적의 총합이 n인 경우) => 패배 횟수 + 1이 본인 등수임 ~~만약 2등이나 N-1등이 확정된 경우, 추가적인 계산이 가능할 수 있음~~ → 순위가 확정된 선수를 바탕으로 추가적인 순위를 추론할 수 있어야 함

이후로는 해설을 참고하였음

코드

순위를 낼 수 있는 선수만


function solution(n, results) {
    const winnerGraph = Array.from({length: n}, () => []);
    const looserGraph = Array.from({length: n}, () => []);
    
    for(result of results){
        const [winner,looser] = result
        winnerGraph[winner-1].push(looser)
        looserGraph[looser-1].push(winner)
    }
    
    const score = []
    for(let i=0;i<n;i++){
        if(winnerGraph[i].length + looserGraph[i].length + 1 === n) score.push([i+1,looserGraph[i].length+1])
    }
    console.log(winnerGraph)
    console.log(looserGraph)
    console.log(score)
}

>> winnerGraph : [ [ 2 ], [ 5 ], [ 2 ], [ 3, 2 ], [] ]
>> looserGraph : [ [], [ 4, 3, 1 ], [ 4 ], [], [ 2 ] ]
>> [ [ 2, 4 ] ]

(1)을 바탕으로 순위를 추론 (해설을 참고하였음)


function solution(n, results) {
    const winnerGraph = Array.from({length: n}, () => []);
    const looserGraph = Array.from({length: n}, () => []);
    
    for(result of results){
        const [winner,looser] = result
        winnerGraph[winner-1].push(looser)
        looserGraph[looser-1].push(winner)
    }
    
    const score = []
    
    for(let i=0;i<n;i++){
        if(winnerGraph[i].length + looserGraph[i].length + 1 === n) score.push([i+1,looserGraph[i].length+1])
    }
    
    for(let j=0;j<n;j++){
        for(const winner of looserGraph[j]){
            if(!winnerGraph[winner]) continue
            for( const looser of winnerGraph[j]){
                winnerGraph[winner].push(looser)
            }
        }
        
        for(const looser of winnerGraph[j]){
            if(!looserGraph[looser]) continue
            for( const looser of looserGraph[j]){
                looserGraph[looser].push(winner)
            }
        }
    }
    console.log(looserGraph)
}

참고했던 해설


const solution = (n, results) => {
	const rangeN = [...Array(n).keys()].map((e) => e + 1);
	// key: winner, value : Set([losers])
	const wins = {};
	// key: loser, value : Set([winners])
	const loses = {};
	rangeN.map((key) => {
		wins[key] = new Set([]);
		loses[key] = new Set([]);
	});

	// 승패 결과 저장
	results.map((val) => {
		const [winner, loser] = val;
		wins[winner].add(loser);
		loses[loser].add(winner);
	});

	rangeN.map((i) => {
		// i 선수를 이긴 선수(losers[i])는 i 선수에게 패한 선수들(wins[i])도 이김
		for (const winner of [...loses[i]]) {
			if (!wins[winner]) continue;
			for (const loser of wins[i]) {
				wins[winner].add(loser);
			}
		}
		// i 선수에게 패한 선수는 i선수를 이긴 선수들에게도 패함
		for (const loser of [...wins[i]]) {
			if (!loses[loser]) continue;
			for (const winner of loses[i]) {
				loses[loser].add(winner);
			}
		}
	});

	return rangeN.reduce(
		(ans, i) => (wins[i].size + loses[i].size === n - 1 ? ans + 1 : ans),
		0
	);
};

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

그래프+플루이드-워셜 알고리즘 영상을 다시 보고 풀어봐야겠다.

👧🏻

정은

(시행착오1) 처음 배열을 초기화할 때 let record = new Array(n).fill(new Array(n).fill(0)); 로 선언했었다.

fill 함수는 같은 참조를 배열 각 원소에 할당한다. 즉, 모든 원소가 같은 참조를 공유하게 된다.

(시행착오2) let record = new Array(n).map(val => new Array(n).fill(0));

map 함수는 해당 원소가 값이 empty면 넘어가는데, new Array(n) 는 원소가 empty인 배열을 생성한다.

(시행착오3) 플로이드-워셜 알고리즘은 반복문의 변수 순서가 중요하다..! 중간 변수를 반복문 최하단으로 했었다.

중간 변수를 최상단으로 두고 반복문을 돌려야한다.

중간변수가 이긴 변수, 진 변수를 찾기 위해 이중 반복문을 또 돌려야 함
즉, 중간 변수의 행과 열에서 1을 다 찾고 서로의 열과 행을 연결해줘야 함

tmi) 수정 전에 잘못된 3중 for문을 두번 작성했더니 통과됐었다. 🙄 (얻어걸림ㅎ)

(의문인 점) 만약 한 중간변수 연산을 끝낸 이후, 이 알고리즘으로 인해 해당 중간변수의 이기거나 진 전력이 추가된다면?

해당 변수를 중간으로 해서 2중 for문을 다시 돌려줘야 하는거 아닐까..?

그래프는 아직 살짝 감이 안와서 연습을 더 해봐야 할 것 같다.

👦🏻

종혁

와살-플루이드 알고리즘을 알고는 있었는데, 이 문제에서 쓰이는 건줄은 몰랐다

👦🏻

재웅

접근은 좋았으나 구현 도중에 막혀 해설을 참고하였고, 플로이드 와샬이라는 특정 알고리즘이 적용된다는 것을 알았음

좀 더 찾아보고 리팩토링해봐야겠다 ..