[CodeKata] 프로그래머스 : 6.11(금), 보석 쇼핑 / 이중우선순위큐

🥋 Oooth More!! (Level 3) : 보석 쇼핑

 

🧮  풀이

DFS, BFS, 순회 등 다양한 방법으로 풀었지만 정확성 일부오답과, 효율성 시간 초과 등이 있어 좋은 모범답안을 해석했다.

 

🖇 리뷰

function solution(gems){
  var count = new Set(gems).size;
  // 보석 종류가 몇개인지 
  var gemMap = new Map()
  // 보석 종류 => 보석 자리를 저장하기 위한 맵
  var gemLength = []
  // 보석을 모두 포함하는 구간을 저장할 배열 
  gems.forEach((gem, i)=> {
    gemMap.delete(gem)
    gemMap.set(gem, i)
    if(gemMap.size === count){
      gemLength.push([gemMap.values().next().value + 1, i+1])
    }
  })

  gemLength.sort((a,b)=> {
    if(a[1]-a[0] === b[1]-b[0]){
      return a[1]-b[1]
    }
    return (a[1]-a[0])-(b[1]-b[0])
  })
  
  return gemLength[0]
}

* 출처https://velog.io/@diddnjs02/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%B3%B4%EC%84%9D-%EC%87%BC%ED%95%91

 

1. count는 중복되지 않는 보석의 개수다. gemMap은 중복되지 않는 보석들의 순서정의를 위한 Map() 이다.
2. gemLength는 정답이 가능한 [시작, 끝] 인덱스 튜플들의 배열이다. 이들을 저장한 뒤, 마지막에 최소값으로 정렬할 것이다.
3. gems를 순회한다. 우선, 현재 gemMap() 에서 gem을 delete() 로 없애준다. (중복되지 않는 순서를 최신화해야 하므로)
4. 다음, gemMap에 현재 gem을 새로 set() 한다. 이 때, key는 gem, value는 현재의 인덱스인 i로 설정한다.
5. 만약, gemMap.size 가 count와 같다면 모든 보석이 들어온 환경이다. 이 때, gemMap 맨 앞, 뒤의 인덱스를 gemLength에 추가한다.
6. 이렇게 모인 gemLength를 정렬한다. 기준은, 1) (끝-시작) 이 작은 순(sort 아래), 2) 같다면 끝이 먼저인 순(sort 위) 이다.

---

🥋 Oooth More!! (Level 3) : 이중 우선순위 큐

* 출처링크 : http://icpckorea.org/problems/2013/onlineset.pdf

 

🧮  풀이

function solution(operations) {
  var answer = [];
  operations.forEach(op => {
    const [cmd, num] = op.split(" ");
    
    if (cmd === "I") answer.push(Number(num))
    if (cmd === "D" && answer.length > 0) {
      if (num === "-1") {
        const idx = answer.indexOf(Math.min.apply(null, answer));
        answer.splice(idx, 1);
      }
      if (num === "1") {
        const idx = answer.indexOf(Math.max.apply(null, answer));
        answer.splice(idx, 1);
      }
    }
  })
  
  answer.sort((a,b) => b-a);
  
  return answer.length === 0 ? [0, 0] : [answer[0], answer[answer.length-1]]
}

1. answer 배열에 우선 operations 조작에 따라 숫자들을 누적하는 큐가 된다. forEach로 순회한다.
2. 각 요소(op)를 split(" ") 하면, 앞 요소는 조작방법(cmd), 뒤 요소는 숫자(num) 으로 나눠진다.
3. 만약, cmd가 I면 num을 answer에 추가해주면 된다.
4. cmd가 D면 answer 큐에서 값을 지워야 한다. 만약, answer가 비어있다면 생략해야 하므로 answer.length 도 조건으로 건다.
5. num이 -1이면 최소값을, 1이면 최대값을 answer에서 지워준다. (indexOf + splice)
6. 이를 내림차순으로 정렬한다. 길이가 0이라면 [0, 0], 값이 존재하면 맨 앞/뒤값을 튜플로 반환한다.

 

🖇 리뷰

위처럼 풀수도 있고, cmd "I"에서 숫자를 넣고 매번 sort() 하는 방법도 있다. 그럼 "D"는 pop(), shift() 로 조작 가능하다.