문제풀이(2022-09-01 THU 💻) & 스터디 (2022-09-04 SUN 📚)
💬 사담
진짜 오랜만에 쓰는 벨로그! 🙋♀️
백준 스터디 끝나면서부터 + 코딩테스트 준비 보다는 사이드 프로젝트 개발에 집중하면서부터
벨로그를 자연스럽게 쉬게 되었다
좋은 기회로 개발자 분들이랑 사이드 프로젝트도 하고,
멋사 해커톤에서 대상도 타고,
미뤄왔던 네트워크 공부도 기술면접 준비도 조금씩 시작하고,
상반기 동안 빡세게 성장했지만!
코테 실력은... 제자리 그 잡채.. 😥
스터디 동기들이랑도 정체되어 있는 것 같은 이 느낌을 어떻게 벗어날지에 대해
잠깐 얘기했었는데 아무래도 회고만이 살길이다 기록하자! 🔥
+) 요즘 프론트엔드 코테는 JavaScript로 언어를 제한하는 경우 많아지는 것 같아서,
그리고 Vanilla JS와 더 친해지기 위해!
알고리즘도 C++ 말고 JS로 풀기 시작했다.. 아직 많이 부족하지만 빠이띵 👊
🚨 첫 번째 시도 (정확성 테케 ⭕ 효율성 테케 ❌)
const solution = (n, works) => {
// 남을 작업량이 없는 경우 (works 배열 값들의 합이 n 보다 작거나 같을 경우) 바로 0을 return
if (works.reduce((acc, cur) => acc + cur, 0) <= n) return 0;
// 남을 작업량이 있는 경우
// n번 동안 i) 내림차순으로 정렬 ii) 남은 작업량이 가장 큰 작업의 양을 -1 해줌
while (n > 0) {
works.sort((a, b) => b - a);
works[0]--;
n--;
}
return works.reduce((acc, cur) => acc + cur * cur, 0);
}누가봐도 효율성 테케를 통과하지 못할 것 같은 코드였지만
그래도 혹시나하고 제출해봤는데 역시나였던 풀이 👀
cf) 문제 제한 사항
- works는 길이 1 이상, 20,000 이하인 배열입니다.
- works의 원소는 50000 이하인 자연수입니다.
- n은 1,000,000 이하인 자연수입니다.
JS의 sort의 시간복잡도는 nlogn이므로
1,000,000 * 20,000 * log(20,000) ≒ 280,000,000,000 이니까 불가능..
✅ 최종 코드
const solution = (n, works) => {
// 남을 작업량이 없는 경우 (works 배열 값들의 합이 n 보다 작거나 같을 경우) 바로 0을 return
if (works.reduce((acc, cur) => acc + cur, 0) <= n) return 0;
// 남을 작업량이 있는 경우
// 내림차순 정렬 처음에 한 번만 시행
works.sort((a, b) => b - a);
while (n > 0) {
// 배열의 첫 번째 값 보다 크거나 같은 값들을 -1 해주는 작업을 n번 시행
let maxWork = works[0];
for (let i=0; i<works.length; i++) {
if (works[i] >= maxWork) {
works[i]--;
n--;
if (n === 0) break;
}
}
}
return works.reduce((acc, cur) => acc + cur * cur, 0);
}그리디 너.. 진짜.. 나한테 좀 잘해줘라... 왜 이렇게 풀이가 안 보이니 😂
배열 sorting을 처음 한 번만 해주고, 첫 번째 값이 항상 max 값일 수 있도록!
즉, sorting을 매번 하지 않고도 배열이 계속 내림차순을 유지할 수 있도록!
해주는 게 핵심인 풀이었다
n * works 배열의 길이로 앞선 풀이보다 복잡도가 훨씬 줄어든다
참고로 사실상 reduce문 보다 for문을 사용하는 것이 성능 측면에서는 더 좋다 나는 개인적으로 reduce문으로 값 축적하는 형식 연습해보고 싶어서 이 문제에서는 reduce문을 썼다
