[프로그래머스]조이스틱(Level2)

📝문제 링크

프로그래머스 > 탐욕법 > 조이스틱 문제보기

🔑문제 KeyPoint

조이스틱과 비슷한 문제로 상,하 가까운 거리로 판단하여 출제되는 문제들이 다수 있었다.
처음에 조이스틱을 전혀 이했는데, 비슷한 문제를 한 3~4번 풀어본 뒤에서야 이해가 되었다.

➰그리디 분류에서는 알아두면 좋은 문제라고 생각한다.

상하 이동거리 / 좌우 이동거리를 분류하여 생각하자.
1. 상하 이동거리 : 현재 알파벳을 기준으로 'A'랑 가까운지 'Z'랑 가까운지 비교
2. 좌우 이동거리 : name안에 'A'가 있는지 없는지 구분하여 거리 비교
('A'를 지나간 개수와 'A'를 마주할때까지 움직인 거리를 생각하여 계산해야함.)

비교적 상하 이동거리는 쉽게 구할 수 있다.
하지만, 좌우 이동거리를 구하는 방법에 있어 조금 시간이 걸렸다.
(Level2 같지 않은 문제,,,)

💡예외케이스로 'AAAABA' 같은 경우를 생각하면 왜 좌우 이동거리를 구하는것이 중요한지 알 수 있다.

💻문제 풀이

public int solution(String name) {
	int answer = 0;
	int len = name.length();
	// 위, 아래 판단
	for(int i=0; i<len; i++) {
		char ch = name.charAt(i);

		// ( 'A' -> 'Z' 방향, 'Z' - > 'A' 역방향 중에 최소로 움직이는 방향 선택)
		int move = Math.min(ch - 'A', 'Z' - ch + 1);
		answer += move;
	}
    
	// 좌, 우 판단
	// 좌 -> 우 방향으로 이동한다 가정.
	int right_left = len - 1;

	// 우 -> 좌 방향으로 이동한다 가정.(A가 중간에 있거나, AAABA 인 경우)
	for(int i=0; i<len; i++) {
		int next = i+1;

		// A가 중간에 있는 경우
		while(next < len && name.charAt(next) == 'A'){
			next++;
		}
		// left = 우 -> 좌로 가는 거리
		// name 길이 중에 A를 지나간 갯수 : left - next
		// i만큼 왓다갓다 움직인 거리 : i *2
		int left = (i*2) + len - next;

		// 좌우 움직임중에 최소 거리를 선택
		right_left = Math.min(right_left, left);
	}

	return answer + right_left;
}

전체 소스보기(git)