문제 목록
❤️🔥 디펜스 게임
❌ 실패 코드 (테스트 케이스 실패 & 시간 초과)
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])- 시간 초과가 있다고 하여 시간 복잡도를 최대한 생각하면서 풀었으나 sort나 무적권 스킬 효과로 적군 수를 0으로 만들어 주는 for문에서 다시 i를 초기값으로 돌리는 것 때문에 효율성이 떨어지는 듯 싶다 시간 초과는 그렇다 치더라도 테스트 케이스가 아예 실패했다는 것은 결과 자체가 달랐다는 이야기인데 어떤 경우에 잘못 처리되는 건지를 알 수 없어서 원인을 찾지 못했다...
- 내가 작성한 코드에서는 지금 각 라운드 마다 만나는 적의 수가 담긴 배열 enemy에서 k번째까지 큰 수들의 적 수가 담긴 라운드를 0으로 만들어 주었다. 하지만 생각해 보니 그 0으로 만들어 준 라운드까지 갈 수 있는 보장이 없었다는 거다... 나는 적절한 타이밍에 무적권을 쓴다는 개념 자체를 잘못 이해하고 있었던 것이다. 그래서 구글링을 통해 다른 사람들이 올린 코드를 보았는데 이진탐색으로 풀어야 한다는 것을 알게 되었다. 이진탐색이라는 알고리즘을 알고는 있었지만 어떻게 활용해서 써야 되는지 몰랐기 때문에 이론만으로는 한계가 있다는 것을 뼈져리게 느끼게 됐다. 그래서 스터디 진행할 때는 이해를 하지 못했으므로 내가 작성한 실패 코드를 그대로 들고 가고 다른 분들의 설명을 들으면서 이진탐색에 대해 이해할 수 있었다.
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]);- 객체에 귤의 각 크기마다 존재하는 갯수를 구하여 값을 뽑아와 정렬을 해 준 뒤, 차곡차곡 넣어준 케이스이다. 푸는 알고리즘 자체는 무난했으나 이번 문제를 통해서 얻게 된 것은 hasOwnProperty() 메서드를 알게 되었다. 프로퍼티가 존재 유무를 알 수 있는 메서드를 통해 한결 편하게 작성할 수 있었다. 나는 for of를 돌면서 키가 있는지 확인하고 할당해 주는 형태인데 오늘 스터디를 통해서 키값을 할당하는 방법이 나랑 다른 것들을 볼 수 있었다. 한번쯤은 볼 법도 했을 텐데 내가 검색했을 때는 안 나왔던 코드들이었다... 귤 고르기 자체를 구글링을 안 해서일까나 내가 한 방법을 제외하고 객체에 키가 없을 때 키를 생성하고 값을 할당하는 코드는 다음과 같다.
arrName.forEach( ele => {
if(obj[ele] === undefined) obj[ele] = 0
obj[element] += 1
});
for(ele of arrName){
obj[ele] = (obj[ele] || 0) + 1;
}
아래는 상당이 많이 축약된 형태를 띄우며 뭔가 신선한 느낌이라... 기분이가 좋군... 나도 저렇게 짜고 싶다!!!
또한 지원님을 통해서 키와 값을 가지고 있는 객체 형태를 배열로 그대로 변환하는 메서드를 알게 되었다.
⭐ Object.entries()
- 모든 프로퍼티와 값을 배열로 반환한다.
⭐ Object.fromEntries()
- 키값 쌍의 목록을 객체로 바꿔 준다
추가로 찾아보니 entries()의 반대 개념으로, 배열에서 객체로 바꿔주는 fromEntries() 메서드도 추가로 알 수 있었다.
