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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱 | 프로그래머스

나의 풀이 추가 - 2020.04.14

해당 게시글에 댓글이 달린 김에 코드를 다시 확인해보았는데, 과거의 코드지만 너무 어렵게 푼 것 같다는 생각이 들었다...

 

프로그래머스의 다른 사람의 풀이를 보고 훨씬간단하게 풀이한 내용이 있어서 응용해서 다시 풀어보았다..

 

역시나 조이스틱을 위, 아래로 움직이는 경우는 최소한의 움직임으로 계산해 준다.

 

그리고 좌, 우로 움직이는 경우는 A가연속해서 등장하는 경우 뒤로 돌아가서 최솟값을 구해주었다.

 

- A가 한 번도 등장하지 않았다면 좌-> 우로 가는 것이 제일 빠르다. ( 다른 방법이 없다. )

- A가 여러 번 등장하는 경우는 최초 A가 나올 때까지 갔다가 -> 뒤로 돌아가서, A가 끝나는데까지만 세주면 된다.

 

ex) BBAAAAAAAAAABB 일 때,

 

최초 A가 시작되는 2번째 index(A) 이전까지만 갔다가, 왼쪽으로 다시 이동해서 연속된 A가 종료되는 12번째 index(B)까지만 이동하면 된다.

 

주어진 문자열을 모두 순회하면서, A를 만났다면, 연속된 A의 종료지점을 구해준다. 그리고 위의 계산을 하면 된다.

 

BBAAAAAAAAAABB일 때, A의 시작 index = 2, 연속된 A의 종료 index = 12가 된다.

 

시작 index를 기준으로, A 이전까지 갔다가 다시 돌아가기 위해서 ( index-1 )*2로 계산해주었다.

 

이제 뒤로 돌아가면서 끝에서부터 12번째 index까지는 이동을 해줘야 하므로 ( 전체 길이 - 종료 index )로 계산해주었다.

 

( * 추가한코드는 아래에 solution2로 추가하였다 ! )

 

아래 풀 때도.. 나름 잘 풀었다고 생각했는데 훨씬 훨씬 간단하게 풀 수 있었다 ㅠㅠ

 

과거 풀었던걸 다시 풀어보는 것도 상당히 중요한 공부가 되는 것 같다....

 

최초 풀이

1. 첫 번째로 조이스틱이 [ 위, 아래 ]로 움직이는 경우를 계산해 주었다.

 

영어 대문자의 ASCII코드 번호는 65~90까지이다.

 

위의 표를 참조해보면 알 수 있듯이, 'M'까지는 우측으로 이동( > )하는 것이 유리하다. ( A = 0번 이동, M = 12번 이동 )

'N'까지는 좌측으로 이동( < )하는 것이 유리하다. ( Z = 1번 이동, ~ N = 13번 이동 )

 

* 알파벳 O를 보았을 때 우측으로 이동하면 14번 이동해야 된다. 그러나 좌측부터 이동하면 12번만 이동해도 된다.

 

그리고 A의 경우는 Default값이기 때문에 [ 위, 아래 ]로 움직이는 경우는 없다.

 

결과적으로, [ 위, 아래 ]로 조이스틱을 움직이는 경우는 아래와 같이 표현해주었다.

		for ( int i = 0 ; i< names.length; i++ ) {
			if ( names[i] < 78 ) {// A~M까지 
				answer += names[i]%65;
			}else { // N~Z
				answer += 91-names[i];
			}
		}

 

2. 두 번째로 조이스틱이 [ 좌, 우 ]로 움직이는 경우를 계산해 주었다.

 

좌, 우로 움직일 때 최소 단위를 구하기 위해서 3가지 경우를 고려하였다.

 

2-1 ) 처음부터 우측으로 쭉 가는 경우

ex) "JEROEN" 같이 입력하고자 하면 무조건 우측 이동할 수밖에 없다. 좌측으로 이동을 해도 되지만 결과는 같다.

