03.24.2022 TIL

TIL

Done it

• 베스트 앨범문제

totalMap을 통해 공통된 장르의 값을 더해 저장해서 Sort해서 먼저 나와야 하는 장르 순서를 구했습니다.

for (let i = 0; i < n; i++) {
    if (totalGenMap.has(genres[i])) totalGenMap.set(genres[i], totalGenMap.get(genres[i]) + plays[i]);
    else totalGenMap.set(genres[i], plays[i]);

    //genMap.set(i, [genres[i], plays[i]]); 해결방안
}

let totalGenMapSort = [...totalGenMap].sort((a, b) => b[1] - a[1]);
// let genMapSort = [...genMap].sort((a, b) => b[1][1] - a[1][1]); 해결방안

totalMap을 돌면서 해당 장르와 같은 것을 찾아 배열에 넣고 이 배열을 이용하여 답을 구했습니다. 이로 인해 O(n^3)의 시간 복잡도가 나왔고 런타임 에러가 발생했습니다.

for (let totalGen of totalGenMapSort) {
    let genArr = [];
    for (let i = 0; i < n; i++) {
        if (totalGen[0] == genres[i]) genArr.push([i, plays[i]]);
     }
    answer = [...answer, ...getSings(genArr)];
    }

그래서 genMap이라는 i => [genre, plays]를 저장하는 Map을 구현하였고 check변수를 통해 2개만 출력하도록 만들어서 O(n^2)의 시간 복잡도로 만들어 해결하였습니다.

for (let totalGen of totalGenMapSort) {
    let check = 0;
    for (let gen of genMapSort) {
        if (check < 2 && gen[1][0] == totalGen[0]) {
            answer.push(gen[0]);
            check++;
        }
    }
}

마지막으로 해설을 통해서 함수형 프로그래밍을 이용한 코드를 봤는데 정말 대박이었습니다. 더 연습하러 가보겠습니다. :)

• O(logn)에 대해서
  • logn인 경우 밑은 크게 상관하지 않고 O(n)에 비해 매우 작고 O(1)과 매우 유사하다고 생각이 됩니다. 즉 O(n)일 때 조건이 발생한 경우라고 생각을 하려고 합니다.(이분 분할...)

 

Feeling

알고리즘을 푸는데 정말 아직 많이 부족하다는 것을 느끼고 있습니다.

그래서 하루에 한 문제라도 풀려고 노력을 해야겠습니다. 저의 실력에 아쉬움이 많이 남았습니다.

그리고 논리력이 좀 부족한 것 같아 논리 책을 이용하여 쌓으려고 합니다. 평일은 엄청 바쁘니 주말을 주로 이용해야 겠습니다. :)

 

 

REF

https://sinseonc.tistory.com/11

https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly