🏷️coa-lee-dev/🧿Coding test/🥘Programmers/탐욕법 Greedy/
조이스틱 joystick
Search

조이스틱 joystick

💡
Level 2 210923 https://programmers.co.kr/learn/courses/30/lessons/42860

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
  • 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

  • name은 알파벳 대문자로만 이루어져 있습니다.
  • name의 길이는 1 이상 20 이하입니다.

입출력 예

name
return
"JEROEN"
56
"JAN"
23

My solution

A로만 구성된 문자열을 이름으로 변경하는 동안 조이스틱을 몇번 움직였는지 그리디로 풀어보자

(맨 처음엔 A로만 이루어져 있습니다.ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA)
 
name과 조이스틱으로 만들어낸 tmp 문자열이 동일하다면 횟수 반환
 
이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
if (location === 64) location = 96;
첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서 
if (location === -1) location = arr.length - 1;
 
이때 최솟값으로 만들기 위해서는 Z를 사용하기 위해서 A~Z까지 조이스틱을 25번 올리는 것이 아니라 한번 내려 Z를 만드는 등의 최적화 과정이 필요하다.
모든 걸 다 해보고 최솟값을 찾는 것이 아니라 그리디 알고리즘답게 선택의 상황에서 그 순간 최적이라 생각되는 것을 선택해나가는 방식을 구현해야 한다.
그리디가 잘 작동하는 조건은 아래와 같고 이 문제도 이 조건이 성립한다.
  • 탐욕스런 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조 조건 : 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해다.
 
A에서 어떤 알파벳까지는 아래가 최적이고 어떤 알파벳까는 위가 최적일까?
← (N) OPQRST UVWXYZ A BCDEFG HIJKLM N(상,하 어디든 13번째) →
A위치는 아스키코드로 65인데 N은 78이다. 위의 계산에 따르면 name으로 주어진 알파벳의 아스키코드가 79이상이면 조이스틱을 아래로 움직이는 것이 최적일 것이다.
아스키코드가 79이상인 알파벳을 만들기 위해 조이스틱을 움직이는 횟수는 90(Z)+1부터 횟수를 누적해가며 -1씩해주다가 해당하는 알파벳의 아스키코드를 만나면 그 누적된 횟수가 최적해일 것이다.
 
커서를 왼쪽과 오른쪽 중 어느쪽으로 이동시키는 것이 최적인가에 대한 고민은 좀더 생각해보아야 한다.
"A가 아닌 다음 알파벳"을 왼쪽으로 움직여야 빨리 만날지 오른쪽으로 움직여야 빨리 만날지에 대한 고민이라고 생각했다.
name 문자열에서 조이스틱의 현 위치의 다음 인덱스부터 A가 아닌 알파벳을 찾고 name을 뒤집어서 찾아본다.
notion image
// let re = /[^A]/;
// console.log(names.join(""));
    // console.log(names.slice(1, names.length).join("").search(re)); // splice로 원본 변경x, slice 사용
    // console.log(names.reverse().join("").search(re)); // reverse 원본 배열 수정하게 됨
뒤에서부터 찾아서 가장 가까운 A가 아닌 알파벳을 찾느라 reverse()를 쓰면 원본 배열이 수정된다.
그래서 for문으로 하나씩 체크한다음 둘중 어떤 게 최솟값인지 구하는 방식이 간단하고 제대로 작동해서 이렇게 바꿨다.
 
[ 'J', 'E', 'R', 'O', 'E', 'N' ]
변경에 필요한 횟수 : 9, 4, 9, 12, 4, 13 >> 정해진 조건에 의해 나온 최솟값이므로 answer에 누적
커서 이동 횟수 : 좌로 가든 우로 가든 5 >> 이중 최솟값을 answer에 더한다.
아래의 코드로 정답을 맞췄다고 생각했다.
function solution(name) {
    let answer = 0;
    let n = name.length;
    let names = name.split("");
    let tmp = Array(name.length).fill("A");
    let right = 0;
    let left = 0;

    // 알파벳을 만들어내는 최소 횟수 구하기
    for (let i = 0; i < n; i++) {
        if (name[i].charCodeAt() - tmp[i].charCodeAt() > 13)
            answer += 91 - name[i].charCodeAt();
        else answer += name[i].charCodeAt() - tmp[i].charCodeAt();
    }

    // 왼쪽 이동으로 갈 수 있는 가장 끝에 있는 A가 아닌 알파벳까지의 이동 횟수(자신의 인덱스 전까지 : i > 0)
    for (let i = n - 1; i > 0; i--) {
        if (names[i] !== "A") left = n - i;
    }
    // 오른쪽 이동으로 갈 수 있는 가장 끝에 있는 A가 아닌 알파벳까지의 이동 횟수
    for (let i = 1; i < n; i++) {
        if (names[i] !== "A") right = i;
    }
    answer += Math.min(left, right);
    return answer;
}
notion image
 
