[탐욕법(Greedy)] 조이스틱 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/42860?language=java 

코딩테스트 연습 - 조이스틱

---

이 문제 진짜 어려웠다

난 탐욕법에 약한 것 같다

특히 인덱스 이용해서 구하는 문제가 나올 때 식을 계산하는 것이 너무 어렵다..ㅠ_ㅠ

 

우선 상하로 움직이는 부분은 쉽게 구했다

A부터 움직이는 방법과 Z부터 뒤로 움직이는 방법 중 작은 값을 고르면 된다

이 때 Z부터 움직이려면 뒤로 한 번 가야하므로 1을 더해준다

 

문제는 좌우 인덱스 이동이다

연속되는 A의 갯수를 구해서 좌우 중 어디로 움직이는 것이 이득일지 선택하면 된다

연속하는 A의 갯수를 구하는 방법도 쉽다

현재 인덱스의 뒷부분부터 반복문을 돌면서 문자가 A라면 더해주면 된다

 

중요한 부분은 좌우 선택이다

// 순서대로 가는 것과, 뒤로 돌아가는 것 중 이동수가 적은 것을 선택
move = Math.min(move, i*2+name.length()-index);

// BBBBAAAAAAAB와 같이 처음부터 뒷부분을 먼저 입력하는 것이 더 빠른 경우도 고려
move = Math.min(move, (name.length()-index)*2 + i);

첫번쨰 코드에서 i에 2를 곱한 이유는 현재 온 인덱스로부터 다시 뒤로 돌아가야되기 떄문이다

출처는 아래에 남겨두었습니다

이건 내가 보고 이해한 그림이다!

i를 2번 곱해서 더하는 이유가 잘 그려져있다!!

 

후... 진짜 어렵네잉..

아무튼 코드!

 

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        int index;
        int move = name.length()-1;
        
        for(int i=0;i<name.length();i++) {
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
            
            index = i+1;
            while(index<name.length() && name.charAt(index) == 'A') {
                index++;
            }
            move = Math.min(move, i*2+name.length()-index);
            move = Math.min(move, (name.length()-index)*2 + i);
        }
        return answer + move;
    }
}

 

 

 

 

 

참고 블로그)

https://velog.io/@jeeseob5761/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1

[프로그래머스] 조이스틱 자바

 

https://excited-hyun.tistory.com/207

[프로그래머스 - Java] 조이스틱