99클럽 코테 스터디 16일자 TIL + 조이스틱

이월(0216tw)·2024년 6월 4일

99클럽 TIL 개발자 취업 기능개발 미들러 자바 정렬 코딩테스트 코딩테스트준비 항해99

99클럽/알고리즘풀이

목록 보기

18/38

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42860(프로그래머스)

학습 키워드

Greedy

시도 방법

(1) 조이스틱을 위 아래로 돌리는 경우에는 Math.min(위로돌린경우 , 아래로돌린경우) 로 처리했다.

(2) 문제는 양옆으로 이동하는 것이었는데 처음에는 왼쪽으로 가는경우 , 오른쪽으로 가는 경우만 생각해서 통과하지 못했다.
왼쪽으로 갔다가 오른쪽 , 왼쪽 등 가는 경우가 있었기 때문이다
이부분은 GPT 도움을 받을 후 예시를 기반으로 아래에 작성하려 한다.

내가 작성한 코드

class Solution {
    public int solution(String name) {
    
        int moveCount = upDownStick(name); 
        moveCount += leftRightStick(name);        
        return moveCount;       
    }
    
    
    public int upDownStick(String name) {
        
        int result = 0 ;         
        for(char chr : name.toCharArray()) {             
            if(chr == 'A') continue;             
            
            result += Math.min( chr-65 , (chr-65-26)*-1 ); 
        }       
        return result;        
    }
    
    
    //이 부분은 GPT 도움 받음
    public static int leftRightStick(String name) {
       int length = name.length();
       int totalMoves = 0;

       // 좌우 이동의 최소 조작 횟수 구하기
       int moveCost = length - 1; // 초기값: 오른쪽으로 쭉 가는 경우

       for (int i = 0; i < length; i++) {
           int nextIndex = i + 1;
           // 다음 변경할 문자의 위치를 찾기
           while (nextIndex < length && name.charAt(nextIndex) == 'A') {
               nextIndex++;
           }

            // 왼쪽으로 돌아가는 경우와 비교하여 최소값 갱신
            moveCost = Math.min(moveCost, 2 * i + length - nextIndex);
            moveCost = Math.min(moveCost, i + 2 * (length - nextIndex));
        }

        return totalMoves + moveCost;
    }
}

코드설명

(1) 스틱을 위아래로 해서 알파벳을 target과 일치시키는 경우

각각의 문자열을 비교하면서 'A'는 별도의 처리를 하지 않는다. (target이 애초에 A인 경우)
chr-65는 오른쪽으로 이동한 횟수 , (chr-65-26)*-1 은 왼쪽으로 이동한 횟수이다.

(2) 스틱을 양옆으로 이동시켜 최소 이동 횟수를 찾는 경우

다음 데이터를 예시로 들어보자. (위아래는 고려하지 않는다)
"NOTBAAAAD"

이론적으로 보았을 때
오른쪽으로 이동하면 O(1) , T(1) , B(1) , D(5) 총 8 이동이 발생한다.
왼쪽으로 이동하면 D(1) , B(5) , T(1) , O(1) 총 8 이동이 발생한다.
만약 왼쪽으로 갔다가 오른쪽으로 가면 D(1) , O(2) , T(1) , B(1) 총 5 이동이 발생한다.

이를 소스의 변수에 대입해 확인해보겠다.

int length = name.length(); // 9
int totalMoves = 0; // 0
int moveCost = length - 1; // 9 - 1 = 8

i = 0
nextIndex = 1 일때 while문에서 false (1 < 9 && 'O' == 'A')
moveCost = Math.min(8 , 20 + 9 - 1) => min(8 , 8)
moveCost = Math.min(8 , 0 + 2 (9 - 1) ) => min(8 , 16)

i = 1
nextIndex = 2 일때 while문에서 false ( 2 < 9 && 'T' == 'A' )
moveCost = Math.min(8 , 2 1 + 8 - 2) => min(8 , 8)
moveCost = Math.min(8 , 1 + 2 (9 - 2 ) ) => min(8 , 15)

i = 2
nextIndex = 3 일때 while문에서 false ( 3 < 9 && 'B' == 'A' )
moveCost = Math.min(8 , 2 2 + 8 - 3 ) => min(8 , 7)
moveCost = Math.min(8 , 2 + 2 (9 - 3 ) ) => min(8 , 14)

i = 3
nextIndex = 4 일 때 while문에서 true ( 4 < 9 && 'A' == 'A')
nextIndex = 5 일 때 while문에서 true ( 5 < 9 && 'A' == 'A')
nextIndex = 6 일 때 while문에서 true ( 6 < 9 && 'A' == 'A')
nextIndex = 7 일 때 while문에서 true ( 7 < 9 && 'A' == 'A')
nextIndex = 8 일 때 while문에서 false ( 8 < 9 && 'A' == 'D' )
moveCost = Math.min(8 , 2 3 + 8 - 8 ) => min(8 , 6)
moveCost = Math.min(8 , 3 + 2 (9 - 8) ) => min(8 , 5)

이후 계속 증가하는 값이므로 가장 작은 수는 5 이다.