찾아보니 마지막 테스트 케이스가 "ABAAAAAAAAABB" >> 7 리턴이라고 한다.
즉, 오른쪽으로 가다가 왼쪽으로 방향을 바꿀 수 있도록 되어 있다. 그럼 현재 위치를 기록할 cur 변수가 필요하다. 현 위치에서부터 가장 가까운 A가 아닌 알파벳을 매번 찾아야 하는 것이다.
커서 변수를 만들어서 해결해보려다가 안되서 1시간 반을 썼는데 레벨 2를 버거워하는 것이 당황스러워서 헬스장에 가서 휴식(?)을 가졌다.
 
생각해보니 그냥 for문 범위를 바꾸지말고 배열에서 이동한 현 위치를 0번 인덱스로 옮기면 같은 로직으로 돌려쓸 수 있겠다 싶었다. 그래서 커서가 (좌 or 우) 최소거리로 이동했을 때의 도착한 그 인덱스를 리턴해주는 함수를 구현했다. 이 리턴받은 start라는 값은 다시 minMove(start)에 전달되고 tmp와 names 배열을 잘라서 그 인덱스가 0번 인덱스가 되도록 만들어준다.
그렇게 되면 항상 0번 인덱스부터 최소 거리를 찾아내는 두 개의 for문이 i값의 변경 없이 잘 작동한다.
 
while문 내에서는 minMove(start)함수가 최소거리만큼만 좌, 우 움직임을 계산하여 이것은 answer에 누적된다.그리고 tmp라는 배열의 원소가 변경되다가 names와 같아지면 while문은 종료된다.
 
💡
조이스틱 문제 푸는 시간이 생각보다 더 걸렸는데 다른 사람 풀이 찾아보니 문제 개편으로 테스트케이스 11번 실패하는 풀이가 많은 것 같아 이 문제를 풀었다는 것이 뿌듯했다. 질문하기에 마지막 테스트 케이스가 "ABAAAAAAAAABB" >> 7 리턴이라고 꿀팁을 남겨주신 분 덕분인 것 같다.
 

소스 코드

function solution(name) {
    let answer = 0;
    let n = name.length;
    let names = name.split("");
    let tmp = Array(name.length).fill("A");

    // 알파벳을 만들어내는 최소 횟수
    for (let i = 0; i < n; i++) {
        if (name[i].charCodeAt() - tmp[i].charCodeAt() > 13)
            answer += 91 - name[i].charCodeAt();
        else answer += name[i].charCodeAt() - tmp[i].charCodeAt();
    }

    // tmp와 names가 같아질 때까지 인덱스를 최소 거리로 이동하면서 tmp의 원소를 바꿈
    function minMove(start) {
        (right = 0), (left = 0);
        names = names.slice(start, names.length).concat(names.slice(0, start));
        tmp = tmp.slice(start, tmp.length).concat(tmp.slice(0, start));

        // 오른쪽 이동으로 갈 수 있는 가장 가까운 "A가 아닌 알파벳"까지의 이동 횟수
        for (let i = 0; i < n; i++) {
            // console.log("r", i, tmp[i], names[i]);
            if (tmp[i] === "A" && names[i] !== "A") {
                right = i;
                break;
            }
        }
        // 왼쪽 이동으로 갈 수 있는 가장 가까운 "A가 아닌 알파벳"까지의 이동 횟수
        for (let i = n - 1; i > 0; i--) {
            // console.log("l", i, tmp[i], names[i]);
            if (tmp[i] === "A" && names[i] !== "A") {
                left = n - i;
                break;
            }
        }
        if (right <= left) {
            tmp[right] = names[right];
            // console.log("r", "tmp", tmp);
            answer += right;
            return right;
        } else {
            tmp[n - left] = names[n - left];
            // console.log("l", "tmp", tmp);
            answer += left;
            return n - left;
        }
    }

    let start = 0;
    while (JSON.stringify(tmp) !== JSON.stringify(names)) {
        start = minMove(start);
    }

    return answer;
}

test("solution", () => {
    expect(solution("AZ")).toBe(2);
    expect(solution("ABAAAAAAAAABB")).toBe(7);
    expect(solution("JEROEN")).toBe(56);
    expect(solution("JAN")).toBe(23);
});
 
Copyright 2021 Bonhaeng Lee