난이도: Lv. 2
정답률: 57%
문제: https://school.programmers.co.kr/learn/courses/30/lessons/132265
알고리즘
1. 토핑 종류당 개수가 몇 개 있는지에 대한 Map을 초기화한다.
2. 동생 롤케이크의 토핑 종류를 저장하는 Set을 선언한다.
3. 주어진 토핑 배열 topping의 맨 끝 원소부터 하나씩 2.의 Set에 담고, 1.의 Map의 해당 key의 value를 1 감소시킨다. value가 0이 되는 경우 key를 삭제한다.
4. topping 배열을 순회하며 3의 과정을 반복하고, 반복하는 도중에 Map의 size와 Set의 size가 같아지는 경우 정답을 1 증가시킨다. Set의 size가 Map의 size보다 큰 경우부터는 더 이상 정답의 가능성이 없으므로 반복문을 break 한다.
코드
function solution(topping) {
let answer = 0;
const toppingMap = new Map();
const brotherSet = new Set();
for (let t of topping) {
if (toppingMap.has(t)) {
toppingMap.set(t, toppingMap.get(t) + 1);
} else {
toppingMap.set(t, 1);
}
}
for (let i = topping.length - 1; i >= 0; i--) {
const tp = topping[i];
const getTp = toppingMap.get(tp);
brotherSet.add(tp);
if (getTp === 1) {
toppingMap.delete(tp);
} else {
toppingMap.set(tp, getTp - 1);
}
if (brotherSet.size === toppingMap.size) { answer++; }
else if (brotherSet.size > toppingMap.size) { break; }
}
return answer;
}
주저리
처음에는 Set으로만 풀었는데 시간이 박살 났다. 주어진 토핑 배열을 복사하고 복사본에서 하나씩 pop()해서 동생 롤케이크 Set에 넣어주고 복사본을 Set으로 만들어 두 Set의 크기가 일치하는지 확인했는데 할 때마다 배열을 Set으로 만들어서 시간이 박살 난 것 같다.
function solution(topping) {
let answer = 0;
const toppingCopy = [...topping];
const set1 = new Set();
const toppingSet = new Set(topping);
const minTopping = Math.ceil(toppingSet.size / 2);
while (toppingCopy.length) {
set1.add(toppingCopy.pop());
if (set1.size >= minTopping) {
const set2 = new Set(toppingCopy);
if (set1.size === set2.size) { answer++; }
else if (set1.size > set2.size) { break; }
}
}
return answer;
}
아무리 생각해도 Set으로 푸는 문제인데 도저히 모르겠어서 질문하기 들어갔다가 제목에 Map 풀이라는 거 보고는 안 보고 나와서 Map으로 해서 쉽게 풀었다. 왜 Map으로 풀 생각은 못했을까 바보아녀?
'코딩테스트' 카테고리의 다른 글
[JS] 프렌즈4블록 (0) | 2024.01.17 |
---|---|
[JS] 파일명 정렬 (0) | 2024.01.17 |
[JS] 오픈채팅방 (0) | 2024.01.11 |
[JS] 스킬트리 (0) | 2024.01.10 |
[JS] 땅따먹기 (0) | 2024.01.09 |