99클럽 코테 스터디 19일차 TIL

오늘의 학습 키워드

• 그리디 알고리즘 (Greedy Algorithm)
• 문자열 조작 (String Manipulation)

문제 이해

이 문제는 주어진 이름을 만들기 위해 조이스틱을 이용해 각 알파벳을 변경하고, 최소한의 조이스틱 이동으로 목표 이름을 완성하는 문제입니다. 이름의 각 알파벳을 'A'에서 목표 알파벳으로 바꾸고, 좌우로 이동하면서 최소한의 조작으로 목표 이름을 만드는 것이 목표입니다.

실패한 풀이

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

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

    int next = i + 1;
    while (next < length && name.charAt(next) == 'A') {
        next++;
    }

    minMove = Math.min(minMove, i + length - next + i);
}

answer += minMove;
return answer;

풀이 설명

1. 초기 설정

   • answer는 최종적으로 필요한 최소 조작 수를 저장하는 변수입니다.
   • length는 주어진 이름의 길이입니다.
   • minMove는 이름을 만들기 위해 필요한 최소한의 좌우 이동 횟수를 저장합니다. 초기 값은 이름의 길이보다 하나 적게 설정했습니다.

2. 알파벳 변경 횟수 계산

   • 각 알파벳을 'A'에서 목표 알파벳으로 바꾸는 데 필요한 최소 조작 횟수를 계산합니다.
   • Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1)은 알파벳을 'A'에서 해당 알파벳으로 바꾸는 데 필요한 최소 조작 횟수를 의미합니다.

3. 최소 이동 횟수 계산

   • next는 현재 위치에서 연속된 'A'의 다음 위치를 찾습니다.
   • 만약 연속된 'A'가 있다면, 이 부분을 건너뛰기 위해 현재 위치에서 'A'가 끝나는 지점까지 돌아가고 다시 앞쪽으로 이동하는 방법을 고려합니다.
   • minMove는 이 방법과 현재 계산된 이동 횟수 중 최소값을 유지합니다.

4. 최종 계산

   • 알파벳 변경에 필요한 조작 수와 최소 이동 횟수를 더해 answer에 저장하고 반환합니다.

오늘 회고

• 최적화에 실패한 것 같다. 예제 케이스는 통과했으나 실제 제출했을 때 일부 실패하였다. 주말에 이어서 개선해보아야할듯하다.