[CodeKata] 프로그래머스 : 7.19(월), 여행경로 / 베스트앨범

🥋 Oooth More!! (Level 3) : 여행경로

 

🧮  풀이

function sortTickets(list) {
  return list.sort((a,b) => {
     return a[1] < b[1] ? -1 : 1;
  })
}


function solution(tickets) {
  let answer;
  function dfs(acc, res) {
    if (res.length === 0) {
      answer = [answer, acc].sort().shift();
      return;
    }
    
    const now = acc[acc.length-1];
    
    for (let i in res) {
      const [d, a] = res[i];
      if (d === now) {
        const copiedRes = [...res];
        const [next] = copiedRes.splice(i,1);
        dfs([...acc, next[1]], copiedRes)
      }
    }
  }
  
  tickets.forEach((t, idx) => {
    if (t[0] === "ICN") {
      const rests = [...tickets];
      rests.splice(idx, 1);
      dfs(t, rests)
    }
  })
  
  return answer;
}

1. sortTickets() 경로 정렬 함수

• 가능한 경로가 복수인 경우 알파벳이 빠른 것이 정답이 된다. 이는, 도착경로에만 해당하므로 2번째 요소만 비교하여 소팅한다.

 

2. dfs() 깊이우선탐색 함수

• 먼저, answer는 정답을 관리할 변수이다. 현재 answer 과 dfs()에서 찾은 정답(acc)을 sort() 한 뒤 앞의 요소로 최신화한다.
• dfs()는 acc(경로 누적배열), res(tickets 잔여요소 배열) 두 배열을 인자로 받는다. res가 0인 경우, 위 answer 비교를 진행한다.
• res가 존재한다면 다음 경로를 찾는다. now는 acc 가장 끝 요소로, 현재 도착지이자 다음 출발지가 될 것이다.
• res를 순회하며 1번째 요소(d)가 now와 같은 요소를 찾는다. 조건에 만족하면, copiedRes(복사본)에서 splice() 한다.
• next는 추출한 요소로 다음경로에 해당한다. acc는 누적된 acc + next[1], res는 splice() 후 남은 copiedRes를 넣는다.

 

3. tickets 순회하며 dfs() 적용

• tickets를 순회하며 1번째 요소가 "ICN"인 경우에만 dfs()를 적용한다.
• acc는 출발 및 도착이 모두 들어가야 하므로 요소 자체를(t), res는 tickets 복사본에서 요소만 splice() 한다. (filter는 중복요소 모두 삭제하므로)

 

🖇 리뷰

같은 DFS 방법이나 매우 간결해서 해석해보았다!

나와 이 풀이 모두 중요한 점은 복사본(tmp)를 splice() 해서 이후 로직에 영향을 주지 않는다는 것이다.

function solution(tickets) {
    var answer = [];
    DFS(tickets,'ICN',["ICN"]);

    return answer.sort()[0];
    
    function DFS(t,start,str){
        if(t.length == 0){
            answer.push(str)
        }
        for(var i in t){
            if(t[i][0] == start){
                let tmp = t.slice();
                tmp.splice(i,1);
                let tmp2 = str.slice();
                tmp2.push(t[i][1]);
                DFS(tmp,t[i][1],tmp2)
            }
        }
    }
}

* 출처 : https://programmers.co.kr/learn/courses/30/lessons/43164/solution_groups?language=javascript/ 

 

우선, answer를 모두 수집한 다음, 마지막에 sort() 후 첫 번째 요소만 반환하는 방법이 더 좋은 것 같다.

또한, DFS는 (남은 티켓, 시작점, 누적 경로) 이렇게 인자로 받는다. dfs() 를 재적용할 때, 남은경로 및 누적경로를 tmp 복사본을 꼭 만들어서 적용해야한다.

---

🥋 Oooth More!! (Level 3) : 베스트앨범

 

🧮  풀이

function solution(genres, plays) {
  let genreObj = {};
  
  for (let i = 0 ; i < genres.length ; i++) {
    const genre = genres[i];
    const play = plays[i];
    
    if (!genreObj[genre]) {
      genreObj[genre] = {
        total: play,
        maxs: [[play, i]],
      }
    }
    else {
      genreObj[genre].total += play;
      genreObj[genre].maxs = [...genreObj[genre].maxs, [play, i]]
        .sort((a,b) =>{
          if (a[0] > b[0]) return -1;
          else if (a[0] < b[0]) return 1;
          else {
            return a[1] - b[1];
          }
        })
        .slice(0,2);
    }
  }
  
  return Object.values(genreObj).sort((a,b) => b.total - a.total).reduce((acc, cur) => { return [...acc, ...cur.maxs]}, []).map(e => e[1]);
}

1. genreObj 해시값 저장

• genreObj는 각 장르를 key로, total(재생수 총합) 및 maxs(재생수가 큰 2곡만) 두 값을 value로 관리하는 해시다.
• genres를 순회하며 각 인덱스(i)에 따라, 해당하는 장르명(genre), 재생수(play) 두 값을 변수에 담는다.
• genreObj에 해당 genre 필드가 없다면, total은 현재 재생수(play)를, maxs는 현재곡의 [play, i] 만을 담은 배열로 저장한다.
• genre 필드가 존재하면 값을 갱신해야 한다. total엔 play 값을 더하고, maxs는 현재까지의 maxs와 지금곡 [play, i] 를 합친다.
• 이를 재생수, 인덱스 높은순으로 비교해서 sort() 한다. 그러면, 기존 2개 및 현재 1개의 곡이 정렬되며 이 중 2개만 slice() 한다.  

 

2. genreObj 가공을 통한 정답(인덱스 배열) 반환

• genreObj를 Object.values() 를 통해 value 값들만 가져온다. 장르명은 필요없고, 재생수를 기준으로 비교하기 때문이다.
• 이 배열을 total(총 재생수) 기준으로 정렬한다. 이를, reduce() 를 통해 누적된 acc + maxs 2곡 을 전개 연산자로 누적한다.
• maxs는 튜플로, 첫 번째 값은 재생수, 두 번째 값은 인덱스다. 정답은 인덱스만 필요하므로 e[1]로만 맵핑한다.

 

 

🖇 리뷰

다른 좋은 풀이들도 많지만, 내 방법은 각 장르(필드)에서 total과 maxs(2개씩) 관리하는 효율적인 방법으로 구현되어 매우 뿌듯했다.

또한, 튜플의 sort() 비교, 2개만 관리하기 위한 slice(), genreObj 값들을 배열화하는 reduce() 까지 메서드를 적극적으로 활용했다. 

* slice() 같은 경우에는 상위의 문제(여행경로)와 마찬가지다. 누적한 다음, reduce 때 2개만 추출해도 좋을 것 같다.