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

안녕하세요 rosepurple입니다 :)

오늘 푼 알고리즘 문제 풀이를 작성해보도록 하겠습니다!

 

문제

오늘은 아래 문제를 풀어봤습니다. (약 1시간 소요)

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

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

풀이

문제를 보면 맨 처음엔 A로만 이루어져 있으며, 인자로 주어지는 name을 만들기 위해서 조이스틱을 몇 번 움직여야 하는지 알아내는 문제입니다.

처음에는 A에서 시작해서 name을 만들기 위해서 코드를 작성했는데 생각만큼 잘 작동하지 않더라고요..

그래서 거꾸로 생각해서 name에서 A를 만드는 방식으로 접근했습니다.

 

int answer = 0;
int len = name.length();
int directionCount = len - 1;

answer은 조이스틱을 움직인 횟수이고 len은 인자로 주어진 name의 길이로 초기화했습니다.

directionCount는 이동 방향의 최댓값을 넣어놨습니다. 알파벳을 바꾸는 위아래의 움직임 말고 좌우의 움직임만 고려해서 관리하기 위해 선언한 프로퍼티입니다.

간단하게 생각했을 때 이동의 최댓값은 초깃값인 A가 얼마나 연속해서 있든지 한쪽으로만 쭉 이동했을 때의 값입니다.

그래서 초깃값으로는 오른쪽으로 쭉 이동했을 때의 값인 name 길이에서 -1한 값을 넣어주었습니다.

 

아래는 for문을 순회하는 코드입니다.

if (name.charAt(i) != 'A') answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);

만약 현재 문자가  초깃값인 'A'가 아니라면 상하로 움직임 중에 가장 적게 움직이는 값을 선택해야 합니다.

그래서 A부터 현재 문자까지와 Z부터 현재 문자까지 중에 어떤 값이 작은지 비교해서 answer에 더해주는 부분입니다.

마지막의 +1은 A, Z, X .. 의 역순으로 세기 때문에 한번 더 더해주었습니다.

 

int nextIndex = i + 1;

현재 문자의 다음 문자가 'A'인지 확인하기 위해 다음 인덱스를 저장하는 프로퍼티를 선언해줍니다.

while (nextIndex < len && name.charAt(nextIndex) == 'A') nextIndex++;

그리고 만약 다음 문자가 'A'라면 어디까지 'A'인지 nextIndex를 증가시키면서 찾아줍니다.

 

directionCount = Math.min(directionCount, i + i + len - nextIndex);

그리고 이동 방향의 최솟값을 구하는 코드입니다.

오른쪽으로만 쭉 이동했을 때의 값이 저장되어있던 directionCount와 현재 문자까지만 바꾸고 반대 방향으로 조이스틱을 움직였을 경우의 값을 비교해줍니다.

i는 현재 문자까지의 인덱스이고, 다시 첫 번째로 되돌아가야 하기 때문에 2번 더해줍니다.

그리고 nextIndex에는 마지막 A의 인덱스가 저장되어있을 것이므로 len - nextIndex라고 하면 끝에서부터 마지막 A까지의 길이입니다.

 

전체 코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();
        int directionCount = len - 1;

        for (int i = 0; i < name.length(); i++) {
            int nextIndex = i + 1;
            if (name.charAt(i) != 'A') answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);

            while (nextIndex < len && name.charAt(nextIndex) == 'A') nextIndex++;
            directionCount = Math.min(directionCount, i + i + len - nextIndex);
        }

        answer += directionCount;
        return answer;
    }
}

 

마무리

생각의 전환이 필요하다고 다시 한번 느꼈던 문제였습니다.

쉽게 풀었지만 이렇게 풀기 전에는 끝도 없이 어렵고 장황하게 풀었던 문제예요..

알고리즘 문제를 쉽게 생각해보는 노력이 필요할 것 같습니다!

 

이번 포스팅도 읽어주셔서 감사합니다. :)