[JS] 프로그래머스 보석 쇼핑
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/67258
첫 트라이
일단 무식하게..
첫 인덱스부터 순회하여 만족되는 구간중 최단구간을 구했다.
2중for문이라 뻔히 시간초과될걸 알았지만.. 허헣
function solution(gems) {
var answer = [];
const db = new Set(gems);
if (db.size === 1) return [1, 1]
gems.forEach((gem, idx) => {
const visit = {};
[...db].forEach(el => visit[el] = 1);
visit[gem] = 0;
var targetLen = db.size - 1, nextIdx = idx;
for (; nextIdx < gems.length; nextIdx++) {
const target = gems[nextIdx];
if (visit[target]) {
targetLen--;
if (targetLen === 0) break;
visit[target] = 0;
}
}
if (!targetLen) answer.push([idx + 1, nextIdx + 1]);
})
return answer.reduce((ac, v) =>
ac[1] - ac[0] > v[1] - v[0] ? v : ac, [1, gems.length]);
}
다시 풀이
슬라이딩 윈도우 알고리즘
이론상 O(n)
-
순차적으로 윈도우를 확장해간다.
AA BBBB AA AA CC DD AA
AA: 1, BB: 2 -
중복이 발생할 때 index를 덥어 씌운다.
AA BB BBAA AA CC DD AA
AA: 1, BB: 3 -
조건에 만족되면 알맞은 형태로 정답후보로 변경 -> 정답과 비교
AA BB BB AA AA CC DDAA
AA: 5, BB: 3, CC: 6, DD: 7 -> [3, 7]
AA BB BB AA AA CC DD AA
AA: 8, BB: 3, CC: 6, DD: 7 -> [3, 8]
function solution(gems) {
const cnt = new Set(gems).size;
const gemMap = {};
var answer = [1, gems.length];
gems.forEach((gem, i) => {
gemMap[gem] = i;
const target = Object.values(gemMap);
if (target.length === cnt) {
const cand = [Math.min(...target) + 1, i + 1];
answer = answer[1] - answer[0] > cand[1] - cand[0] ? cand : answer;
}
})
return answer;
}
전개연산자... 와 Math.min
, Object.values
로 배열 길이를 구하는 과정이 생각보다 많이 무거운 것 같다.
최종코드
다른 분들처럼.. Map 객체를 써서 쉽게 size를 구할 수 있고
Map은 삽입 순서를 유지해주기에 min 비교연산이 필요 없다.
function solution(gems) {
const cnt = new Set(gems).size;
const gemMap = new Map();
var answer = [1, gems.length];
gems.forEach((gem, i) => {
gemMap.delete(gem);
gemMap.set(gem, i);
if (gemMap.size === cnt){
const cand = [gemMap.values().next().value + 1, i + 1];
answer = answer[1] - answer[0] > cand[1] - cand[0] ? cand : answer;
}
})
return answer;
}
Map을 애용하도록 하자..
코드 추가
공식 문제 해설을 참고하여 다시 작성해봤다
https://tech.kakao.com/2020/07/01/2020-internship-test/
더 직관적인 알고리즘인 것 같다.
- 조건이 만족될 때까지 right++ (빈도수 +1)
- 조건이 만족되면 left++ (빈도수-1, 빈도수 0이 되면 Map에서 삭제)
- right이 범위를 초과할 때까지 반복
function solution(gems) {
const cnt = new Set(gems).size;
var ans = [1, gems.length];
var l = 0, r = 0;
const hit = new Map();
hit.set(gems[0], 1)
while (r < gems.length) {
if (hit.size === cnt) {
if(ans[1] - ans[0] > r - l)
ans = [l + 1, r + 1]
hit.set(gems[l], hit.get(gems[l]) - 1);
if (hit.get(gems[l]) === 0)
hit.delete(gems[l])
l++;
}
else {
r++;
const right = hit.get(gems[r]);
hit.set(gems[r], right ? right + 1 : 1);
}
}
return ans;
}
Author And Source
이 문제에 관하여([JS] 프로그래머스 보석 쇼핑), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bepyan/JS-프로그래머스-보석-쇼핑저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)