![[프로그래머스,Level 2] 조이스틱(JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FblZYKw%2FbtqT8JjQrNM%2F51Kpoeq0lA6USfn0W3Fv11%2Fimg.png)
- 첫 풀이 및 정답풀이
이 문제를 처음 읽고 이해하는 데 시간이 좀 걸렸다. 설명을 간단하게 풀어보면, 상하 방향은 단순히 알파벳을 변경하는 것이고 좌우 방향은 커서를 옮기는 것이다. 단, 여기서 말하는 커서는 우리가 일반적으로 생각하는 | 커서보다 직사각형 크기의 커서를 생각하면 편하다. 그리고 모든 이름의 첫 시작은 AAA로 시작하게 된다.
입력 예제 2를 통해 보면, 3자리의 이름인 JAN을 만들기 위해서는 AAA를 적절히 변형시켜야 한다. 첫 시작은 첫 번째 문자부터 이므로 초기 상태는 AAA 이 상태이다. 이 상태에서 첫 글자를 J로 바꾸면 JAA이고 여기서 왼쪽으로 한 번 옮기면 JAA 상태가 된다. 그 후, 마지막 글자를 Z로 바꾸면 JAZ가 되며 완성이 된다.
마지막으로 이 문제에서 원하는 조이스틱의 조작 횟수를 구하기 위해서는 좌 or 우 이동 횟수 + A가 아닌 문자의 상 or 하 이동 횟수로 구할 수 있다.
문제의 기본 개념을 이해한 상태에서 필자는 두 가지의 로직으로 나누어 구현하기로 했다. 첫 번째로 상,하 방향으로 알파벳을 변경하는 로직과 두 번째는 좌,우 방향으로 이동하는 횟수를 카운팅 하는 로직이다.
상,하 방향으로 움직여 알파벳을 변경하는 횟수를 구하는 로직은 아스키코드를 이용했다. 아스키코드 상으로 알파벳 대문자 A ~ Z는 65 ~90이므로, 이를 정수로 변환해 -65를 취하면 0~25로 알파벳에 대한 참조가 가능하다. 위의 첫 번째 글자를 J로 바꾸는 과정을 통해 살펴보자.
1. 모든 시작은 A인 0부터 시작한다.
2. J는 9로 참조가 가능하다.
3. A->J는 9-0 = 9로 조이스틱을 9번 위로 올리면 변경이 가능하다.
4. 반대로 아래 방향으로 조이스틱을 접근하게 된다면 A->Z 후, Z->J로 접근해야 한다. 이는 Z인 25 -J인 9 = 16이 나온다. 여기에 A->Z로 한 번 더 움직였기에 최종적으로 조이스틱을 17번 아래로 내리면 변경이 가능하다.
5. 두 방법 중 적은 횟수를 움직이는 것은 9번이므로 첫 번째 글자를 J로 바꾸기 위해선 조이스틱을 9번 움직인다.
위의 과정을 A가 아닌 알파벳을 만날 때마다 수행해주면 알파벳을 변경하는 첫 번째 로직이 완성된다. 코드를 통해 보자.
class Solution {
public int solution(String name) {
int answer = 0;
// 1. 주어진 문자열 탐색.
for(int i =0 ; i<name.length();i++){
// 2. 만난 문자가 A가 아니면 변경해주어야 한다.
if(name.charAt(i) != 'A'){
// 3. ud_min: 상 또는 하 방향으로 움직이는 최소 횟수.
int ud_min,x,y;
// 4. x: A에서 특정 알파벳으로 변경을 위해 상으로 움직이는 횟수.
x = Math.abs((name.charAt(i) - 65) - 0);
// 5. y: A에서 특정 알파벳으로 변경을 위해 하로 움직이는 횟수, A->Z를 위해 +1을 수행.
y = Math.abs((name.charAt(i) - 65) - 25)+1;
// 6. 상,하 중 최소 횟수를 취한다.
ud_min = x<=y ? x : y;
// 7. answer 변수에 누적합.
answer+=ud_min;
}
}
}
}다음은 좌,우 방향으로 이동하는 횟수를 카운팅 하는 로직을 구현한다. 구현을 시작했을 때는 최소횟수를 구해야 하기 때문에 우측으로 갔다가 다시 돌아가는 경우는 배제해도 된다고 생각하여 우측 또는 좌측으로의 일방통행만을 고려했다.(예외가 존재한다.) 우선 일방통행의 경우만 알파벳 변경 로직은 고려하지 않고 입력 예제 1번을 조금 변형해 과정을 살펴보자.
먼저, 우측 방향으로의 일방통행이다.
| 0 | 1 | 2 | 3 | 4 | 5 |
| J | E | A | O | A | A |
1. 초기 스타트는 0번 인덱스인 J부터이다.
2. ->로 1번 인덱스에서 1번, ->->로 2번 인덱스에서 2번, ->->->로 3번 인덱스에서 3번.....
3. 결국 오른쪽 이동은 각 번호의 인덱스 만큼 이동하게 된다.
4. 이러한 특성을 이용해 A가 아닌 문자인 경우, 해당 인덱스를 별도의 변수에 저장한다.
5. 위 예제에서는 3번 인덱스가 저장된다. 즉, 오른쪽으로 3번 움직인 경우이다.
결국 알파벳 변경 로직에서 8. 한 줄만 추가해주면 된다.
class Solution {
public int solution(String name) {
int answer = 0;
// 오른쪽 이동 횟수 저장 변수
int r_idx = 0;
// 1. 주어진 문자열 탐색.
for(int i =0 ; i<name.length();i++){
// 2. 만난 문자가 A가 아니면 변경해주어야 한다.
if(name.charAt(i) != 'A'){
// 3. ud_min: 상 또는 하 방향으로 움직이는 최소 횟수.
int ud_min,x,y;
// 4. x: A에서 특정 알파벳으로 변경을 위해 상으로 움직이는 횟수.
x = Math.abs((name.charAt(i) - 65) - 0);
// 5. y: A에서 특정 알파벳으로 변경을 위해 하로 움직이는 횟수, A->Z를 위해 +1을 수행.
y = Math.abs((name.charAt(i) - 65) - 25)+1;
// 6. 상,하 중 최소 횟수를 취한다.
ud_min = x<=y ? x : y;
// 7. answer 변수에 누적합.
answer+=ud_min;
// 8. 마지막 인덱스를 저장.
r_idx = i;
}
}
}
}
다음은, 왼쪽 방향으로의 일방통행이다.
| 0 | 1 | 2 | 3 | 4 | 5 |
| J | E | A | O | A | A |
1. 초기 스타트는 5번 인덱스인 A부터이며, 0번 인덱스에서 스타트하므로 1번 인덱스까지만 고려해준다.
2. 0번 인덱스에서 <-로 5번 인덱스에서 1번, <-<-로 4번 인덱스에서 2번, <-<-<-로 3번 인덱스에서 3번....
3. 마찬가지로 규칙성을 찾을 수 있다. number.length() - 마지막 인덱스(1번).
4. 결국 왼쪽으로 이동은 6 - 1로 5번 움직여야 한다.
이 과정을 위해서는 별도의 반복문을 하나 더 작성한다.
class Solution {
public int solution(String name) {
int answer = 0;
// 오른쪽, 왼쪽 이동 횟수 저장 변수
int r_idx = 0,l_idx = 0;
// 1. 주어진 문자열 탐색.
for(int i =0 ; i<name.length();i++){
// 2. 만난 문자가 A가 아니면 변경해주어야 한다.
if(name.charAt(i) != 'A'){
// 3. ud_min: 상 또는 하 방향으로 움직이는 최소 횟수.
int ud_min,x,y;
// 4. x: A에서 특정 알파벳으로 변경을 위해 상으로 움직이는 횟수.
x = Math.abs((name.charAt(i) - 65) - 0);
// 5. y: A에서 특정 알파벳으로 변경을 위해 하로 움직이는 횟수, A->Z를 위해 +1을 수행.
y = Math.abs((name.charAt(i) - 65) - 25)+1;
// 6. 상,하 중 최소 횟수를 취한다.
ud_min = x<=y ? x : y;
// 7. answer 변수에 누적합.
answer+=ud_min;
// 8. 마지막 인덱스를 저장.
r_idx = i;
}
}
// 9. 왼쪽 일방통행 이동 횟수를 구하기 위한 반복문.
for(int i=name.length()-1;i>0;i--){
// 10. A가 아닌 경우 인덱스를 갱신한다.
if(name.charAt(i) != 'A') l_idx =i;
}
// 11. 전체 문자열의 길이 - 해당 인덱스 = 왼쪽으로 이동 횟수.
l_idx = name.length()-l_idx;
}
}이제 오른쪽과 왼쪽 이동 횟수 중 더 작은 값을 알파벳 변환 횟수와 더해주면 예제 테스트 케이스는 통과가 가능하지만, 제출 시 테스트 케이스 11번에서 실패가 나오게 된다.
테스트 케이스 11번이 바로 앞서 언급한 이동방향을 변경하는 경우이다. 이에 대한 대표적인 테스트 케이스는 "ABABAAAAABA" #11과 "ABAAAAAAAAABB" #7이 있다. "ABAAAAAAAAABB"를 예로 들어보자.
칸의 한계로 길이를 10으로 하겠다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| A | B | A | A | A | A | A | A | B | B |
이 예시를 위의 일방통행 방법으로 구하면 오른쪽 방향과 왼쪽 방향 모두 9번 움직여야 한다. 하지만 오른쪽으로 이동하다가 왼쪽으로 이동하면, A->B(1번)->A(0번)->B(9번)->B(8번)으로 총 4번 움직이면 변경이 가능하다. 이를 해결하기 위해 필자가 생각한 방법은 아래와 같다.
1. 우선 A가 아닌 알파벳이 처음 등장한 뒤 부터 고려한다.
2. pre_idx라는 변수를 통해 현재 i가 가리키는 인덱스 이전의 인덱스 값을 저장하는 변수를 사용한다.
=> 1번 인덱스는 처음 등장하는 A가 아닌 알파벳이다. (i =1, pre_idx =1로 갱신.)
=> i가 다음 등장하는 A가 아닌 알파벳인 8을 가리킨다. (i = 8, pre_idx=1)
3. 이 상태에서 pre_idx -> i로 가기 위해선 i - pre_idx만큼 이동해야 한다. ( 8 - 1 = 7)
4. 다시 돌아가는 방법은 pre_idx만큼 이동한 거리를 돌아가면 0번 인덱스, 왼쪽 방향 이동 횟수를 구하는 number.length() - i를 통해 10 - 8 = 2 만큼 이동해야 한다. 즉, pre_idx + (number.length() - i) = 3
5. 결국, 그대로 진행하는 경우 7 > 다시 돌아가는 경우 3으로 최소를 취하기 위해 다시 돌아간다.
6. 단, 주의해야 할 점은 pre_idx + (number.length() - i) = 3라는 결과는 1번 인덱스에서 8번 인덱스로 이동하는 경우였기 때문에 1번 인덱스까지 가는 pre_idx를 한 번 더 더해주어야 한다. (pre_idx * 2) + (number.length() - i) =4
여기까지 다시 돌아가는 경우까지 고려했으므로 해당 결과를 별도의 변수에 저장하여 Math.min(Math.min(오른쪽 일방통행, 왼쪽 일방통행), 다시 돌아가는 경우)로 최소 이동 횟수를 취하면 된다. 마지막으로 최종 코드이다.
class Solution {
public int solution(String name) {
int answer = 0;
// 오른쪽, 왼쪽 이동 횟수 저장 변수
int r_idx = 0,l_idx = 0;
// 이전 인덱스를 저장하는 변수, 다시 돌아가는 경우의 횟수를 저장하는 변수.
int pre_r=0, lr_idx=0;
// 1. 주어진 문자열 탐색.
for(int i =0 ; i<name.length();i++){
// 2. 만난 문자가 A가 아니면 변경해주어야 한다.
if(name.charAt(i) != 'A'){
// 3. ud_min: 상 또는 하 방향으로 움직이는 최소 횟수.
int ud_min,x,y;
// 4. x: A에서 특정 알파벳으로 변경을 위해 상으로 움직이는 횟수.
x = Math.abs((name.charAt(i) - 65) - 0);
// 5. y: A에서 특정 알파벳으로 변경을 위해 하로 움직이는 횟수, A->Z를 위해 +1을 수행.
y = Math.abs((name.charAt(i) - 65) - 25)+1;
// 6. 상,하 중 최소 횟수를 취한다.
ud_min = x<=y ? x : y;
// 7. 처음 등장하는 A가 아닌 알파벳인 경우( answer에 값이 존재한다.)
// && 일방통행 횟수 > 돌아가는 횟수 인 경우.
if(answer!=0 && i-pre_r>pre_r+(name.length()-i)){
// 8. 돌아가는 횟수를 갱신.
lr_idx = pre_r * 2 + (name.length()-i);
}
// 9. 이전 인덱스로 저장
pre_r = i;
// 10. 오른쪽 이동횟수 갱신.
r_idx = i;
// 11. answer에 누적합.
answer+=ud_min;
}
}
// 12. 왼쪽 일방통행 이동 횟수를 구하기 위한 반복문.
for(int i=name.length()-1;i>0;i--){
// 13. A가 아닌 경우 인덱스를 갱신한다.
if(name.charAt(i) != 'A') l_idx =i;
}
// 14. 전체 문자열의 길이 - 해당 인덱스 = 왼쪽으로 이동 횟수.
l_idx = name.length()-l_idx;
// 15. 방향을 바꾸는 경우가 존재하지 않는다면, 일방통행 중 최솟값.
if(lr_idx !=0)
answer+=Math.min(Math.min(r_idx,l_idx),lr_idx);
// 16. 방향을 바꾸는 경우가 존재하면, 세 가지 경우 중 최솟값.
else
answer+=Math.min(r_idx,l_idx);
return answer;
}
} 이 문제는 방향을 바꾸는 경우가 추가된 테스트 케이스로 말이 많더라.