=> 이 경우는 전체 글자의 길이-1 해주면 된다.

 

2-2) 뒤부터 가는 경우

ex) "JAN" , "JAAAAAAIN"

 

"JAAAAAAIN"을보자. 이 경우 우측으로 이동하면 오른쪽으로 최대 8번을 이동한다.

이 경우 좌측으로 이동하면 J -> N -> I 만 이동을 해서 각 알파벳들을 [ 위, 아래 ] 조작만 해주면 끝이 난다.

 

이 경우는 시작할 때 JAAAAAAIN으로 이동하기 때문에 기본 moveCnt = 1로 주었다.

그리고 좌로 갈 수 있는 최소 값은 A가 아닌 값이 마지막으로 나오는 경우이다.

 

예를 들면 우 -> 좌로 이동하고 있을 때, JABAAIN이라고 하면 A가 아닌 수 B까지는 무조건 가서 [ 위, 아래 ] 조작이 이루어져야 한다.

 

결과적으로, 뒤부터 가는 경우의 코드는 아래와 같이 표현해주었다.

			// 뒤부터 세는경우 , 1번째부터 'A'가 아닌게 나올때까지는 무조건 움직여 주어야 한다. 
			for ( int i = 1 ;  i < names.length; i++ ) {
				if ( names[i] != 'A' ) {
					moveCnt = names.length-i;
					break;
				}
			}

 

2-3) 중간에 멈추고 돌아가서 계산하는 경우

ex) "BBAAAAABA"

 

이 경우 가장적은 조작으로 갈 수 있는 경로는 BBAAAAABA -> BBAAAAABA-> BBAAAAABA -> BBAAAAABA로 두 번째 인덱스까지 가서 B를 만들어주고 뒤로 돌아가서 마지막 B를 만들어주면 [ 좌, 우 ] 이동은 4번만 하면 된다.

 

내가 생각해낸 방법은.. 주어진 name에서 A가 연속으로 나열된 경우가 존재할 때, A가 시작되기 전까지 갔다가 , 다시 돌아가서 , A가 끝나는 지점까지 가는 경우를 계산해주었다..

 

예를 들면 BBAAAAABA는 A가 연속으로 나열된 경우가 존재하고 BBAAAAABA 붉은색 표시한 부분이 된다.

이때 붉은색이 시작되는 INDEX번호 2와 ( BBAAAAABA ) 끝나는 INDEX 6을 기록한다. ( BBAAAAABA )

즉, 2번째 INDEX전까지 갔다가 6번째 다음 INDEX까지만 이동하면 된다.

 

A의 시작점 앞에 존재하는 INDEX들은 BBAAAAABA -> BBAAAAABA 처럼 갔던 길을 다시 되돌아와야 한다.

 

즉, INDEX * 2 만큼 이동을 하게 된다. 만약 5번째 INDEX까지 갔다가 돌아가면 총 10번을 이동하게 된다.

 

그리고 A의 마지막 INDEX 이후까지가 종료 시점이 되고, 이때의 이동거리는 [ ( NAME의 길이 -1) - 마지막 인덱스 ]를 해서 구해주면 된다.

 

여기서 한 가지 고려해야 할 점은 BBBBAAAAA처럼 연속된 A의 마지막 INDEX가 글자의 끝에 존재하는 경우이다.

 

이때는 BBBB까지만 가면 됨으로 A시작점-1의 INDEX만큼만 더해주면 된다.

			while ( i < names.length ) {
				
				int endIndex = 0 ;
				
				if ( names[i] == 'A' ) {
					
					endIndex = i + 1 ;
					
					while ( endIndex < names.length && names[endIndex] == 'A' ) {
						endIndex++;
					}
					
					// 연속된 A의 끝이 마지막 까지 이어진 경우라면 
					if ( endIndex == names.length ) {
						moveCnt = i-1 ;
					}else 
                    	moveCnt = 1 + (i-1)*2 + names.length-1-endIndex;
                    if (moveCnt < 0)
                    	continue;
					if ( moveCnt < min )
                    	min = moveCnt ;
					i = endIndex+1;					
				}else i++;
			}

