[프로그래머스] 탐욕법(Greedy) _ 조이스틱

2021_09_05 알고리즘 스터디 문제 풀이

문제 URL 

코딩테스트 연습 - 조이스틱

문제

 

수도코드

알파벳 상수 선언 'ABCDEFGHIJKLMNOPQRXTUVWXYZ'

count = 0
temp -> name.length 만큼의 길이를 가진 'A'로 이루어진 문자열
let i = 0;

while문으로 temp가 name과 같아질때까지 반복
    name[i] temp[i]와 같지 않다면, 조이스틱을 써야 함
        alphabet.indexOf(name[i]), 인덱스를 찾고, 그 인덱스가 alphabet.length / 2 이상이라면,
            조이스틱을 아래로 조작, 카운팅은 alphabet.length - alphabet.indexOf(name[i]);
        그렇지 않다면, 조이스틱을 위로 조작
            카운팅은 alphabet.indexOf(name[i]);
    temp[i]가 name[i]와 같아지도록 처리
    
    name[i]와 temp[i]가 같아졌다면, 이제 커서를 옮겨야 함
        name[i + 1]이 'A'가 아니고, alphabet에 속한다면
            i++;
            count증가
        name[i + 1]이; 'A'이고, alphabet에 속한다면, 
            i--;
            count증가
            만약 i가 0보다 작다면, i =  name.length + i;

count를 리턴한다

 

문제 풀이

function solution(name) {
    let temp = name.split("").map(() => 'A').join("");
    
    let count = 0;
    const alphabet = 'ABCDEFGHIJKLMNOPQRXTUVWXYZ';
    
    let i = 0;
    while (temp !== name) {
        if (name[i] !== temp[i]) {
            const index = alphabet.indexOf(name[i]);
            if (index >= alphabet.length / 2) {
                count += alphabet.length - alphabet.indexOf(name[i]);
            } else {
                count += alphabet.indexOf(name[i]);
            }
            temp = temp.slice(0, i) + name[i] + temp.slice(i + 1);
        }

        if (name[i + 1] !== 'A' && alphabet.includes(name[i + 1])) {
            i++;
            count++
        } else if (name[i + 1] === 'A' && alphabet.includes(name[i + 1])) {
            i--;
            if (i < 0) {
                i = name.length + i;
            }
            count++
        }
    }
    return count
}

시간 복잡도 O(n^2) 코드를 구현했고, 테스트를 통과했다.

하지만 처참히 채점에서 무너지고 말았다. 런타임 에러가 뜨는 상태라 O(n^2)으로 구현된 코드에 최적화를 진행해야 해결가능한 문제 같다