[알고리즘/프로그래머스/고득점Kit] 해시(JS)브라운 먹고싶다/..(폰켓몬, 완주하지 못한 선수, 의상, 전화번호 목록, 베스트 앨범)

문제 : 폰켓몬

---

https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=javascript 

프로그래머스

 

풀이

---

function solution(nums) {
    // 종류(Set.size)와 nums.length/2 를 비교
    // 종류가 더 많거나 같으면 길이 리턴, 아니면 종류 리턴. 
    const types = new Set(nums).size
    const len = nums.length/2
    return len <= types ? len : types
}

 

 

---

 

문제: 완주하지 못한 선수

---

https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=javascript 

프로그래머스

 

풀이

---

처음에 아래와 같이 index가 존재하면 splice 하는 방식으로 한 번 풀어봤는데 효율성에서 모두 시간 초과가 났다..ㅎ 

function solution(participant, completion) {
    for (let p of participant) {
        const idx = completion.indexOf(p)
        // 존재하면 completion에서 제거 
        if (idx >= 0) {
            completion.splice(idx, 1)
            continue
        }
        return p
    }
}

 

그래서 해시로 풀어야 했다. 

function solution(participant, completion) {
    // participant 돌면서 개수 저장하고, completion 돌면서 1씩 빼고, 0보다 큰 경우 key를 return 
    const obj = {}
    for (let i=0;i<participant.length;i++) {
        const p = participant[i]
        const c = completion[i]
        obj[p] = (obj[p] || 0) + 1
        obj[c] = (obj[c] || 0) - 1 
    }

    return Object.keys(obj).filter(key => obj[key] > 0).join('')
}

 

---

 

문제: 전화번호 목록 

---

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

프로그래머스

 

풀이

---

function solution(phone_book) {
    const obj = {}
    for (let p of phone_book) {
        obj[p] = 1
    }
    
    for (let p of phone_book) { 
        for (let i=0;i<p.length;i++) {
            const num = p.substring(0, i)
            if (obj[num] && num !== p) return false
        }
       
    }
    return true // 다 돌고 나오면 true 
}

처음에 아무 생각 없이 그냥 for문을 한 번 돌면서 obj에 넣고 확인하고를 했다.. 8, 9, 19번 케이스에서 자꾸 틀려서 왜 그런가 했더니 입력은 정렬이 되어있는 값이 아니었다. 따라서 미리 다 obj에 숫자 값들을 넣어두고 각 입력을 한 인덱스 씩 잘라서 obj에 있나 확인해봐야 했다. 

 

더 쉬운 건 그냥 아래처럼 sort를 해버리고 현재 값이 다음 값의 접두어인지만 확인해 주는 방법이다.

function solution(phone_book) {
    phone_book.sort()
    
    for (let i=1;i<phone_book.length;i++) { 
        // 현재 값이 다음 값의 접두어인지 확인
        if (phone_book[i].indexOf(phone_book[i-1]) === 0) return false
    }
    return true 
}

위와 같이 indexOf로 시작 위치가 0인지 확인하거나 startsWith으로 판단할 수도 있다. 

 

---

 

문제:  의상

---

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=javascript 

프로그래머스

 

풀이

---

function solution(clothes) {
    // clothes 종류별로 개수 저장, (각 개수 + 1)을 곱해서 -1
    const types = {}
    for (let [name, type] of clothes) {
        types[type] = (types[type] || 0) + 1
    }
    
    return Object.values(types).reduce((acc, cnt) => acc * (cnt+1), 1) - 1
}

 

---

 

문제:  베스트 앨범

---

https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=javascript 

프로그래머스

 

풀이

---

function solution(genres, plays) {
    /** 
    * 장르별 합 : { 장르 : 플레이 횟수 }를 구해서 많이 재생된 장르 순으로 sort
    * 장르별 재생된 곡 : { 장르: [[idx, 횟수]] }
    * 재생된 장르를 배열로 만들어서 for문 돌면서 곡 배열을 횟수 순으로 정렬. 
    * 많이 재생된 순으로 곡들을 인덱스 오름차순, 재생횟수 내림차순으로 정렬. 인덱스만 return
    */
    const sum = {}
    const songs = {}
    for (let i=0;i<genres.length;i++) {
        const gen = genres[i]
        const play = plays[i]
        sum[gen] = (sum[gen] || 0) + play
        songs[gen] = (songs[gen] || [])
        songs[gen].push([i, play])
    }
    
    const sortedTypes = Object.keys(sum).sort((key1, key2) => sum[key2] - sum[key1]) 
    const sortedSongs = sortedTypes.reduce((acc, type) => {
    	// 인덱스 오름차순, 재생횟수 내림차순 정렬
        acc.push(...songs[type].sort(([i1], [i2]) => i1 - i2)
                 .sort(([i1, p1], [i2, p2]) => p2 - p1).slice(0, 2))
        return acc
    }, [])

    return sortedSongs.map(([idx, _]) => idx)
  
}

이런 방법 말고도 { 인덱스와 장르, 재생횟수 }를 하나의 객체로 묶어서 푸는 방법도 있어서 도전해봤다. 처음 푼 건 구조가 복잡해서 정렬이 어려웠는데, 이렇게 하니까 좀 더 직관적이었다. 정렬도 if 문으로 순차적으로 처리해서 가독성이 좋은 거 같다.

마지막에 각 장르별로 2개까지만 가져오는 부분은 해시로 하나씩 더해가면서 2개 이상이면 false를 리턴하여 filter하면 된다.

function solution(genres, plays) {
  /**
   * 장르별 합을 sum에 저장
   * genres 돌면서 {인덱스, 장르, 재생횟수} 객체 생성
   * 장르 재생횟수 내림 -> 곡 재생횟수 내림 -> 인덱스 오름차순으로 sort. 2개까지 자르고 idx만 return
   */
  const playsByGenre = {};
  const obj = {};
  for (let i = 0; i < genres.length; i++) {
    const gen = genres[i];
    playsByGenre[gen] = (playsByGenre[gen] || 0) + plays[i];
  }
  

  return genres
    .map((genre, idx) => ({ idx, genre, play: plays[idx] }))
    .sort((a, b) => {
      if (a.genre !== b.genre) return playsByGenre[b.genre] - playsByGenre[a.genre];
      if (a.play !== b.play) return b.play - a.play;
      return a.idx - b.idx;
    })
    .filter(({ genre }) => {
      obj[genre] = (obj[genre] || 0) + 1;
      if (obj[genre] <= 2) return true;
      return false;
    })
    .map(({ idx }) => idx);
}