[프로그래머스] JavaScript Lv2 - 조이스틱(42860)

개요

문제 이름: 조이스틱 (42860)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42860
플랫폼: 프로그래머스
알고리즘 분류: 탐욕법(Greedy)
소요 시간: 10시간

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 그리디(Greedy) 알고리즘과 최적화 문제를 결합한 형태입니다. 주어진 이름을 만들기 위해 조이스틱을 최소한으로 조작하는 방법을 찾아야 합니다. 문제를 해결하기 위해서는 두 가지 주요 부분을 고려해야 합니다.

1. 각 문자를 변경하기 위한 상하 이동 횟수
2. 문자 간 이동을 위한 좌우 이동 횟수

 

문제 접근 방식

• 각 문자에 대해 'A'에서 해당 문자로 변경하는데 필요한 최소 이동 횟수를 계산합니다.
• 좌우 이동의 최적 경로를 찾습니다. 이때 연속된 'A'를 고려하여 불필요한 이동을 줄입니다.

 

문제 요약

• 주어진 문자열의 각 문자를 'A'에서 변경하는데 필요한 최소 이동 횟수 계산
• 문자 간 이동을 위한 최적의 좌우 이동 경로 찾기
• 두 값을 합산하여 총 최소 이동 횟수 반환

 

탐욕법(그리디) 알고리즘

그리디 알고리즘은 최적화 문제를 해결하는 방법 중 하나로, '각 단계에서 가장 최선의 선택을 하는' 전략을 사용합니다.

• 지역적 최적해: 그리디 알고리즘은 각 단계에서 그 순간에 가장 좋아 보이는 선택을 합니다. 이를 '지역적 최적해'라고 합니다.
• 단순성: 문제를 작은 단위로 나누고, 각 단위에서 최적의 해를 찾는 방식이므로 구현이 비교적 간단합니다.
• 효율성: 대체로 실행 속도가 빠르며, 복잡한 계산 없이 해를 찾을 수 있습니다.
• 최적해 보장 불가: 그리디 알고리즘은 항상 전체적인 최적해를 보장하지는 않습니다. 일부 문제에서는 최적해를 찾지 못할 수 있습니다.

다만, 일부 문제에서는 그리디 알고리즘이 최적해를 보장하지 않으므로 주의가 필요합니다.

 

조이스틱 문제와 그리디 알고리즘

이 문제에서 그리디 알고리즘은 다음과 같이 적용됩니다.

• 각 문자 변경: 각 문자를 변경할 때, 위로 이동하는 것과 아래로 이동하는 것 중 더 적은 횟수를 선택합니다.
• 이동 방향 결정: 현재 위치에서 다음 변경해야 할 문자로 이동할 때, 왼쪽으로 가는 것과 오른쪽으로 가는 것 중 더 적은 이동을 요구하는 방향을 선택합니다.
• 'A' 건너뛰기: 연속된 'A'를 만났을 때, 이를 건너뛰고 다음으로 변경해야 할 문자로 이동하는 것이 더 효율적인지 판단합니다.

이러한 방식으로 각 단계에서 최선의 선택을 함으로써, 전체적으로 최소한의 조작으로 목표 문자열을 만들어 낼 수 있습니다.

 

시도

1차 시도  (성공)

function solution(name) {
    let totalMoves = 0;  // 총 이동 횟수
    let leftRightMoves = name.length - 1;  // 좌우 이동 횟수 (초기값은 한 방향으로 쭉 이동하는 경우)

    for (let i = 0; i < name.length; i++) {
        let char = name[i];
        // 각 문자에 대해 위아래 이동 횟수 계산
        let upMoves = char.charCodeAt(0) - "A".charCodeAt(0);
        let downMoves = 26 - upMoves;
        totalMoves += Math.min(upMoves, downMoves);  // 위아래 중 최소 이동 횟수 더하기

        // 현재 위치 이후의 연속된 A의 끝 위치 찾기
        let nextIndex = i + 1;
        while (nextIndex < name.length && name[nextIndex] === "A") {
            nextIndex++;
        }

        // 좌우 이동의 최소값 갱신
        // 1. 현재까지 왔다가 돌아가는 경우
        let moveBack = i * 2 + (name.length - nextIndex);
        // 2. 끝까지 갔다가 돌아오는 경우
        let moveForward = (name.length - nextIndex) * 2 + i;
        leftRightMoves = Math.min(leftRightMoves, moveBack, moveForward);
    }

    return totalMoves + leftRightMoves;  // 총 이동 횟수 반환
}