전체 코드

package Programmers.Level2;

public class JoyStick {

	public static void main(String[] args) {

		String number ="JEROEN";

		int answer = solution2( number );

		System.out.println(answer);

	}//main

	public static int solution(String name) {

		int answer = 0;

		char[] names = name.toCharArray();
		
		// 위,아래로 알파벳을 움직여주는 경우.명확하다.
		for ( int i = 0 ; i< names.length; i++ ) {
			if ( names[i] < 78 ) {// A~M까지 
				answer += names[i]%65;
			}else { // N~Z
				answer += 91-names[i];
			}
		}

		// 좌->우 끝까지 조이스틱을 이동한 경우.
		int min = name.length()-1 ;

		// 좌,우 움직이는 경우
		if ( name.contains("A") ) {

			int moveCnt = 1 ;
			
			// 뒤부터 세는경우 , 1번째부터 'A'가 아닌게 나올때까지는 무조건 움직여 주어야 한다. 
			for ( int i = 1 ;  i < names.length; i++ ) {
				if ( names[i] != 'A' ) {
					moveCnt = names.length-i;
					break;
				}
			}
			System.out.println(" 뒤부터 : " +moveCnt);
			
			if ( min > moveCnt ) min = moveCnt ;
			int i = 0 ;
			
			while ( i < names.length ) {
				
				int endIndex = 0 ;
				
				if ( names[i] == 'A' ) {
					
					endIndex = i + 1 ;
					
					while ( endIndex < names.length && names[endIndex] == 'A' ) {
						endIndex++;
					}
					
					// 연속된 A의 끝이 마지막 까지 이어진 경우라면 
					if ( endIndex == names.length ) {
						moveCnt = i-1 ;
					}else moveCnt = 1 + (i-1)*2 + names.length-1-endIndex;
					
					if ( moveCnt < min ) min = moveCnt ;
					
					i = endIndex+1;
					
				}else i++;
			}
			
			System.out.println(" 돌아와서 : " + moveCnt);
			
			if ( min > moveCnt ) min = moveCnt ;
		}

		return answer+min;
	}
	
	public static int solution2(String name) {
		int answer = 0 ;
		
		// 위,아래로 알파벳을 움직여주는 경우.명확하다.
		for ( char c : name.toCharArray()) {
			if( c < 78 ) answer+=c%65;
			else answer+=91-c;
		}
		
		// 좌,우의 최소는 문자열 시작부터 끝가지 가는경우이다.
		int min = name.length()-1;
		
		// A가 연속되는 경우에는 뒤로돌아갔을때 최솟값을 구해주어서 비교해준다.
		for ( int i = 0; i < name.length(); i ++ ) {
			int index = i;
			
			if( name.charAt(index)=='A' ) {
				while( index < name.length() && name.charAt(index)=='A') {
					index++;
				}
				
				// 종료시점의 index는 연속된 A가 끝나는지점이다.
				
				// ((i-1)*2)은  A가 가기전까지 갔다가, 다시 Back하는 수를 세준것이다.
				// 연속된 A가 끝나는 index까지 뒤에서 세야함으로 ( 전체길이 - index )를 해준다.
				int moveCnt = ((i-1)*2) + name.length() - index;
				min = Math.min(min, moveCnt);
			}
		}
		System.out.println(" 좌,우 이동거리 : " + min );
		return answer+min;
	}

}//class

제출 결과

후기

아직 조이스틱 문제는 Programmers에서 채점할 때의 테스트 케이스가 부족한 것 같다.

 

AABAAAAAAABBB 의경우에 11이 답이지만, 14로 출력되는 코드로도 100점으로 채점이 되었다..

 

그래서 제 코드도 완전하지 않을 수 있으니.. 반례가 있으면 지적해주시면 수정하겠습니다.