[프로그래머스/C++] 조이스틱

1. 문제 / 난이도 : Level 2

programmers.co.kr/learn/courses/30/lessons/42860?language=cpp

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

---

2. 풀이 및 코드

처음에는 굉장히 단순하게 오른쪽으로 이동하는 것보다 왼쪽으로 이동하는 게 적은 경우는 _A______형태로 name[1] == 'A' 일 때 뿐이라고 생각했다.

그래서 호다닥 풀어서 냈으나, 결과는 당연히 실패....

정확하게 풀기 위해서는 다음과 같은 반례를 고려해야 한다.

name = "BBBAAAB" / answer = 9
name = "ABABAAAAABA" / answer = 11

요점은 쭉 오른쪽으로 가다가 어느 순간 왼쪽으로 되돌아갈 때가 최적인 경우도 있다는 것!

결국 최적의 경우를 항상 선택해야하므로 Greedy 다.

 

(1) 초기화 및 설정

answer = 0;
int N = name.length(); // name 길이
int a_num = 'A' - '0'; // 'A'의 ASCII
string compare(N, 'A'); // 바꾸고자 하는 문자열

• a_num : 알파벳을 바꿀 때 위, 아래 버튼을 몇 번 눌러야하는지를 간편히 계산하기 위해 ASCII 코드를 이용.
  • ex ) 'A' = 48, 'B' = 49 이므로 ASCII 코드의 차를 이용해 버튼을 몇 번 눌러야하는지 계산할 수 있음.
• compare : 'A'를 N만큼 가지고 있는 문자열. 나중에 While 종료조건(compare == name)을 위해 사용.
  • ex ) name = 'JAZ'. 'compare' = 'AAA

(2) 최적 방향 찾기

int check_move(int N, int i, string name, string compare) {
	int left = 0; int right = 0; int index = 0;
	for (int j = i + 1; j < i + N; j++) { // 오른쪽으로 이동하는 경우
		if (name[j % N] != compare[j % N]) { // name과 compare가 달라질 때까지 이동
			right = j - i; // 오른쪽으로 몇 번 이동했는지
			index = j % N; // 그때의 인덱스
			break;
		}
	}

	for (int j = i - 1; j > i - N; j--) { // 왼쪽으로 이동하는 경우
		if (name[(N + j) % N] != compare[(N + j) % N]) {
			left = i - j;
			if(left < right) index = (N + j) % N; // 왼쪽으로 이동하는 경우가 더 최적이면, 해당 위치로 인덱스 갱신
			break;
		}
	}
	answer += min(left, right); // 왼쪽 이동과 오른쪽 이동 중에 더 작은 값 더하기
	return index; // 그 때의 인덱스 반환
}

• 왼쪽으로 이동하는 것과 오른쪽으로 이동하는 것 중 어느 방향으로 이동하는 것이 더 최적인지를 계산하기 위한 함수.
• 맨 끝 문자에서 +1 을 하면 맨 처음으로, 맨 처음 문자에서 -1을 하면 맨 끝으로 이동해야하기 때문에 모듈러 연산 사용.
  • ex ) N = 7, j = 8 이라면, name[j % N] = name[8 % 7] = name[1]
• 최적의 이동 수만큼 answer에 더해주고, 그 때 도착한 인덱스 반환

(3) 원하는 문자열이 될 때까지 갱신하며 반복

int i = 0;
	while (name != compare) {
		if(name[i] == compare[i]) i = check_move(N, i, name, compare); // 현재 인덱스의 name과 compare가 같으면 이동
		if (name[i] != 'A') {
			int move = (name[i] - '0') - a_num; // 얼마나 위 버튼을 눌러야 하는지
			if (move > 13) move = 26 - move; // 중간값인 13보다 크다면 아래 버튼을 누르는 게 이득
			answer += move;
			compare[i] = name[i]; // compare 갱신
		}
	}
	return answer;

---

3. 전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int answer;

int check_move(int N, int i, string name, string compare) {
	int left = 0; int right = 0; int index = 0;
	for (int j = i + 1; j < i + N; j++) {
		if (name[j % N] != compare[j % N]) {
			right = j - i;
			index = j % N;
			break;
		}
	}

	for (int j = i - 1; j > i - N; j--) {
		if (name[(N + j) % N] != compare[(N + j) % N]) {
			left = i - j;
			if(left < right) index = (N + j) % N;
			break;
		}
	}
	answer += min(left, right);
	return index;
}

int solution(string name) {
	answer = 0;
	int N = name.length();
	int a_num = 'A' - '0';
	string compare(N, 'A');

	int i = 0;
	while (name != compare) {
		if(name[i] == compare[i]) i = check_move(N, i, name, compare);
		if (name[i] != 'A') {
			int move = (name[i] - '0') - a_num;
			if (move > 13) move = 26 - move;
			answer += move;
			compare[i] = name[i];
		}
	}
	return answer;
}