문제
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한사항
- name은 알파벳 대문자로만 이루어져 있습니다.
- name의 길이는 1 이상 20 이하입니다.
풀이
알파벳 변화값: 'A'를 타겟 알파벳으로 바꾸는데 필요한 횟수
인덱스 간 이동: 인덱스에서 다른 인덱스로 움직이
1. 각 'A'를 타겟 알파벳으로 바꾸는데 필요한 횟수를 구한다 (인덱스 간 이동은 우선 고려하지 않는다)
우선 알파벳 변화값을 모두 합쳐서 answer에 저장해둔다. A에서 증가하여 타겟을 닿는 방법과 감소하여 타겟에 닿는 경우 중 최소 값을 저장한다.
- A, B, C, .. , F
- A, Z, Y, X, W .. F
인덱스 간 이동 횟수와 상관 없이 꼭 이동해야 하는 횟수다.
위를 먼저 계산하면 string의 인덱스 간 이동하면서 각 인덱스의 알파벳 변화값을 누적 저장해서 string의 나머지가 전부 'A'라 더이상 인덱스간 이동이 필요 없을 때를 알 수 있다.
(예) BBA에서 알파벳 변화 횟수는 2회다. 그래서 인덱스 0에서 +1를 하고, 오른쪽으로 이동하여 횟수+1로 횟수가 총 2회가 되면 더 이상 바꿔야 할 알파벳이 없다는 것을 확인하고 인덱스 간 이동을 할 필요가 없다.
2. 시작 인덱스에서 좌측으로 쭉 가는 경우와 우측으로 쭉 가는 경우를 계산해서 이 둘 중 최소 인덱스 이동이 더 적은 횟수를 저장한다.
이로써 가장 단순한 이동인 직선 이동의 최소 횟수를 구한다.
1에서 언급했듯이 이동하면서 최종 알파벳 변화값과 현재까지의 알파벳 변화값이 일치하는지 확인하기 때문에 아직 확인 전인 알파벳이 모두 연속적으로 'A'인 경우까지 고려해서 최소 횟수를 구할 수 있다.
3. 그런데, G T A A S K K A E 처럼, 단순 직선 이동이 아니라 왔다갔다 해야 하는 경우가 있다
위 예시에서는 G, T 방문 후 다시 G로 돌아온 다음, E, A, K, K, S 순으로 확인하는 것이 최소 이동횟수다.
이 경우를 포함하기 위해 연속되는 'A'의 시작과 끝을 확인하고, string을 A반복 시작 전과 후 두 파트로 나눈다.
이동은 시작 전 파트와 시작 후 파트 중 하나를 반복해야 되기 때문에 (G에서 T로 갔다가 G로 돌아온 것과 같이) 둘 중 하나를 두배하고 다른 하나를 저장했을 때의 최소값을 구한다.
2에서 찾은 최소 횟수와 비교하여 최종적인 최소 횟수를 구한다.
4. answer에 인덱스 간 최소 이동 횟수를 더한다.
코드
class Solution {
public int solution(String name) {
int answer = 0;
int charMoves = 0; // 이 변수에 최소 알파벳 변화값을 저장한다.
for (int i =0; i < name.length(); i++) {
// A부터 차례대로 가는 법과 반대로 가는 법 중 최소 값을 저장한다
int charMove = Math.min(name.charAt(i) - 'A', 26-(name.charAt(i) - 'A'));
charMoves += charMove;
}
// 최종 이동 횟수에 알파벳 변화값을 더한다.
answer += charMoves;
// 누적 이동횟수를 저장하여 바뀌어야 할 알파벳은 모두 방문했는지 확인한다.
int rightChanges = charMoves;
int leftChanges = charMoves;
// 인덱스 0에서부터 차례대로 방문하는 경우
int idx = 0;
int rightMoves = 0;
while (rightChanges != 0) {
int charMove = Math.min(name.charAt(idx) - 'A', 26-(name.charAt(idx) - 'A'));
rightChanges -= charMove;
if (rightChanges != 0) {
rightMoves += 1;
}
idx += 1;
}
// 인덱스 0부터 왼쪽으로 방문하는 경우
idx = 0;
int leftMoves = 0;
while (leftChanges != 0) {
int charMove = Math.min(name.charAt(idx) - 'A', 26-(name.charAt(idx) - 'A'));
leftChanges -= charMove;
if (leftChanges != 0) {
leftMoves += 1;
}
idx -= 1;
if (idx < 0) {
idx = name.length()-1;
}
}
int minMoves = Math.min(leftMoves, rightMoves);
int start = 0;
int end = 0;
idx = 0;
while (idx < name.length()-1) {
start = idx;
end = idx;
idx += 1;
while (name.charAt(idx) == 'A' && idx < name.length()-1) {
end += 1;
idx += 1;
int repeatStart = (start * 2) + (name.length()-end-1);
int repeatEnd = (name.length()-end-1)*2 + (start);
minMoves = Math.min(minMoves, repeatStart);
minMoves = Math.min(minMoves, repeatEnd);
}
}
answer += minMoves;
return answer;
}
}출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
