99클럽 3기 코테 스터디 19일차 TIL /[프로그래머스] 조이스틱 자바 풀이 그리디 문제

 

 

 

 

 

 

1. 오늘의 학습 문제 

---

문제

---

 

https://school.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 이하입니다.

입출력 예namereturn

"JEROEN"	56
"JAN"	23

 

 

 

 

 

 

코드

---

import java.util.*;
import java.io.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        int maxChunk=0;//바꾸지 않을 'A...' 문자열 덩어리의 최대길이
        int tempChunk= 0; //Chunk의 임시길이
        int[] keyIdx = new int[2]; // tempChunk의 양 끝 idx
        int lastIdx=0;// 문자열에서 바꿔야할 문자의 마지막 idx를 저장

        /*
        1. 문자별로 바꿔야할 횟수를 구해야할 것 같다.
        2. 커서 변경 최소 횟수
            바꿔야할 문자들을, 최소로 접근할 수 있는 방법을 알아야할 것 같다.
            시작문자~keyIdx[0] 최소거리와 시작문자~keyIdx[1] 최소거리 중 작은 것을 a, 큰 것을 b라할때,  
            min(a*2 + b > lastIdx )
         */

        for(int i=0;i<name.length();i++){
            if(name.charAt(i)!='A'){ //문자가 A가 아닐때(바꿔야함)
                //상 or 하 커서 조작시 최소 거리 구하기
                int distance=Math.abs(name.charAt(i) - 'A');
                answer+= Math.min(distance, 26-distance);
                lastIdx=i;

                //좌우 조작시 거리 구하기 위한 요소 계산
                // 'A..' 최대길이 덩어리에 대해 좌우 인덱스 구하기
                if(tempChunk>maxChunk) {
                    maxChunk = tempChunk;
                    keyIdx[0] = i - tempChunk - 1;
                    keyIdx[1] = i;
                }
                tempChunk=0; //'A'가 나왔으므로 chunk 초기화해주기
            }
            else{
                tempChunk++; //'A'덩어리 길이 세어주기
            }
        }

        int a=Math.min(keyIdx[0], name.length()-keyIdx[1]); //시작~ keyIdx 원소 중 최소거리
        int b= Math.max(keyIdx[0], name.length()-keyIdx[1]); //시작~ keyIdx 원소 중 최대거리

        return answer+ Math.min( 2*a + b, lastIdx);
    }
}

 

문제를 풀기 위해서는 두 가지를 나누어 고려해야한다. 

 

1. (상하)문자의 변경 횟수 

2. (좌우)커서 변경 횟수

 

 

 

1. (상하)문자의 변경 횟수 최솟값 구하기

  

1은 어렵지 않다. 현재 문자 -'A'의 절대값을 distance라 할때, distance와 26-distance중 작은 것을 더해주면 된다. 

                int distance=Math.abs(name.charAt(i) - 'A');
                answer+= Math.min(distance, 26-distance);

 

 

 

 

2. (좌우)커서 변경 횟수 최솟값 구하기

 

2는 고려할 사항이 좀 있다. 하지만 1번 아이디어를 사용하면 풀 수 있다. 

 먼저 한 방향으로 이동하는 방법이 있겠다. 단순히 ->왼쪽으로 이동한다고 생각하자. 문자열 중 맨 끝에 있는 'A'가 아닌 문자열의 idx까지 이동한다. 이를 lastIdx라 하자. 헷갈리니 A를 0, A가 아닌 문자를 1로 하겠다.

 

101000 

 

 이 경우 문자열의 길이는 6, lastIdx는 2이다. lastIdx인 2는 최소 이동횟수가 된다.

 

 하지만, 다음의 경우도 고려해야한다. 

 

100001

 

이 경우 문자열의 길이는 6, lastIdx는 5이다. 이때 최소 이동횟수는 lastIdx가 아니다. 

커서는 좌우로 움직일 수 있기에, 뒤로 조작하면 1이 최소 이동횟수가 된다. 

그렇다면 단순히 문자열길이-lastIdx가 최솟값일까? 그것도 아니다. 

 

왜냐면

 

010001

 

이 경우는, 최소이동횟수가 3이된다.. 따라서 연속해서 나오는 A의 최대길이 뭉치가 있다는 점을 생각해서,

그 최대길이를 구하고, 그 바로 좌우의 인덱스를 통해서 정답을 찾고자하였다.

최대길이 뭉치를 chunk라 하면, 그 부분은 커서를 통해 탐색할 필요가 없는 것이다. 

 

01010000010

          ↓
01010000010

 

이 경우 chunk의 길이는 5, 좌우 idx는 각각 3, 9이다 (각각 keyIdx[0], keyIdx[1]) . lastIdx는 9. 

 두 방향으로 탐색할때, 어떠한 방향으로 가더라도, 시작 부분을 거치기위해 다시 돌아와야할 것이다. 

이때 최소만 이동하기 위해, 시작~keyIdx[0]의 최소거리 , 시작~keyIdx[1]의 최소거리  중 작은 것을 구한다. 

int a=Math.min(keyIdx[0], name.length()-keyIdx[1]); //시작~ keyIdx 원소 중 최소거리
int b= Math.max(keyIdx[0], name.length()-keyIdx[1]); //시작~ keyIdx 원소 중 최대거리

 

이 경우는 keyIdx[1]이 시작부분과의 거리가 2이므로, 최소거리 a가 된다. 

이때, 2*a + b가 이동거리가 되겠다. 

이를 lastIdx와 비교하여, 작은 것을 선택하면 된다. 

 

return answer+ Math.min( 2*a + b, lastIdx);

 

2. 오늘의 회고

---

 

• 문제가 퍼즐 같아서, 풀이를 고민하는 것이 재미있었다. 
• 한동안 문제들이 어려웠는데, 오랜만에 직접 풀어서 기분이 좋았다, 그런데 다른 풀이를 참고하니 더 간단하게 코드를 작성한 경우가 많아서, 리팩토링에 대해 고민해봐야겠다. 나는 for문 끝에서 최종적으로 이동횟수를 구했는데, for문 내에서 비교하며 갱신하는 방법이 있었다. 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL