99클럽 코테 스터디 16일차 TIL + Greedy(조이스틱)

오늘의 과제

프로그래머스 Lv.2로 분류된 조이스틱입니다.

 

이번 문제 유형은 순차적으로 최선의 선택을 이어나가는 탐욕법(Greedy)입니다.

문제

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

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

글자의 길이와 똑같은 길이로 A로 초기화 되어 있는 문자열이 있다고 가정하고

주어진 글자로 바꾸는 최소한의 조작 수를 구하면 됩니다.

 

문자를 바꿀 때에는 위, 아래로 조작할 수 있고 만약 A,Z와 같이 알파벳의 끝이라면 A => Z, Z => A와 같이

끝으로 이동합니다.

 

다음 문자를 바꿀 때에는 해당 문자를 선택해야 하기 때문에 왼쪽, 오른쪽으로 이동해야 하며

위, 아래와 동일하게 처음 혹은 끝으로 이동합니다.

 

이 문제에서 어려운 점은 문자를 A => 목표 문자로 바꾸는 것이 아니라 문제의 예시인 "JAZ"처럼

정방향으로 가는것이 빠를지, 뒤로 돌아 가는것이 빠를지 판단하는 로직입니다.

 

먼저 문자를 바꾸는 것은 아스키 코드를 활용합니다.

 

위로 가는 경우 => 해당 문자 - 'A'

아래로 가는 경우 => 'Z' - 해당 문자

 

다음으로 이 문제의 관건인 좌,우 중 어디로 이동하는지 판별합니다.

 

먼저 기본 이동값은 0번 문자열에서 마지막 문자열까지 정방향으로 이동하는 경우이기 때문에

문자열 길이 - 1로 구할 수 있습니다.

 

다만 문제의 예시와 같이 A의 경우에는 굳이 가서 바꾸지 않아도 되기 때문에

바로 이동할 수 있습니다.

 

그럼 정방향 VS 역방향 중 최소 값으로 세팅해주면 됩니다.

 

뒤로 돌아가는 계산식은 아래와 같이 구합니다.

 

현재까지 온 위치까지 왔다가 돌아가는 거리 => i * 2 + length + cursor

 

또한 AABBBBBA와 같이 처음부터 역방향으로 가는 경우도 고려합니다.

 

처음부터 역방향으로 갔다가 돌아서 움직이는 경우 => (length - cursor) * 2 + i

 

 

코드입니다.

class Solution {
    public int solution(String name) {
        // 카운트
        int answer = 0;
        // 조이스틱이 가르키는 위치
        int cursor = 0;
        
        int length = name.length();
        // 0번 인덱스 기준으로 오른쪽 끝까지 움직였을 때 이동 횟수
        int move = length -1;

        for(int i = 0; i < length; i++){
            char c = name.charAt(i);
            // 위, 아래 중 최소로 움직일 수 있는 값으로 세팅
            answer += Math.min(c - 'A', 'Z' - c + 1);

            cursor = i + 1;
            // A의 경우 바꾸지 않아도 된다
            while(cursor < length && name.charAt(cursor) == 'A') cursor++;
            // 0 => 끝까지 순서대로 가는것, 현재(i)의 위치까지 왔다가
            // 다시 뒤로 돌아 가는 것
            move = Math.min(move, i * 2 + length - cursor);
            // 첫 문자열부터 뒤로 돌아가는 경우
            move = Math.min(move, (length - cursor) * 2 + i);
        }
        return answer + move;
    }
}

 

 

배운 점

코드 블럭에 언어 종류가 있는지 모르고 계속 bash로 올리고 있었습니다...ㅎ;

 

첫 문자열부터 돌아가는 경우를 끝까지 찾아내지 못했습니다.

 

결국 시간을 너무 할애해 다른 사람의 사례를 보고 이해하고 넘어갑니다.

 

아직은 수학적 사고가 부족한지 그저 외우는 정형화된 스킬은 조금씩 찾아가지만

특정 점화식을 찾는다거나, 테스트 케이스를 찾아내는 생각은 너무 느린 것 같습니다.

 

같은 LV.2라도 약한 부분을 찾았으니 집중적으로 해당 능력을 키워야겠습니다.

 

 

오늘의 한줄평

혼자 시간을 쏟은 깊은 고뇌도 좋지만 때론 효율을 위해 타인에게 도움을 구하는 것 또한 능력이다.