Algorithm

[CodeKata] 프로그래머스 : 5.30(일), 순위 & 불량 사용자

ttaeng_99 2021. 6. 1. 01:40
반응형

🥋 Oooth More!! (Level 3) : 순위

* 출처 : http://contest.usaco.org/JAN08.htm

 

🧮 풀이

그래프와 DFS를 통해 풀어보려 했으나 오답률이 높아, 모범답안을 보고 해석리뷰를 하였다.

 

🖇 리뷰

function solution(n, results) {
    var answer = 0;
    const graph = Array.from({ length: n+1 },() => Array(n+1).fill(false));
    results.map((item) => {
        const [win,lose]=item;
        graph[win][lose]=1; //이긴 경우 1
        graph[lose][win]=-1; //졌을 경우 -1
        graph[win][win]=0;//자기자신
        graph[lose][lose]=0;
    })
    
    const range=[...Array(n).keys()].map(e=>e+1);
    for(const mid of range){
        for(const a of range){
            for(const b of range){
                if(graph[a][mid]==1 && graph[mid][b]==1 ){ //a가 mid이기고 mid가 b이김
                    graph[a][b]=1;
                }else if(graph[a][mid]==-1 && graph[mid][b]==-1){//a가 mid한테 지고 mid가 b한테 지면
                
                    graph[a][b]=-1;
                }
            }
        }
    }
    for(const a of range){
        let possible=true;
        for(const b of range){
            if(graph[a][b]===false){
                possible=false;
                break;
            }
        }
        if(possible){
            answer+=1;
        }
    }

    return answer;
}

* 출처 : https://haerang94.tistory.com/330

  1. 먼저, graph 2차원 배열을 만든다. results 배열을 순회하며, [win][lose] 는 1, [lose][win] 은 -1, 자기자신은 0을 대입한다.
  2. range는 각 선수들의 번호가 담겨 있는 배열이다. Array.from() 문법으로도 만들 수 있다.
  3. 이를 3중 순회하며, mid값이 a와 b 사이에 있는 경우 a와 b 사이의 승패관계가 성립될 수 있다. (플로이드 와샬 알고리즘)
  4. 다시, range를 순회하며 빈 값(false)이 있는 경우엔 break, 모두 값이 있다면 승패관계가 정리된 선수이므로 answer을 1 더한다.

 

- 플로이드-와샬(Floyd-Warshall) 알고리즘

 

그래프에서 모든 정점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 이 때, 거쳐가는 정점을 기준으로 알고리즘을 수행하는 것이다.

 

const INF = Infinity;

const floydWarshall = (dist) => {
  const let = dist.length;
  for (let mid = 0 ; mid < len ; mid++) {
    for (let a = 0 ; a < len ; a++) {
      for (let b = 0 ; b < len ; b++) {
        if (dist[a][b] > dist[a][mid] + dist[mid][b]) {
          dist[a][b] = dist[a][mid] + dist[mid][b];
        }
  	  }
    }
  }
};

const solution = (function() {
  const graph = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
  ];
  
  floydWarshall(graph);
  
  return graph;
}());

위 예시는, 두 정점간의 이동경로 vs 특정 정점을 거치는 이동경로 중, 소요시간이 적은 경로를 저장하는 플로이드 와샬 알고리즘이다.

이를 통해, 더 나은 소요시간(혹은 가중치)로 최신화할 수 있으며, 상위 문제처럼 승패를 가중치로 표현하며 그래프 관계도를 짤 수 있다.

🥋 Oooth More!! (Level 3) : 불량 사용자

 

🧮 풀이

function solution(user_id, banned_id) {
  let banList = [];
  banned_id.forEach(id => {
    let list = [];
    let strs = id.split("").reduce((acc, cur, idx) => {
      return cur === "*" ? acc : [...acc, [cur, idx]];
    }, [])

    user_id.forEach(user => {
      if (user.length === id.length && strs.every(str => user[str[1]] === str[0])) {
        list.push(user)
      }
    })
    banList.push(list);
  })
  
  let cases = [];
  
  function dfs(idx, list) {
    if (idx === banList.length) {
      list = JSON.stringify(list.sort());
      if (!cases.includes(list)) {
        cases.push(list)
      }
    }
    
    else {
      for (let ele of banList[idx]) {
        if (!list.includes(ele)) {
          dfs(idx+1, [...list, ele])
        }
      }
    }
  }
  
  dfs(0, [])

  return cases.length;
}

 

1. banList user_id 후보들의 배열 만들기

  • banList 배열은 각각의 banned_id 에 해당될 수 있는 user_id 후보들의 집합을 배열로 저장한다. 이중 forEach로 탐색한다.
  • 먼저, banned_id의 각각의 id를 strs로 편집한다. 이는, *을 제거하고, 글자만 ['글자', '인덱스'] 튜플 형태로 변형한 것이다.
  • 다음으로 user_id를 순회하며, 1) 해당 id와 글자수가 같고, 2) strs의 모든 요소를 만족하는 id값들만을 list에 저장한다.
  • 이렇게, list에 현재 banned_id 경우에 해당될 수 있는 id들이 모이면, 이를 최종적으로 banList에 push() 해준다.

 

2. banList 후보들의 조합을 DFS로 구하기

  • dfs() 함수를 통해 banList의 모든 배열을 순회하며 가능한 경우의 수의 조합들을 만들어 cases 배열에 push() 하는 것이다.
  • dfs() 함수는 idx(인덱스), list(경우의 수 누적배열) 을 매개변수로 받는다. idx가 banList.length와 같다면 탐색이 완료된다.
  • 탐색 완료 시, 배열 비교를 위해 list를 JSON으로 만든다. 이 값이 cases에 없다면 push() 해준다. (개수만 필요하므로 includes() 탐색에 용이한 JSON string으로 담음)
  • 탐색 미완료 시, banList[idx] id 후보들의 배열을 순회하며, 해당 값이 누적하고있는 list에 없는 경우에만 dfs() 를 호출한다.

 

🖇  리뷰

"불량 사용자" 문제의 경우, DFS & BFS 어느 방법을 사용해도 무방하다. (결국은 완전탐색 알고리즘을 구현하는 것이 목적)

다양한 방법들이 있지만, 나와 유사한 방법을 쓴 경우도 있었기에 이 방법을 권장하는 바이다.

 

반응형