[프로그래머스] 조이스틱 문제풀이 (Java)

ajufresh·2020년 5월 23일
0

프로그래머스

목록 보기
1/5

🔗 링크

https://programmers.co.kr/learn/courses/30/lessons/42860

🕹️ 문제

이름에 대해 조이스틱 조작 횟수의 최솟값 구하기

(모든 글자는 A로 시작. 세 글자면 AAA, 네글자면 AAAA)

- 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z)- 커서를 오른쪽으로 이동
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)

👀 예제로 문제 파악하기

입력 : JAZ

초기 상태인 'AAA'에서 'JAZ'를 만들기 위한 첫 번째 단계인

0번째 AJ로 만들기 위해 가능한 경우의 수는 아래와 같다.

AJ
	1.: 9(최솟값)
	2.: 17

최소 횟수로 옮길 수 있는 방법은 1번이기 때문에 1번을 선택하고 answer에 9를 더해준다.

(현재 위치 : 0, answer : 9)

현재 상황은 아래와 같다. (JAA)
0번째 J : 현재 위치, 알바펫 배치 끝
1번째 A : X
2번째 A : 알파벳 배치 끝

현재 남은 작업은 2번째 값인 'A'를 'Z'로 바꾸는 작업이다.

그러기 위해서는 위치를 옮겨야하는데,

현재 위치인 0번째에서 2번째로 위치를 옮길 수 있는 경우의 수는 아래와 같다.

0번째 → 2번째
	1.: 1(최솟값)
	2.: 2

최소 횟수로 옮길 수 있는 방법은 1번 방법이기 때문에 1번을 선택하고 answer에 1을 더해준 후에 위치를 옮겨준다.

(현재 위치 : 2, answer : 10)

이제 'A'를 'Z'로 바꾸는 작업을 해야한다.

AZ
	1.: 252.: 1(최솟값)

2번 방법을 선택하는 것이 최솟값이기 때문에 answer에 1을 더해준다.

(현재 위치 : 2, answer : 11)

모든 작업이 끝났다.

answer인 11을 return한다.

😮 알고리즘 풀이 순서

  1. 조이스틱을 최소한으로 움직일 수 있는 값의 배열을 구한다. (=min[])

    • JAZ 같은 경우에는 [9, 0, 1]이 나온다.
    • 이 배열은 최솟값의 배열 역할뿐만 아니라 값이 있는 위치를 찾을 수 있는 역할도 한다.
      • 알파벳 배치가 끝난 것은 0으로 변환
      • 0이 아닌 값위치를 찾을 때 이 배열을 사용
  2. min[startAt]의 해당하는 위치의 최솟값을 더해준다.

  • startAt의 초기 값은 0으로 초기화 한다.
  1. min[startAt]을 0으로 바꿔준다.

  2. min[]의 모든 값0이면 반복을 종료한다.

  3. 다음 값이 있는 위치의 최솟값을 구한다.

  • 오른쪽(▶) : min[startAt]의 값이 0이 아닐 때 까지 +1한다. (끝까지 오면 0번째로 되돌아간다.)
  • 왼쪽(◀) : min[startAt]의 값이 0이 아닐 때 까지 -1한다. (0번째로 오면 마지막으로 되돌아간다.)
  1. 2번으로 되돌아간다.

👨‍💻 코드

public class Solution {

  public int solution(String name) {
    int answer = 0;

    // 1. 조이스틱을 최소한으로 움직일 수 있는 값을 구한다.
    int[] min = new int[name.length()];

    for (int i = 0; i < name.length(); i++) {
      min[i] = Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
    }

    // 2. 현재 위치부터 시작해서 min의 모든 요소가 0이 될 때 까지 반복
    int startAt = 0;

    while (true) {
      answer += min[startAt];
      min[startAt] = 0;

      if (everythingIsZero(min)) {
        break;
      }

      int[] goToAt = goToAt(min, startAt);

      startAt = goToAt[0];
      answer += goToAt[1];
    }

    return answer;
  }

  // 왼쪽, 오른쪽 중 더 가까운 곳을 찾고 가까운 곳의 위치와 더할 값을 찾음
  private int[] goToAt(int[] min, int startAt) {

    int[] minThings = new int[2]; // 0번째->위치, 1번째->더할 값

    // 오른쪽으로 가는 최소 횟수 구하기
    int rightAt = startAt + 1 > min.length - 1 ? 0 : startAt + 1;
    int right = 1;

    while (min[rightAt] == 0) {
      rightAt = rightAt + 1 > min.length - 1 ? 0 : rightAt + 1;
      right++;
    }

    // 왼쪽으로 가는 최소 횟수 구하기
    int leftAt = startAt - 1 < 0 ? min.length - 1 : startAt - 1;
    int left = 1;

    while (min[leftAt] == 0) {
      leftAt = leftAt - 1 < 0 ? min.length - 1 : leftAt - 1;
      left++;
    }

    if (right > left) {
      minThings[0] = leftAt;
      minThings[1] = left;
    } else {
      minThings[0] = rightAt;
      minThings[1] = right;
    }

    return minThings;

  }

  // 모든 요소가 0인지 검사하는 메소드
  private boolean everythingIsZero(int[] min) {

    for (int i = 0; i < min.length; i++) {
      if (min[i] != 0) {
        return false;
      }
    }
    return true;
  }


  @Test
  public void 정답() {
    Assert.assertEquals(11, solution("JAZ"));
    Assert.assertEquals(56, solution("JEROEN"));
    Assert.assertEquals(23, solution("JAN"));
  }
}

profile
공블로그

0개의 댓글