알고리즘
도망친 곳에 낙원은 없었다 - 끝내 나를 놓아주지 않는 명예의 전당
으아아아악!!!! 진짜 으아아ㅏ아아아아아아아아악!!!!!!!!!
콜라 문제를 풀다가 못풀겠어서 명예의 전당으로 넘어왔는데, 이것도 도무지 풀이가 안 되긴 마찬가지였다.
k가 score의 길이보다 클 경우도 생각해서 if (k > score.length) 인 경우를 걸어 따로 return을 했는데도 이런다.
아래는 어질어질한 길이의, 9번과 11번을 통과하지 못한 나의 코드.
// 스코어중 최하위 k개 점수를 명예의 전당에 등록시키고, 가장 최하위 점수를 발표하는 시스템
// 찾아달라는건 매일의 최하위 점수를 기록한 배열 -> 이건 명예의전당 배열부터 필요하다
function findLeastScore (k, score) {
const hallOfFame = [];
const leastScores = [];
// k가 더 클경우를 생각해야 함
// 만약 k = 6이고 score [50, 400, 30, 25] 라면 50, 50, 30, 25, 25, 25 가 될것
if (k > score.length) {
for (let i = 0; i < score.length; i++) {
hallOfFame.push(score[i]);
hallOfFame.sort((a,b) => b - a);
leastScores.push(hallOfFame[hallOfFame.length-1]);
}
for (let i = 0; i < k - score.length; i++) {
leastScores.push(hallOfFame[hallOfFame.length-1]);
}
return leastScores;
}
for (let i = 0; i < k; i++) {
hallOfFame.push(score[i]);
hallOfFame.sort((a,b) => b - a);
leastScores.push(hallOfFame[hallOfFame.length-1]);
}
// 명전배열 꽉 찼으면서 명전점수보다 score 쪽이 크면 명전쪽을 갈아치운다
// pop으로 최하점 썰고, findIndex로 score보다 큰 값 찾아서 splice로 중간에 끼워넣자
for (let i = k; i < score.length; i++) {
const idx = hallOfFame.findIndex((el) => el < score[i]);
if (idx !== -1) {
hallOfFame.pop();
hallOfFame.splice(idx, 0, score[i]);
}
hallOfFame.sort((a,b) => b - a);
leastScores.push(hallOfFame[hallOfFame.length-1]);
}
return leastScores;
}
function solution(k, score) {
var answer = [];
answer = findLeastScore(k, score)
return answer;
}어휴 지저분해라. 코드가 대체 몇 줄이 나오는건지! 길더라도 일단 돌아만 간다면 뭐 그냥 그러려니 할텐데 심지어 TC도 끝끝내 두개에게 붙잡혀 통과하질 못한다. 😭
좀더 추상화를... 일반화를... 어떻게 할 수 있을까? 거의 다 온것 같은데 답답 그 자체. 사실 코드가 많이 중복되는 것 같은데 이걸 어떻게 좀더 간결하게 쓸 수 있을지 도무지 떠오르질 않는다. 머리에 쥐가 난 것 같아!
누군가의 정답공유대로 다시 작성해본 통과 코드
도저히 모르겠어서 누군가 질문하기 란에 공유해준 정답 코드를 보고 나름대로 재구성을 해봤다. 다른 점이 있다면 정답 공유자분은 map을 쓰셨고 나는 forEach를 썼다는 정도.
// 매일 명예의 전당 최하점을 발표 -> 이 최하점 배열을 구해달라고 한다
// 답을 구하려면 일단 명예의 전당 점수부터 구해야 한다
// 제한사항에 주의 - k가 score의 길이보다 크거나 같을 수 있다. 이러면 pop 없이 그냥 push할 수 있을 것
// 정답코드대로 map을 써볼까? 일단 forEach로 돌아보자!
function findLeastScore (k, score) {
const hallOfFame = [];
const leastScores = [];
score.forEach((el) => {
// 일단 k까지는 그냥 넣어줘야 하니까 forEach 돌면서 내림차순 정렬하고 맨 끝 요소를 최하점 배열에 push하자
if (leastScores.length < k) {
hallOfFame.push(el);
hallOfFame.sort((a,b) => b-a);
leastScores.push(hallOfFame.at(-1));
}
else {
hallOfFame.push(el);
hallOfFame.sort((a,b) => b-a);
hallOfFame.pop();
leastScores.push(hallOfFame.at(-1));
}
});
console.log('hallOfFame: ', hallOfFame)
console.log('leastScores: ', leastScores)
return leastScores;
}
function solution(k, score) {
var answer = [];
answer = findLeastScore(k, score);
return answer;
}이렇게 했더니 k > score.length 인 TC 9번, 11번의 반례도 무사히 통과되었다!
- 그러나 여기서 의문 - k > score.length 인 경우여도 이 코드에는 문제가 없는걸까? 🤔
만약k = 8, score = [30, 50, 20, 100, 25, 90, 35]라면 어떻게 될까? score 길이가 더 짧은데 반복문이 돌아가나?
일단 구하고자 하는 배열은[30, 30, 20, 20, 20, 20, 20, 20]이 될 것이다.
-> 이 경우는 score 배열을 내림차순 정렬한 맨 끝 값이 항상 최하점이 될 것. pop은 안해도 되고 push만 하면 될 것.
-> score의 forEach 문을 돌고있긴 하지만, if문의 조건절이 최하점 배열의 길이 < k라면 일단 명전 최하점을 계속 최하점배열에 push해줘 이므로 score 길이에 영향받지 않는다.
-> 얘는 최하점배열의 길이가 k가 될때까지(= 일단 k개만큼 다 집어넣을때까지) if문 속을 계속 실행해줄 것.
-> 이러다가 if문의 조건절을 만족하지 않는 순간 빠져나가서 다른 구문을 돌 것.
드디어 답을 찾아냈다 - 마시는 건 쉽지만 구하기는 어려운 콜라 문제
도대체 몇 일 걸린거지? 한 나흘 닷새 정도 걸린 것 같다. 마시긴 쉽지만 구하긴 어렵구나. 망할 놈의 콜라
// 줘야하는 병수 a, 받는 콜라수 b, 가진 병수 n
function countCoke(a, b, n) {
let earnedCoke = 0;
let surplustBottle = 0;
let answer = 0;
while (n > 0) {
// 빈병 수 < 나누는 수인데 잉여빈병을 더해 나눌 수 있다면, 잉여빈병에서 그만큼 빼와서 빈병 수에 더해준다
if(n < a && n + surplustBottle >= a) {
surplustBottle -= (a - n);
n += (a - n);
}
earnedCoke = Math.floor(n / a) * b;
answer += earnedCoke;
surplustBottle += n % a;
n = earnedCoke;
if (n + surplustBottle < a) {
break;
}
}
return answer;
}
function solution(a, b, n) {
var answer = 0;
answer = countCoke(a,b,n);
return answer;
}되는 코드는 항상 간결하다 - 얻은 콜라도 결국 똑같이 '빈병'이 된다는걸 생각하자
세상 똑똑이들의 간결한 풀이로 접근법을 익혀보자.
- 일단 parseInt를 쓰는 깔끔함에 감탄
- n에 그냥 빈병 수까지 와르륵 다 들어간다
- if문이고 뭐고 걸 필요 없이 while문이 돌아갈 조건이 깔끔
아니 이걸 어떻게 한줄로 풀어
??????????????????????????????????????????????
나처럼 경악하는 코멘트 속에서 누군가가 설명을 남겨주셨다.
a를 주고 b를 돌려받는다 치면 한번 줄때 a-b 만큼 없어지는 셈.
처음 9병 갖고있고 3병 줘서 1병 받는다 치면 9병에서 2병씩 없어지는 것이니, n / (a-b) 를 해주면 몇 번째에 n이 0이 되는 지 알 수 있다.
아니 이 물결 두줄은 또 뭐야
??????????????? 아니 이건 또 뭐야. 동작은 하는거야?
참고 블로그1
참고 블로그2
-> double tilde라고 한다. tilde는 비트연산자로 NOT의 기능을 한다고 하는데, 각 자리의 비트를 뒤집어버리는 기능이라고.
-> 이진수에서 맨앞 비트는 부호를 나타내기도 하기 때문에, 비트연산에서 0과 일을 각각 뒤집어버리면 부호가 같이 바뀐다.
-> 아무튼 그래서 비트 뒤집기를 두번 하면 원래의 수로 돌아온다.
- 그래서 이걸 왜 쓰는데? -> Math.floor의 기능을 한다고.
단점은 가독성 - 이게 뭔 용도인지 모르는 사람들은 Math.floor 역할을 한다는 것을 다음 생에도 모를 것 같다.
