[Lv2] 조이스틱

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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

문제 원출처: https://commissies.ch.tudelft.nl/chipcie/archief/2010/nwerc/nwerc2010.pdf

 

---

왼쪽 끝에서 ←로 오른쪽 끝으로 갈 수도 있고, 오른쪽 끝에서 →로 왼쪽 끝으로 갈 수도 있습니다.

 

이 문제는 의외로 더러운 부분이 있습니다.

 

 

왔다갔다하는건 동선 낭비다? 시작점에서 오른쪽으로만 간 결과와 왼쪽키로 넘어가서 왼쪽으로만 간 결과만 본다?

 

AAZAAAAAAAAAAAAAAAAAAAZAAA 일 경우,

 

오른쪽으로만 가면 24번의 조작, 왼쪽으로만 가면 26번의 조작, (문제에서 총 길이는 20자 이하이지만)

 

섞어서 왔다갔다하면 10번의 조작으로, 결국 섞는 결과를 고려해야 합니다.

 

하지만 무턱대고 현재칸에서 왼,오에 대한 다중호출함수면 StackOverFlow 예외가 발생합니다.(메모리 부족)

 

왼쪽이든 오른쪽이든 딱 바꿀 문자열 칸으로 순간이동하는 이동만 생각해봅니다.

 

 

그러면 이 이동을 둘 중 가까운 것 하나만 해도 되는지 볼까요.

 

처음 칸에서 오른쪽키만 눌러서 바꿀 문자를 만나는 것이 빠른지, 왼쪽키만 눌러서 바꿀 문자를 만나는 것이 빠른지 봐야합니다.

 

그런데 AZAAZAAZAAAAAAAAVAAAZAAZAAZ 일 경우,

 

초반에는 1칸 / 1칸으로 같고, 그 다음도 2칸 / 2칸으로 같고, 그 다음도 2칸 / 2칸, .. 그러다가 9칸 / 4칸으로 차이가 납니다.

 

AZAAZAAZAAAAAAAAVAAAZAAZAAZA 일 경우,

 

처음에 오른쪽으로 1칸 움직이는게 왼쪽키로 넘어가서 2칸 움직이는 것보다 효율적일 것 같지만,

 

위에서 보다시피 결국은 아니게 됩니다.(1칸 줄이려다 4칸 손해봄..)

 

다음 번의 판단만으로 전체를 판단하기는 어렵다는 거죠.

 

 

이번 문제는 효율성도 측정하지 않고, 주어지는 문자도 20자 이하입니다.

 

다중호출함수 사용 + 왼,오 바꾸는 위치로만 2경우 모두 판단 정도로만 해도 20자면 될 것 같습니다.

class Solution {
	int min;
	
	public void move(char[] rests, int index, int sum, int[] updown) {
		char[] newrests = rests;
		if(rests[index]!='A') {
			sum+=updown[rests[index]-'A'];
			newrests = rests.clone();
			newrests[index]='A';
		}
		boolean isAllA = true;
		for(int i=0;i<newrests.length;i++) {
			if(newrests[i]!='A') {
				isAllA = false;
				break;
			}
		}
		if(isAllA) {
			if(sum<min) min=sum;
		}
		else {
			int leftNotA = -1;
			int rightNotA = -1;
			int rightMove = -1;
			int leftMove = -1;
			if(index<rests.length-1) {
				int tmpmove = 0;
				for(int i=index+1;i<rests.length;i++) {
					tmpmove++;
					if(rests[i]!='A') {
						rightNotA = i;
						break;
					}
				}
				if(rightNotA==-1) {
					tmpmove++;
					for(int i=0;i<index;i++) {
						if(rests[i]!='A') {
							rightNotA = i;
							break;
						}
						tmpmove++;
					}
				}
				if(rightNotA!=-1) rightMove = tmpmove;
			} else {
				int tmpmove = 1;
				for(int i=0;i<index;i++) {
					if(rests[i]!='A') {
						rightNotA = i;
						break;
					}
					tmpmove++;
				}
				if(rightNotA!=-1) rightMove = tmpmove;
			}
			if(index>0) {
				int tmpmove = 0;
				for(int i=index-1;i>=0;i--) {
					tmpmove++;
					if(rests[i]!='A') {
						leftNotA = i;
						break;
					}
				}
				if(leftNotA==-1) {
					tmpmove++;
					for(int i=rests.length-1;i>index;i--) {
						if(rests[i]!='A') {
							leftNotA = i;
							break;
						}
						tmpmove++;
					}
				}
				if(leftNotA!=-1) leftMove = tmpmove;
			} else {
				int tmpmove = 1;
				for(int i=rests.length-1;i>index;i--) {
					if(rests[i]!='A') {
						leftNotA = i;
						break;
					}
					tmpmove++;
				}
				if(leftNotA!=-1) leftMove = tmpmove;
			}
			move(newrests, rightNotA, sum+rightMove, updown);
			move(newrests, leftNotA, sum+leftMove, updown);
		}
	}
	
	public int solution(String name) {
		char[] rests = name.toCharArray();
		int[] updown = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1};
		min = Integer.MAX_VALUE;
		move(rests, 0, 0, updown);
		return min;
    }
}

move 함수에서, 문자열이 모두 A면 끝나지만, 아닐 경우 아래로 이어집니다.

 

양끝에서 넘을 수 있기 때문에, 조금 복잡하지만..

 

오른쪽으로 가는 수를 셀 때,

오른쪽 끝이 아니면 - 오른쪽으로 가보고, 넘어서 돌아오고

오른쪽 끝이면 - 넘어서 돌아오고

 

왼쪽으로 가는 수를 셀 때,

왼쪽 끝이 아니면 - 왼쪽으로 가보고, 넘어서 돌아오고

왼쪽 끝이면 - 넘어서 돌아오고

 

20자 제한이 없다면, 아마 메모리 초과가 날 겁니다. 

 

문제는 쉬운데 상황이 까다로운 것 뿐이니 풀이는 여기까지..