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

문제내용

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

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

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

---

문제 접근 방법

조이스틱을 움직이는 방법은 상하좌우로 4가지 경우이다. 어디로 움직이든 한번 움직일때마다 1의 기회비용이 발생한다. 이때 기회비용을 최솟값으로 갖기 위해선 어떻게 해야할지 생각을 했는데... 솔직히 내가 풀긴했는데 풀고나서 다른블로그 글을 보니 복잡하게 풀었다는걸 알았다. 그래도 한번 말해보려한다.

 

우선 조이스틱을 상하로 움직이는 경우.

A에서 시작해 스틱을 위로 올리는 경우 int up = Math.abs('A'-'문자');

A에서 시작해 스틱을 아래로 내리는 경우 int down = Math.abs('Z'-'문자)+1; 를 이용해

위아래로 움직였을때 최소 = Math.min(up, down)를 통해 최소 비용을 구한다.

(참고로 나는 Math.min(up,down)+1을 했고 +1을 한 이유는 전칸에서 지금칸으로 이동한 비용을 더해준것.)

 

두번째 조이스틱을 좌우로 움직이는 경우.

첫 기준으로 A가 2번째 위치에 있는지 없는지에 대해 생각했다.

• 2번째에 A가 위치하고 있다면 일반적으로 좌로 이동이 최소비용이됨.
• 아니라면 우로 이동이 최소 비용이됨.

첫 기준만 만족하게 된다면 'ABAAAAABA' , 'AABAAAABA' 같은 입력값에 예외가 발생한다. 따라서 시작은 첫 기준을 이용해 시작을 하지만 다음과 같은 조건을 추가해줘야한다.

• 전체 A의 개수를 Acnt , 중간에 있는 A의 개수를 temp라고 할때 Acnt-temp<temp 일 경우 움직이던 방향의 반대로 움직이는게 최소비용이 된다는 조건.
• 'ABAAAABA' 의경우 B와 B사이에 있는 A의 개수 temp=4개이고 temp를 제외한 나머지 A의 개수는 2개이다. 따라서 A를 이동할때 드는 기회비용을 최대한으로 줄이기 위해선 'A' 4개를 건너는 것보다 'A' 2개를 건너는게 유리하다.
• 단, Acnt와 temp의 값이 같지않을때만 적용 돼야한다.

 

위의 경우들을 생각하며 풀었는데... 흠.. 일단 돌려보면 문제는 풀렸다고 나오긴한다.

근데 이게 그리디 알고리즘이 맞는지도 의문이다...

일단보자.

 

---

풀이

package org.greedy.lv2;

public class joyStick {
	public static int solution(String name) {
		int answer = 0;
		int temp = 0;//전체 A카운트 변수
		for(int i=0; i<name.length(); i++) {//A전부 A일경우 0반환.
			if(name.charAt(i)=='A') {
				temp++;
				if(temp==name.length()) {return 0;}
			}
		}
		//2번째가 A일때와 아닐때로.(좌우)
		if(name.charAt(1)=='A') {
			//2번째 A면 왼쪽으로 이동.
			answer = leftCnt(name, temp, 2);
		}else {
			//아니면 오른쪽으로 이동.
			answer = rigthCnt(name, temp, name.length());
		}
		return answer-1;
	}
	
	//좌로 이동할때 함수
	public static int leftCnt(String name, int Acnt, int idx) {
		int cnt = 0;//좌로 이동시 조이스틱 사용횟수 cnt
		int temp = 0;//임시 A카운트
		int up = 0;//조이스틱 위로 조작 카운트
		int down = 0;//조이스틱 아래로 조작 카운트
		//시작부터 좌로가면 끝에서 부터시작.
		for(int i=name.length()-1; i>=idx; i--) {
			char ch = name.charAt(i);
			if(ch=='A') {//i번째에서 A가 나왔을때
				temp = 0;
				//중간에 다른알파벳 안나올때까지 i~2번 인덱스 사이에 있는 A개수세기
				for(int j=i; j>=2; j--) {
					if(name.charAt(j) == 'A') {temp++;}
					else {break;}
				}
				if(temp == i-1) {break;}//앞으로 탐색해야 할것들이 전부 A일땐 움직일 필요 없음.
				
				/* else if에서는 전체 A개수랑 i~2번사이에 A개수를 비교하여
				 * Acnt-temp < temp 일 경우엔 사이에 있는 A갯수가 더 많아서
				 * 이동할때 반대로 이동해주는게 더 최소비용이 듦.
				 */
				else if(temp!=Acnt && temp > Acnt-temp) {
					//반대로 쭉이동하면서 카운트해주고 끝내기.
					//+1은 끝에서 첨으로 이동하는 비용을 더한거.
					cnt += rigthCnt(name, Acnt, name.length()-i)+1;
					break;
				}
				//위에 모든 조건아닐땐 한칸 좌로 이동하면서 cnt+1
				else {cnt += 1;}
				
			}else {//i번째에서 A가 아닐땐 그냥 바로 조이스틱 위아래 조작하면됨.
				//그리고 그중에서 최솟값+한칸이동 을 해주면됨.
				up = Math.abs('A' - ch);
				down = Math.abs('Z' - ch) + 1;
				cnt += Math.min(up, down)+1;
				
			}
		}
		//좌로이동시엔 첫번째꺼 탐색안하고 넘어가니까 for문 끝나면 해주기.
		up = Math.abs('A' - name.charAt(0));
		down = Math.abs('Z' - name.charAt(0)) + 1;
		cnt += Math.min(up, down)+1;
		
		return cnt;
	}
	
	//우로 이동할때 함수
	//좌로 이동할때랑 원리는 비슷하고 좌를 이해하면 우로 이동은 더쉬움.
	public static int rigthCnt(String name, int Acnt, int idx) {
		int cnt=0;
		int temp = 0;
		int up = 0;
		int down = 0;
		for(int i=0; i<idx; i++) {
			char ch = name.charAt(i);
			if(ch == 'A') {//A일떄
				temp = 0;
				for(int j=i; j<name.length(); j++) {
					if(name.charAt(j)=='A') {temp++;}
					else{break;}
				}
				if(temp == name.length()-i) {break;}
				else if(temp!=Acnt && temp>Acnt-temp) {
					cnt += leftCnt(name, Acnt ,i);
					break;
				}
				else {cnt += 1;}
			}else {//아닐때
				up = Math.abs('A' - ch);
				down = Math.abs('Z' - ch) + 1;
				cnt += Math.min(up, down)+1;
			}
		}
		return cnt;
	}
}

 

---

마치며

다른 블로그보면 풀이방식이 엄청 간단하던데,,, 한번 참고해봐야겠다.