[프로그래머스 코딩테스트 연습문제] 덧칠하기 | 알고리즘 설명 & 문제 풀이 with 자바스크립트(Javascript)

1. 문제 설명

2. 제한사항

3. 입출력 예

4. 입출력 예 설명

5. 첫번째 문제 풀이(2023-12-30) faild

이 문제도 코딩테스트의 단골 유형중 기본인데, 제가 처음 풀어보는 입장이다보니 익숙한 for문 위주로 풀어서인지... 테스트케이스 50개 중 23개를 통과하는 기염(?)을 토했습니다. 당연히도 n^3의 성능이다보니 범위가 100,000 임에도 불구하고 그런 괴랄한 모습을 보이지 않나...

아무튼 알고리즘을 설명드리면 n만큼의 연속된 수가 들어있는 배열 arr을 생성한 후 section 만큼 for문을 돌리면서 중첩 for문에는 페인트칠 범위m만큼 돌리면서 section에 해당 arr의 현재 section의 값이 들어있는 경우 count를 증가시키며 for문을 돌린 후

누적된 count(중첩 for문이 끝나고 페인트를 칠한 총 횟수)를 countArray에 push해줍니다. 그렇게 상위 for문까지 끝나고 나면 section당 칠해야 하는 구역을 칠한 값(count)을 보관 중인 배열이 생성되는데,

countArray를 내림차순을 이용하여 큰 값이 앞으로 오게 한 후 다시 for문을 countArray의 길이만큼 돌려 최대한 많이 페인트를 칠한 순으로 누적시킨 값과 m을 비교하여 m보다 같거나 큰 경우 현재 i + 1(만약 최소 세 번 칠해서 만족할 경우 i는 2일 것이고, 1 + 1 = 3 이므로 최소값 3를 return 합니다.)를 반환합니다.

솔직히 저도 코딩 하면서 구상은 했는데... 음... 정석은 아닌 것 같고 설명하는 지금까지도 헷갈리네요. 😅

function solution(n, m, section) {
   
    let arr = new Array(n).fill(0).map((val,index) => index + 1);
   
    let countArray = [];
   
    for (let i = 0; i < section.length; i++) {
       
        let count = 0;    
        let paint = section[i]
        let paintIndex = arr.indexOf(paint);
        for(let j = 0 ; j < m ; j++){
            if (section.includes(arr[j + paintIndex])) {
                count++;
            }
        }
        countArray.push(count);
    }
    let countRole = 0;
    countArray.sort((a,b) => b - a);

    let result = [];
    for(let i = 0 ; i < countArray.length ; i++){
        countRole += countArray[i];
        if(countRole >= section.length){
            return i+1           
        }
    }  
}