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

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

1. 문제 및 접근 방법

 

완성해야 하는 글자가 3글자면 AAA, 4글자면 AAAA로 주어지는데 조이스틱 마다 기능이 있다

위는 다음 알파벳, 아래는 이전 알파벳(a라면 z로 이동가능)

왼쪽은 커서의 이동(왼쪽 끝이면 오른쪽), 오른쪽도 커서의 이동(오른 끝이면 왼끝으로)

가장 적게 움직여서 원하는 글자 만들기!

 

 

커서의 이동은 aaaaaaz를 만들어야 한다면 왼쪽 커서로 움직이는게 베스트니까 필요

알파벳을 저장해두고, 알파벳 총 크기와 그 수를 크기를 비교해 반이상일지 아닐지 판별, (저장할 필요 xx)

왼 오도 전체 문장의 인덱스와 그 인덱스의 절반을 비교해 왼일지 오른일지 판별

왼 오로 움직이려면 현재 인덱스를 저장해줘야 하나 ? aabaaaaaaab라면 오2번, 왼3번으로 최소 움직임을(반대 상관x)가질 수 있으니

알파벳 순서는 링크드 리스트로 관리 ? or  현재 위치는 큐로 관리 ? (이럴 필요 x)

 

 

 

 

 

 

 

2.  풀이

 

private final static int[] AlPHABET = new int[]
            {       65,66,67,68,69,70,71,72,73,74,
                    75,76,77,78,79,80,81,82,83,84,
                    85,86,87,88,89,90};
    public static void main(String[] args) {

        조이스틱 main = new 조이스틱();
        System.out.println(main.solution("JAZ"));;



    }

    public int solution(String name) {


        int count = 0;
        int answer = 0;
        int length = name.length();

//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < name.length(); i++) {
//            sb = sb.append("A");
//
//
//        }
//        String answer = sb.toString();
//        while (answer != name) {
//
//        }



        for (int i = 0; i <length; i++) {
            int now = name.charAt(i);

            if (now <= 77) {
                count = count+(now - 65);

            } else {
                count = count + (91 - now);
            }
        }


        int min = length - 1; // 오른쪽으로만 가능 경우로 일단 먼저

        for (int i = 0; i < length; i++) {
            int next = i + 1;
            while (next != length && name.charAt(next) == 65) {
                next++;
            }
            // i까지 가는 거리 + 돌아가서 나머지 처리하는 거리
            min = Math.min(min, i + length - next + Math.min(i, length - next));
        }

        answer = count + min;


        return answer;
    }

 

전체 풀이

 

 

 

일단 2단계로 나눠서 풀었는데, 다시 합쳐서 시도해야겠다

 

 

 

 

 

2-1 아스키코드 ?

 

 

 

아스키코드는 American Standard Code for Information Interchange의 약자로서,

ASCII라고 불린다. 또한 ANSI에서 만든 표준 코드체계이다.

아스키는 각 문자를 7비트로 표현하므로 2^7 = 128개의 문자를 표현할 수 있다.

 

 

 

0~127에 대응하는 아스키 코드 표

https://velog.io/@dingdoooo/JavaStudy-4.-%EC%95%84%EC%8A%A4%ED%82%A4%EC%BD%94%EB%93%9C-Char-String-%EB%B3%80%ED%99%98%EA%B3%BC-%EC%9D%91%EC%9A%A9

 

 

 

 

 

2-2 알파벳 변환 계산

 

 

 

먼저 알파벳의 아스키 코드 값으로 접근했다.

 

현재 알파벳이 아스키 코드 기준 중간 값이거나, 작다면 

현재 알파벳의 아스키 코드에서 65를 빼 위로 움직이고,

 

크다면 뒤에서 접근하는 아래로 움직여 횟수를 세어준다. (91은 A부터 시작하기에 하나 더 추가)

 

 

 

 

 

 

2-3 좌우 움직임 계산

 

 

먼저 min을 아무 조건없이 오른 쪽으로 이동하는 경우로 초기화

6개의 글자라면 5번 움직임

 

그 다음은 A(65)가 아니고, next가 length만큼 크기가 되기 전까지 계속 돌면서

A가 아닌 수의 곳을 찾아준다 ! (A라면 거기로 갈 필요가 없어지기에 제외시킬 수 있으니)

 

 

 

그리고 최소의 움직임을 비교해주는데, 약간 복잡하다.

 

상, 하는 사실 A부터 시작이라 고정 값이지만, 좌, 우는 현재 위치에 따라 달라진다. (계속 최적만 찾으면 되긴 하지만)

 

 

최소 이동거리라는 건 현재 i 값에서 다음 next로 움직이기 위해서 왼쪽으로 갈 지 오른 쪽으로 갈 지

 

1. 현재 위치인 i에서 직진(오른쪽)으로 이동하는 거리 or
2. 시작위치로 후진(왼쪽) 쭉 왼쪽으로 이동하는 거리

 

i + length - next는 직진하는 경로이다.

i에서 출발해 next로 가는 거리

 

반대로 가려면 Math.min(i, length-next) 현재 i번째 위치와 전체 수에서 next를 빼주는 값 중 작은 게 반대로 가는 경로

 

1. 각 수마다 왼쪽으로 갈 지 or 오른 쪽으로 갈 지 정하고

 

2. 다음 과정은 현재 위치에서 'A'가 아닌 위치까지 직진하는 경우 vs

 

 

 

 

현재 위치 i에서 다음의 'A'가 아닌 문자인 next로 이동하는 최소 경로를 뜻하는데,

 

 

1. 직진해서 다시 돌아오는 경로

(i +  length - next)현재 위치은 i에서 다음 'A'가 아닌 next로 직진 후 되돌아오는 경로

 

2. 짧은 경로

Math.max(i, legth - next)는 현재 i에서 시작 위치로 돌아가는 length - next와 시작점에서 A로 가는 (i)의 거리 중 작은 값을 선택

즉 왼쪽으로 가냐 오른 쪽으로 가냐 중 적은 값을 정하함

 

 

 

쉽게 말해 A아닌 수 때문에 

 

 

ex) "aabaaaaaaab"라면 오2번, 왼3번으로 최소 움직임을 가질 수 있으니 (왼3 오2도 상관 x)

 

 

계속 일자로 움직일 수가 없기에  다시 돌아가서 next로 뒤로 이동하는 것과 직진을 비교 후 최소 거리를 저장하고,

그렇게 정해진 최소 거리와 더 적은 거리를 계속 비교해가면서 min에 업데이트

 

 

 

마지막으로 위에 세어준 count와 이동거리를 더해주면 끝!

 

 

 

 

 

3 마무리

 

사실 처음엔 둘(상하와 좌우의 계산)을 합치고 싶었으나

Stringbuilder로 "AAA"를 만들어준 후 정답과 비교비교하면서  바꿔주고 count 세려고..

 

풀 시간이 크게 없어 간단하게 접근했다.. 다음에 순서는 queue를 써서 넣고 순서를 비교 해봐야겠다.

 

그리디 알고리즘 분류라고 하는데,

그리디는 현재 해가 다음 해를 고려하지 않고 현재의 최선이 결과적인 최선이라고 할 수 있는 알고리즘이다.

 

마시멜로 실험의 반례같은 느낌이라고 생각하면 그냥 완전 이해~!

 

a -> 정답인 char로 바꿔 주는건 편하게 접근했으나, 순서는 약간 복잡해서 어려웠다 ㅠㅠ