5일 전에 풀었던 문제를 미루고 미루다 이제야 올려봅니당..
이번에 푼 문제도 역시 프로그래머스 코딩테스트 연습 고득점 kit에 그리디 분류에 level2 문제다 ! ( 이게 그리디인지는 아직도 의문이고.. 레벨2 치고는 고민해야 할 부분이 은근 있었다 ! ) 문제 링크는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/42860
문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한 사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
입출력 예
| name | return |
|---|---|
| JEROEN | 56 |
| JAN | 23 |
풀이 방법
이 문제는 알파벳을 변경하기 위한 위 아래로의 조작, 각 문자로 이동하기 위한 좌 우로의 조작 두 가지를 모두 최소화 해야한다.
먼저 알파벳 변경은 단순히 위로가 까가운지 아래로가 가까운지만 판별하면 된다. 그렇기 때문에 문자열의 길이만큼 n번의 반복에서 아스키코드를 이용하여 위로 조이스틱을 조작할지, 아래로 조이스틱을 조작할지 판별하고 몇 회 조작할지를 모두 더해주었다.
다음으로 각 문자를 조작하기 위한 좌우 이동 횟수를 알아내야한다. 이 때의 변수는 A가 있는지 없는지, 있다면 어디에 위치하는지였다. A는 초기 값이기 때문에 변경할 것이 없으므로 그 위치에 도달하지 않아도 되기 때문이다.
위의 내용을 고려하여 크게 상황을 나누어보았다. 왼쪽이든 오른쪽이든 한 방향으로 쭉 이동하는 경우와 한 방향으로 갔다가 반대편으로 방향을 바꾸는 경우다. ( 이 경우를 앞으로 U턴이라고 표현할 것이다. )
먼저 간단하게 판별할 수 있는 case0과 case1은 각각 모든 문자가 A인 경우, A가 하나도 없는 경우이다. case0은 아무런 변화도 주지 않아도 되기때문에 0을 반환하고, A가 하나도 없는 경우는 한 방향으로 쭉 가면 되기 때문에 문자열의 길이 - 1 에 처음 반복문에서 구한 알파벳 조작 횟수를 더해서 반환해주면 된다.
이제 A와 A가 아닌 문자들이 섞여있는 경우들 중에서 한 방향으로 쭉 갈지, 그렇다면 오른쪽이 좋을지 왼쪽이 좋을지 그리고 모든 칸을 거쳐야하는지, U턴을 해야하는지를 판별해야한다. 이를 반별하기 위해서는 세가지 변수가 필요했다.
1. 가장 길게 A가 연속해서 반복되는 구간의 길이 ( maxA )
2. A가 가장 길게 연속해서 반복되는 구간까지 도달하기 위해서 처음 위치에서 왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때의 경우에 더 가까운 방향과 그 거리 ( distance )
3. 처음 위치의 바로 오른쪽 혹은 바로 왼쪽에 A가 있는지, 있다면 몇 개가 연속으로 반복되는지 그 개수 ( leftA, rightA 그리고 둘 중에 더 긴 구간 bigger )
위의 값들을 이용해서 maxA <= distance인 경우는 한 방향으로 쭉 가야하는 경우이므로 문자열의 길이 - 1에 알파벳 조작 횟수를 더해서 반환해주면 되는데 이 때, bigger만큼은 도달하지 않아도되는 구간이기 때문에 bigger를 빼준다. ( 만약 처음 위치의 바로 오른쪽 왼쪽에 A가 없다면 bigger가 0일 것이므로 일관되게 처리 가능하다. )
max > distance인 경우에는 bigger의 크기와 maxA와 distance의 값 중 어떤것이 크냐에 따라서 한 방향으로 갈지, U턴을 해야할지가 정해진다. bigger가 더 큰 경우는 한 방향으로 가고 bigger구간에 도달하지 않는 것이 조작 횟수가 더 줄어드므로 위의 경우와 같은 결과를 반환하게 된다. 반대로 bigger가 더 작은 경우는 U턴을 해야하는 경우이므로 distance구간은 두 번을 거치므로 2배를 해주고 maxA구간은 도달하지 않아도 되므로 그 만큼의 길이는 빼준 후 알파벳 조작 횟수를 더해서 반환해준다 !
( 다른 아이디어가 있을 수 있지만, 본인은 A가 있는 경우 그 구간을 도달하지 않아도 되는 경우에 핵심을 맞춰서 고민하다보니 위의 세가지 변수들을 이용하여 경로를 판별하는 다음과 같은 알고리즘이 나오게 되었다. 쓰다보니 길어지고 복잡해졌지만 코드는 막상 간단하게 느껴질수도 있을 것이다. 시간 복잡도도 O(n)으로 좋은 수준으로 결과를 도출할 수 있다 ! )
코드
원래 알고리즘 문제를 풀 때 주석을 잘 안 다는데, 이거는 케이스를 명확하게 나눠서 풀었고, 아이디어를 구현에 옮기는 과정에서 나도 헷갈려서 주석을 달아두었다 ! 위의 풀이 방법 설명에서 아이디어를 얻고 아래의 코드를 주석과 함께 읽는다면 이해에 도움이 될 것이라고 생각한다 !
public static int solution(String name) {
// 알파벳 변경 횟수랑 A가 연달아서 가장 길게 있는 구간 개수 및 그 끝 위치 구하기 한 for문에서 !
int alphaChanged = 0;
int maxA = 0;
int countA = 0;
int maxIndex = -1;
for(int i=0; i<name.length(); i++){
// 알파벳 변경 조이스틱 횟수
if((int)name.charAt(i)-65 < 13){ alphaChanged += (name.charAt(i)-65); }
else{ alphaChanged += (91-name.charAt(i)); }
// 연달아서 있는 A 개수 시작위치
if(name.charAt(i) == 'A'){
if(i != 0) countA++;
if(i == name.length()-1){
if(countA > maxA){
maxA = countA;
maxIndex = i-1;
}
}
}
else{
if(countA > maxA){
maxA = countA;
maxIndex = i-1;
countA = 0;
}
}
}
// case 0
// 다 A인 경우
if(maxA == name.length()-1) return 0;
// case 1
// A가 없는 경우
// alphaChanged + 오른쪽으로 쭉 가는 경우니까 length() - 1 해서 return
if(maxA == 0){ return alphaChanged+name.length()-1; }
// 가장 긴 구간까지 왼쪽 혹은 오른쪽 더 가까운 거리 구하기
int distance = maxIndex - maxA;
if((name.length()-maxIndex-1) < distance) distance = name.length()-maxIndex-1;
// 바로 오른쪽과 바로 왼쪽에 A가 있는지, 있다면 연달아 몇개인지 구하기기
int leftA = 0;
int rightA = 0;
for(int i=1; i<name.length(); i++){
if(name.charAt(i) == 'A') leftA++;
else break;
}
for(int i=1; i<=name.length(); i++){
if(name.charAt(name.length()-i) == 'A') rightA++;
else break;
}
int bigger = rightA;
if(leftA > rightA) bigger = leftA;
// case2
// maxA >= distance
// case3
// maxA < distance
// leftA rightA 고려하기
if(maxA <= distance){ return name.length()-bigger-1+alphaChanged; }
else{
if(maxA-distance < bigger) return name.length()-bigger-1+alphaChanged;
return (distance*2)+((name.length()-1)-(distance+maxA))+alphaChanged;
}
}