[프로그래머스] 조이스틱 for JAVA _ 그리디 알고리즘

 

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

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

 

 

문제

 

 

 

 

---

 

 

약간 노가다로 풀었다.

 

 

우선 조이스틱 상하를 살펴보면

 

A~N까지 0~13이고 Z~O가 0~12이다. N이 딱 가운데임

 

그래서 arraylist에 A~N, Z~O 를 각각 넣어서 몇 번째에 있는지 확인해 answer에 더해주었다.

 

 

조이스틱 좌우가 어려운데.. 예를 들어 ABAAAAAAB 일 때 무작정 오른쪽으로 가면 효율이 떨어진다.

 

> < < 순서로 +3을 해야하는거임 코드로 짤때는 생각이 안나서 다른 사람꺼 참고했다.

 

먼저 A가 연속으로 있을 때를 확인하기 위해 nextIndex = i + 1로 만들어준다.

 

while문으로 A가 연속으로 있는지 확인하기 위해

 

그리고 이 인덱스에 해당하는 문자가 A인지 확인하고

A라면 nextIndex ++;를 해주고 다시 while문으로 이 인덱스가 A인지 확인...

 

이런식으로 연속된 A인지 확인한다. 연속이 끝나면 마지막으로 nextIndex++; 하고 끝난 nextIndex값을

 

name.length() 값에서 빼준다.

 

 

그러니까 name.length()에서 뭉텅이 A의 연속값을 빼주는거다.

 

원래 name.length() -1 이 최대 이동 횟수인데 맨 앞에서 맨 뒤로 가는 +1도 해줘야하니까 +1-1은 따로 안넣어주는거임

 

 

그리고 맨 앞에 A -> B, 그리고 다시 A <- B 이렇게 무조건 2번을 왔다갔다 해야하므로

 

i * 2번을 더해야한다.

 

 

그래서

 

int nextIndex = i + 1;
while(nextIndex < name.length() && name.charAt(nextIndex) == 'A')
      nextIndex++;
            
 min = Math.min(min, (i * 2) + name.length() - nextIndex);

 

를 한 min값이 조이스틱 좌우 값이 되어 answer에 더해준다.

 

 

 

코드

 

import java.util.List;
import java.util.Arrays;

class Solution {
    public int solution(String name) {
        int answer = 0;
        int min = name.length() -1;
        
        String[] Falpha = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"};
        String[] Balpha = {"A", "Z", "Y", "X", "W", "V", "U", "T", "S", "R", "Q", "P", "O"};
        
        List<String> Flist = Arrays.asList(Falpha);
        List<String> Blist = Arrays.asList(Balpha);
        
        for(int i = 0; i < name.length(); i++){
            
            //상하
            if((Flist.indexOf(String.valueOf(name.charAt(i)))) != -1)
                answer += Flist.indexOf(String.valueOf(name.charAt(i)));
            else if((Blist.indexOf(String.valueOf(name.charAt(i)))) != -1)
                answer += Blist.indexOf(String.valueOf(name.charAt(i)));
            
            //좌우
            int nextIndex = i + 1;
            while(nextIndex < name.length() && name.charAt(nextIndex) == 'A')
                nextIndex++;
            
            min = Math.min(min, (i * 2) + name.length() - nextIndex);
        }
        
        answer += min;
        
        return answer;
    }
}

 

 

charAt을 사용해서 string과 비교를 하려니

charAt으로 char된 값을 다시 String.valueOf를 이용해 string 값으로 변환해줘야하는 아주..비효율적인 코드가 나왔다.

 

후~~~

 

 

 

성능

 

 

 

좌우는 걍 다른사람꺼 참고했다.

 

 

https://hellodavid.tistory.com/4

이분이 진짜 깔끔하게 짜셨다.

 

public int solution(String name) {
  int answer = 0;
  int len = name.length();

  // 제일 짧은 좌, 우 이동은 그냥 맨 오른쪽으로 이동할 때
  int min = len - 1;

  for (int i = 0; i < len; i++) {
    // 조이스틱 상, 하 이동
    char c = name.charAt(i);
    int mov = (c - 'A' < 'Z' - c + 1) ? (c - 'A') : ('Z' - c + 1);
    answer += mov;

    // 조이스틱 좌, 우 이동
    int nextIndex = i + 1;
    // 다음 단어가 A이고, 단어가 끝나기 전까지 nextIndex 증가
    while (nextIndex < len && name.charAt(nextIndex) == 'A')
      nextIndex++;

    min = Math.min(min, (i * 2) + len - nextIndex);
  }

  answer += min;

  return answer;
}

 

 

상하 움직임을 mov = (c - 'A' < 'Z' - c + 1) ? (c - 'A') : ('Z' - c + 1); 이 코드 하나로 정리한게 ㅎㄷㄷ

 

 

아니 좌우 저거 어떻게 짜는거지 진짜... 천재들인가

 

 

 

 

---

다른 사람 코드

 

 

 

 

음~ 나처럼 리스트 2개 안쓰고 걍 배열에 숫자를 넣었다.

 

.toCharArray()를 이용해 문자열을 char형 배열로 만들어준다.

 

char 문자에서 'A' = 67이다. 이것을 이용해 diff 배열 index 값을 더해준다.

 

좌우는 위와 같음