상세한 설명은 다음과 같습니다.

1. totalMoves: 각 문자를 변경하는데 필요한 상하 이동 횟수의 총합을 저장합니다.
2. leftRightMoves: 좌우 이동의 최소 횟수를 저장합니다. 초기값은 name의 길이 - 1로, 이는 한 방향으로 쭉 이동하는 경우입니다.
3. 문자열을 순회하면서 각 문자에 대해
   1. upMoves와 downMoves를 계산하여 각 문자를 만드는데 필요한 최소 이동 횟수를 구합니다.
   2. charCodeAt(0)를 사용해 문자의 ASCII 코드를 얻습니다.
   3. Math.min()을 사용해 위아래 이동 중 최소값을 totalMoves에 더합니다.
4. 연속된 'A'의 끝 위치를 찾습니다
   1. while 루프를 사용해 현재 위치 이후의 연속된 'A'의 끝 위치를 찾습니다.
5. 좌우 이동의 최소값을 갱신합니다.
   1. 현재까지 왔다가 돌아가는 경우 (moveBack)
   2. 끝까지 갔다가 돌아오는 경우 (moveForward)
   3. Math.min()을 사용해 이 두 경우와 기존 leftRightMoves 중 최소값을 선택합니다.
6. 최종적으로 totalMoves와 leftRightMoves의 합을 반환합니다.

시간 복잡도: O(n), 여기서 n은 name의 길이입니다. 문자열을 한 번 순회합니다.
공간 복잡도: O(1), 추가적인 공간을 사용하지 않고 몇 개의 변수만 사용합니다.

 

2차 시도  (성공)

function solution(name) {
    let moves = 0;  // 상하 이동 횟수
    let minSideMove = name.length - 1;  // 좌우 이동의 최소값 (초기값은 한 방향으로 쭉 이동하는 경우)
    
    for (let i = 0; i < name.length; i++) {
        // 각 문자에 대해 위아래 중 최소 이동 횟수 계산
        moves += Math.min(name[i].charCodeAt(0) - 65, 91 - name[i].charCodeAt(0));
        
        // 현재 위치 이후의 연속된 A의 끝 위치 찾기
        let endA = i + 1;
        while (endA < name.length && name[endA] === 'A') endA++;
        
        // 좌우 이동의 최소값 갱신
        // 1. 현재까지 왔다가 돌아가는 경우
        // 2. 끝까지 갔다가 돌아오는 경우
        minSideMove = Math.min(minSideMove, i * 2 + (name.length - endA), (name.length - endA) * 2 + i);
    }
    
    return moves + minSideMove;  // 총 이동 횟수 반환
}

이 코드는 1차 시도의 코드를 더욱 간결하게 만든 버전입니다. 주요 차이점과 설명은 다음과 같습니다.

1. moves: 1차 시도의 totalMoves와 동일한 역할을 합니다.
2. 문자 변경을 위한 상하 이동 계산
   1. Math.min(name[i].charCodeAt(0) - 65, 91 - name[i].charCodeAt(0))
   2. 65는 'A'의 ASCII 코드, 91은 'Z' 다음 문자의 ASCII 코드입니다.
   3. 이 방식으로 위로 이동하는 경우와 아래로 이동하는 경우 중 최소값을 직접 계산합니다.
3. 연속된 'A' 탐색
   1. endA 변수를 사용해 현재 위치 이후의 연속된 'A'의 끝 위치를 찾습니다.
4. 좌우 이동 최소값 갱신
   1. Math.min()을 사용해 세 가지 경우(기존 최소값, 현재까지 왔다가 돌아가는 경우, 끝까지 갔다가 돌아오는 경우) 중 최소값을 선택합니다.
5. 최종적으로 moves와 minSideMove의 합을 반환합니다.

이 코드 또한 마찬가지로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

 

사용된 메서드

• charCodeAt(0): 문자열의 지정된 인덱스에 있는 문자의 Unicode 값을 반환합니다. 여기서는 ASCII 코드를 얻는 데 사용됩니다.
• Math.min(): 주어진 숫자들 중 가장 작은 숫자를 반환합니다. 여기서는 여러 경우의 수 중 최소값을 선택하는 데 사용됩니다.
• while 루프: 조건이 참인 동안 코드 블록을 반복 실행합니다. 여기서는 연속된 'A'를 찾는 데 사용됩니다.