[알고리즘 문제풀이] 프로그래머스 - 조이스틱

yourjin·2022년 2월 27일

알고리즘 문제풀이

목록 보기

2/28

TIL (2022.01.30)

➕ 오늘 푼 문제

프로그래머스 - 조이스틱

➕ 아이디어

상하 이동
- A ~ N : 다음 문자로 이동 (ch - ‘A’)
- M ~ Z : 이전 문자로 이동 ( ’Z’ - ch + 1)
  - A에서 Z로 이동하는 횟수 +1을 해줘야 한다.
- min( ch - ‘A’, ’Z’ - ch + 1) 으로 계산할 수도 있다.
좌우 이동
- move : name을 만들기 위한 최소 이동 횟수
  - 초기값 = len(name) -1 (우측으로만 이동한 횟수)
- move = min(move, i + (len(name) - j) + min(i, len(name)-j))
  - 최소 이동 횟수를 구하기 위해서는 (1개 이상의) 연속된 A가 발견되는 경우를 주목해야 한다. 연속된 A가 있으면 더 이상의 이동이 불필요하기 때문에 , 방향을 트는 것이 더 유리할 수도 있기 때문이다!
  - 위 공식에서 사용되는 변수의 의미들은 다음과 같다.
    - i : name을 0번째 부터 len(name)-1번째까지 반복하는 인덱스
      - 여기서 i 는 시작점에서 A구간의 시작점까지의 거리이다.
    - j : 연속된 A 구간에서 마지막 A의 인덱스
      - 여기서 len(name)-j 는 끝점에서 A구간의 끝점까지의 거리이다.
  - move는 매번 반복을 하면서, A구간을 만날 경우 좌측으로 이동 후 돌아가는 방법과 우측으로 이동 후 돌아가는 방법 중 최소 값을 찾는다. 이들 중 가장 작은 값이 move의 값이 된다.
    - min(i, len(name)-j) : 좌측으로 이동 횟수와(i)와 우즉 이동 횟수(len(name)-j) 중 작은 값

➕ Java 코드

class Solution {
    public static int solution(String name) {
        int answer = 0;
        int move = name.length() -1;
        int n = name.length();

        for(int i=0; i <n; i++){
            // 상하 이동
            answer += Math.min((int)(name.charAt(i)-'A'), (int)('Z' - name.charAt(i) + 1));

            // 좌우 이동
            int j = i + 1;
            while(j < n && name.charAt(j) == 'A'){
                j++;
            }

            // 좌측 이동 후 돌아가는 것, 우측 이동 후 돌아가는 것 중 최소 값을 구함
            int rightBack = i, leftBack = n - j;
            int minLength = Math.min(rightBack, leftBack);

            // 최소 이동 횟수 갱신
            move = Math.min(move, rightBack + leftBack + minLength);
        }

        answer += move;
        
        return answer;
    }
}

➕ Python 코드

def solution(name):
    answer = 0
    move = len(name)-1  # 우측으로만 이동한 경우의 횟수
    n = len(name)

    for i in range(n):
        # 상하이동
        answer += min(ord(name[i]) - ord('A'), ord('Z') - ord(name[i]) + 1)
        
        # 좌우이동
        j = i+1
        # 연속되는 'A' 의 마지막 위치를 찾음
        while j < n and name[j] == 'A':
            j += 1

        # 우측 이동 후 돌아가는 것과 좌측 이동 후 돌아가는 것 중 작은 값을 선택
        left_back, right_back = i, n-j
        min_length = min(left_back, right_back)

        # 최소 좌우 이동 거리를 구함
        move = min(move, left_back + right_back + min_length)

    answer += move

    return answer