문제 목록
❌ 실패 코드 (테스트 케이스 실패 & 시간 초과)
function solution(n, k, enemy) {
//! 시간 초과 있다니까 시간 복잡도 생각하면서 푸셈
// 준호 디펜스 게임 폐인됨
// 매 라운드마다 enemy[i]마리 등장
// 병사 n명 enemy[i]는 1대1임
// 7 - 2 남은 병사 = 5
// 무적권 스킬을 k번 사용할 수 있음 무적권은 병사를 소모하지 않고 한 라운드 넘길 수 있음.
// 무적권 스킬은 적이 많을 때 사용해야 개이득이니까 enemy 정렬해서 k번째까지 쓰면 됨
// 내림차순 정렬 후 k번까지 쓸 거임
let enemyRound = [...enemy];
let goodTiming = enemyRound.sort((a, b) => b - a);
console.log(goodTiming)
console.log(enemy)
// 무적권 써야 되는 적군인 수만 추출
skill = goodTiming.slice(0, k);
console.log(skill)
//! 적절한 시기에 무적권의 스킬 효과로 적군 수를 0으로 만들어 줌
// 무적권 써야 되는 적군인 수와 enemy[i]번째가 같다면 해당 enemy[i]에 스킬 효과로 적군의 수가 0이 됨
// skill을 한 번 썼으니 shift
// 무적권 써야 되는 적군인 수를 다시 enemy의 처음부터 찾아야 하므로 i를 -1로 주고 증감이 돼서 0번째 인덱스부터 시작
for (let i = 0; i < enemy.length; i++) {
if (skill[0] === enemy[i]) {
enemy[i] = 0;
skill.shift();
i = -1;
}
}
console.log(enemy)
//? 라운드를 돌면서 아군이 적군보다 크거나 같으면 적군의 수만큼 아군을 잃음
//? 그렇지 않다면 아군이 이길 수 있는 병력이 아니니 깰 수 없는 라운드므로 return round
for(let round = 0 ; round < enemy.length ; round++){
if(n >= enemy[round]){
n -= enemy[round];
} else {
console.log(round)
return round;
}
}
console.log(enemy.length)
return enemy.length
}
solution(7,3, [4, 2, 4, 5, 3, 3, 1])
function solution(n, k, enemy) {
let left = 0;
let right = enemy.length;
const getSum = (index) => (index + 1 - k >= 0 ? enemy
.slice(0, index + 1)
.sort((a, b) => a - b)
.slice(0, index + 1 - k)
.reduce((acc, cur) => acc + cur, 0) : 0);
while (true) {
if (right - left === 1) return right;
@@ -21,4 +20,89 @@ function solution(n, k, enemy) {
right = mid;
}
}
}
// // 왜 위에 풀이는 통과를 하고? 왜 아래 풀이는 채점 통과를 못하는가?ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
// function solution(n, k, enemy) {
// /* 씁..테케 통과는 되는데, 제출이 안돼서 검색 :파라메트릭 서치(이진탐색) 및 큐 문제라고 한다.
// mid의 위치에서 지금 가진 n명의 병사와 k개의 무적권으로 막을 수 있다면 L을 mid+1로 옮긴다.
// - 막을 수 있는지 어케암?
// -> mid 까지의 라운드개수에 - k개의 무적권 사용해서 =남은 라운드의 적수 총합을 구해서
// -> n명의 병사보다 작은지 확인한다.
// 막을 수 없다면 R을 mid 로 옮기고 원래있던 mid의 위치는 새로 설정된 L,R 중간으로 다시 조정하여 범위를 좁힌다
// 중요한건 L의위치가 방어여부를 결정한다. L 미만까지는 다 방어가능 L 이상부터는 방어불가능으로 보고 범위를 좁혀나간다.
// 범위를 계속 좁히고 좁혀서 L위치 인덱스가 R위치 인덱스보다 크거나 같아지면 바로 L인덱스 위치를 리턴한다.
// */
// let left = 0
// let right = enemy.length;
// /* [4, 2, 4, 5, 3, 3, 1] k=3 n=7
// idx 0 1 2 3 4 5 6
// pos L M R
// val 0 3.5->3 7
// */
// // mid의 위치에서 현재 자원으로 방어할 수 있나 확인하기
// const sumTillMid = (midIdx) => (midIdx + 1 - k >= 0 ? enemy //무적권으로 모든 라운드커버가 불가능하면
// .slice(0, midIdx + 1) //에너미 배열의 중간라운드까지 잘라서 (slice end미포함 이니까 +1) [4,2,4,5]
// .sort() //오름차순해서 적은 수의 적들만 n명의 병사로 상대, 많은적수는 k무적권을 쓴다. [2,4,4,5]
// .slice(0,midIdx+1 - k) //많은 적수의 라운드를 k무적권을 사용하여 빼주고 k=3 -> 4-3 ->slice(0,1) [2]
// .reduce((acc,cur)=> acc+cur,0) : 0); //남은 앞에 라운드 적수들을 다 더한다. 병사2명으로 mid 까지 방어가능
// while(true){
// if (left >= right) return left;
// let mid = Math.floor((left+right)/2);
// n >= sumTillMid(mid) //n=7, sumTillMid 의값은 2로 트루
// ? left = mid+1 //left의 위치를 mid+1인 4로 옮기고 다시반복. (mid(3)까지 방어가능인거 확인했으니까 그다음자리로 옮기는것.)
// : right = mid;
// }
// }
// /*2트 [4, 2, 4, 5, 3, 3, 1] k=3 n=7 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
// idx 0 1 2 3 4 5 6
// pos L M R
// val 4 5 7
// const sumTillMid = (midIdx) => (midIdx + 1 - k >= 0 ? enemy
// .slice(0, midIdx + 1) //(slice end미포함 이니까 +1) [4,2,4,5,3,3]
// .sort() //오름차순해서 적은 수의 적들만 n명의 병사로 상대, 많은적수는 k무적권을 쓴다. [2,3,3,4,4,5]
// .slice(0,midIdx+1 - k) //많은 적수의 라운드를 k무적권을 사용하여 빼주고 k=3 -> 6-3 ->slice(0,3) [2,3,3]
// .reduce((acc,cur)=> acc+cur,0) : 0); //남은 앞에 라운드 적수들을 다 더한다. 병사8명있어야 현재 Mid위치 라운드까지 방어가능
// n >= sumTillMid(mid) //n=7, sumTillMid 값은 8로 폴스
// ? left = mid+1
// : right = mid; //right의 위치를 mid인 5로 옮기고 다시반복. (현재 L=4, M=4.5, R=5)
// 3트 [4, 2, 4, 5, 3, 3, 1] k=3 n=7 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
// idx 0 1 2 3 4 5 6
// pos LM R
// val 44 5
// const sumTillMid = (midIdx) => (midIdx + 1 - k >= 0 ? enemy
// .slice(0, midIdx + 1) //(slice end미포함 이니까 +1) [4,2,4,5,3]
// .sort() //오름차순해서 적은 수의 적들만 n명의 병사로 상대, 많은적수는 k무적권을 쓴다. [2,3,4,4,5]
// .slice(0,midIdx+1 - k) //많은 적수의 라운드를 k무적권을 사용하여 빼주고 k=3 -> 5-3 ->slice(0,2) [2,3]
// .reduce((acc,cur)=> acc+cur,0) : 0); //남은 앞에 라운드 적수들을 다 더한다. 병사 5명 있어야 현재 Mid위치 라운드까지 방어가능
// while(true){
// if (left >= right) return left;
// n >= sumTillMid(mid) //n=7, sumTillMid 의 값은 5로 트루
// ? left = mid+1 //left 위치를 mid+1인 5로 옮기고 다시반복하려고 보니 (현재 L=5 R=5) 다음 while 반복에서 if문 충족 리턴 left
// : right = mid;
// */
이진탐색 말고 최소 힙으로 푸신 효근님의 코드도 참고하면 좋을 것 같다.
function solution(n, k, enemy) {
// 시간이 실패가 계속 나오니깐 최소 힙을 사용해 보자
// 임시의 합을 담는 공간 temp를 만든다.
// 무적권을 쓴 값을 담는 배열 skill을 만든다
// 무적권의 총합과 n의 값의 합인 temp를 만든다.
// enemy의 누적합인 enemySum을 만든다.
// skill의 합을 구해주는 함수 sumSkill을 만든다.
// enemy를 순회한다.
// skill 배열의 길이가 k보다 작을 경우 계속 넣어주고 sort 해준다
// skill 배열의 마지막 값보다 enemy의 값이 더 클 경우 있던 값을 pop해주고 큰 값을 push 해준다.
// temp와 enemySum을 비교하여 temp가 작으면 멈춤
// answer의 값을 올려준다.
let answer = 0;
const skill = new MinHeap();
let skillSum = 0;
let temp = 0;
let enemySum = 0;
for(let i = 0; i < enemy.length ; i++){
if(skill.size() < k){
// push
skill.heappush(enemy[i]);
skillSum += enemy[i];
} else if(skill.getMin() < enemy[i]){
// pop
skillSum -= skill.heappop();
skill.heappush(enemy[i]);
skillSum += enemy[i];
}
temp = n + skillSum;
enemySum += enemy[i];
// console.log(skill, skillSum, enemySum);
if(temp < enemySum){
break;
}
answer++;
}
return answer;
}
class MinHeap {
constructor() {
this.heap = [ null ];
}
size() {
return this.heap.length - 1;
}
getMin() {
return this.heap[1] ? this.heap[1] : null;
}
swap(a, b) {
[ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
}
heappush(value) {
this.heap.push(value);
let curIdx = this.heap.length - 1;
let parIdx = (curIdx / 2) >> 0;
while(curIdx > 1 && this.heap[parIdx] > this.heap[curIdx]) {
this.swap(parIdx, curIdx)
curIdx = parIdx;
parIdx = (curIdx / 2) >> 0;
}
}
heappop() {
const min = this.heap[1];
if(this.heap.length <= 2) this.heap = [ null ];
else this.heap[1] = this.heap.pop();
let curIdx = 1;
let leftIdx = curIdx * 2;
let rightIdx = curIdx * 2 + 1;
if(!this.heap[leftIdx]) return min;
if(!this.heap[rightIdx]) {
if(this.heap[leftIdx] < this.heap[curIdx]) {
this.swap(leftIdx, curIdx);
}
return min;
}
while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]) {
const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
this.swap(minIdx, curIdx);
curIdx = minIdx;
leftIdx = curIdx * 2;
rightIdx = curIdx * 2 + 1;
}
return min;
}
}
function solution(k, d) {
// 원점 (0, 0)으로부터 x축 방향으로 a*k, y축 방향으로 b*k만큼 떨어진 위치에 찍고
// 원점이랑 거리가 d가 넘으면 점 안 찍음
// 원의 방정식을 이용
let result = 0;
for (let x = 0; x <= d; x += k) {
let y = parseInt(Math.sqrt(d * d - x * x));
result += parseInt(y / k) + 1;
}
return result;
}
solution(2, 4);
function solution(k, tangerine) {
// 경화는 과수월에서 귤을 수확
// 수확한 귤 중 k개를 골라서 상자 하나에 담아 판매하려고 함
// 수확 귤의 크기가 일정하지 않아서 크기별로 분류해 서로 다른 종류의 수를 최소화하고 싶어함
// [1, 3, 2, 5, 4, 5, 2, 3]
// 5 5 2 2 3 3
// 각자 귤의 개수를 구해서 많은 순서대로 넣기
// 크기별로 객체 만들어 주기
let size = {};
for (let type of tangerine) {
// 귤의 크기 객체 속성이 없다면 키를 만들어 주고 초기 키값으로 0으로 설정
//? hasOwnProperty(): 파라미터로 전달된 속성이 객체에 존재하면 true 반환
if (!size.hasOwnProperty(type)) {
size[type] = 0;
}
size[type] += 1;
}
// 키값만 가지고 오기
size = Object.values(size);
console.log(size);
// 최소한의 종류를 넣으려면 크기가 큰 것부터 넣으면 됨
size.sort((a, b) => b - a);
console.log(size);
let result = 0;
for (const ele of size) {
result += 1;
k -= ele;
if (k <= 0) break;
}
console.log(result);
return result;
}
solution(4, [1, 3, 2, 5, 4, 5, 2, 3]);
arrName.forEach( ele => {
if(obj[ele] === undefined) obj[ele] = 0
obj[element] += 1
});
for(ele of arrName){
obj[ele] = (obj[ele] || 0) + 1;
}
아래는 상당이 많이 축약된 형태를 띄우며 뭔가 신선한 느낌이라... 기분이가 좋군... 나도 저렇게 짜고 싶다!!!
또한 지원님을 통해서 키와 값을 가지고 있는 객체 형태를 배열로 그대로 변환하는 메서드를 알게 되었다.
추가로 찾아보니 entries()의 반대 개념으로, 배열에서 객체로 바꿔주는 fromEntries() 메서드도 추가로 알 수 있었다.