[Javascript/PGS] Lv.2 : 조이스틱 (Greedy) 🎮🔥

 

https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=javascript#

프로그래머스

---

프로그래머스 레벨 2

근데 꽤 어려웠다 ㅠㅠ 꼭 탐욕법으로 풀지 않아도 되는 것 같았다

이정도 난이도면 레벨3 아니냐고,,

1. 첫번째 풀이 : 74.1점 😵

반례 : "BBBBAAAAAAB"

기댓값 10, 결과값 12

 

function solution(Name) {
    let name = Name.split('');
    let answer = 0;
    console.log('A'.charCodeAt(),'Z'.charCodeAt()); // 65~90
    // abcdefghijklm-n(13)-opqrstuvwxyz
    let n = 0;
    let i = 0;
    let cnt = 0; // A의 갯수
    for(let k=0; k<name.length; ++k){
        if(name[k]=='A') cnt++;
    }
    if(cnt===name.length) return 0;
    while(1){
        console.log(i, name[i] ,answer)
        n = String(name[i]).charCodeAt();
        if(n!==65) cnt++;
        if((n-65)>13){
            answer += (90-n+1);
        }
        else answer += (n-65);
        name.splice(i,1,'A')
        if(cnt == name.length) break;
        
        // 앞쪽으로 가야하는 수, 뒤쪽으로 가야하는 수 비교 (A의 개수)
        let front=1; let back=1;
        let j = i+1;
        while(1){
            if(j>name.length-1) j = 0;
            if(name[j]=='A') front++;
            else break;
            j++;
        }
        let k = i-1;
        while(1){
            if(k<0) k = name.length-1;
            if(name[k]=='A') back++;
            else break;
            k--;
        }
        console.log("front", front, "back" ,back)
        if(front > back) {
            i = k;
            answer += back;
        }
        else {
            i = j;
            answer += front;
        }
    }
    
    return answer;
}

 

---

2. 두번째 풀이 : 정답 ✅

알파벳 변경 횟수 카운트는 쉬웠는데, 이동횟수 min 갱신이 어려웠다!!!

 

<주요 코드>
        let rightFirst = j * 2 + (name.length - nextIdx);
        let leftFirst = (name.length - nextIdx) * 2 + j;
        minMove = Math.min(minMove, rightFirst, leftFirst);

 

위 코드를 쉽게 풀이해보면, 아래와 같다.

 

예시 ) "BBBBAAAAAAB"

 

1️⃣ 인덱스 0부터 오른쪽으로 갔다가 되돌아와서 뒤로 가는 경우 (rightFirst)

-> 0을 기준으로, right - left 왕복 후 뒤로 넘어가서 끝부분 9로 감

• j = 3 (여기까지 오른쪽으로 가야 함)

• nextIdx = 9 (다음 B가 있는 위치)

• 계산: 3 * 2 + (10 - 9) = 6 + 1 = 7

 

2️⃣ 인덱스 0에서 왼쪽(뒤)으로 갔다가 다시 돌아와서 오른쪽으로 가는 경우 (leftFirst)

-> 0을 기준으로, 9번째 인덱스로 갔다가 다시 0으로 돌아와서(왕복) 오른쪽으로 감

• nextIdx = 9 (다음 B가 있는 위치)

• name.length - nextIdx = 10 - 9 = 1

• 계산: (1 * 2) + 3 = 2 + 3 = 5

 

즉, 곱하기 2를 해주는건 왕복운동이기 때문!

 

나의 풀이

function solution(name) {
    let answer = 0;
    console.log('A'.charCodeAt(),'Z'.charCodeAt()); // 65~90
    // abcdefghijklm-n(13)-opqrstuvwxyz
    let n = 0;
    let i = 0;
    let cnt = 0; // A가 아닌 값의 개수
    // 1. 알파벳 총 변경 횟수
    for(let k=0; k<name.length; ++k){
        if(name[k]!=='A'){
            answer += Math.min(name[k].charCodeAt()-65, 
                        90-name[k].charCodeAt()+1);
            cnt++;
            min = k;
        }
    }
    if(cnt===0) return 0;
    
    // 2. 최수 이동 횟수
    let minMove = name.length - 1;
    for (let j = 0; j < name.length; j++) {
        let nextIdx = j + 1;
        while (nextIdx < name.length && name[nextIdx] === 'A') {
            nextIdx++;
        }
        let rightFirst = j * 2 + (name.length - nextIdx);
        let leftFirst = (name.length - nextIdx) * 2 + j;
        minMove = Math.min(minMove, rightFirst, leftFirst);
    }
    answer += minMove;
    return answer;
}