(프로그래머스) 조이스틱

문제 링크

• 프로그래머스

요약

• 나중에 다시 풀어봐야됨

최종 §

결과

• 이 문제는 내탓50 + 남탓50 이다.
  • 프로그래머스에는 이 문제가 greedy로 분류되어 있는데 이게 어딜봐서 greedy야; 부분최적이 전체최적이 될것이라고 생각하면 틀린다.
  • 다만 이 문제를 보고 이 풀이를 바로 생각해낼 수 있을까? 라고 한다면, 그것도 좀 자신이 없다. 진짜 x발 됐네 그냥
• 어쨋든, 문제의 key idea는:
  • 우선 조이스틱 위아래 움직이는 횟수는 상수다. 이건 신경쓸 필요가 없다.
  • 신경써야 할 건 왼쪽/오른쪽으로 움직이는 횟순데, 이건 "AAA..." 이런식으로 'A' 가 연속된 애들을 회피했을 때 움직이는 횟수가 줄어드느냐를 봐야 한다.
• 자세한건 코드를 보면서 파악하자.

#include <string>
#include <vector>
 
using namespace std;
 
#define ABS_DIFF(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ROUND_DIFF(a, b, total) (MIN(ABS_DIFF((a), (b)), (total) - ABS_DIFF((a), (b))))
 
#define UP_DOWN(ch) (ROUND_DIFF((ch), 'A', 'Z' - 'A' + 1))
 
int solution(string name) {
	int min_left_right = name.size() - 1;
	int up_down = 0;
 
	for (int i = 0; i < name.size(); i++) {
		if (name[i] > 'A') {
			int j = i + 1;
 
			up_down += UP_DOWN(name[i]);
 
			while (j < name.size() && name[j] == 'A') {
				j++;
			}
 
			min_left_right = MIN(min_left_right, i + i + name.size() - j);
			min_left_right = MIN(min_left_right, (name.size() - j) * 2 + i);
		}
	}
 
	if (!up_down) {
		return 0;
	}
 
	return min_left_right + up_down;
}

• 우선, 오른쪽으로만 움직인다고 가정하면 총 움직이는 횟수는 전체 길이 - 1 이다. 그게 L13 이다.
• 또 다른 방법은, 중간에 'A' 연속구간을 회피하기 위해 와리가리 치는 방법이다. 아래의 두 방법이 있다.
  • 우선, 한 index i 를 잡았다고 해보자. 그리고 i 이후 'A' 가 아닌 첫 문자의 위치를 j 라고 해보자.
    • 그럼, 원점에서 오른쪽으로 i 까지 움직이고, 다시 원점으로 돌아오고, 왼쪽으로 더 가서 j 까지 가는 방법이 있다. 즉, 이때의 총 움직인 거리는 i + i + name.size() - j 이다. 이게 위 코드에서 L26 이다.
    • 그리고, 반대로 원점에서 왼쪽으로 가서 j 로 갔다가, 다시 원점으로 돌아오고, 오른쪽으로 더 가서 i 까지 가는 방법이 있다. 이때의 총 거리는 (name.size() - j) * 2 + i 이다. 이게 위 코드에서 L27 이다.
  • 이런식으로 i 를 쭉 움직이면서 최소 이동 거리를 찾으면 된다.

삽질 기록 §

결과

#include <string>
#include <vector>
 
using namespace std;
 
#define bms unsigned int
#define MAX_I32 (0x7FFFFFFF)
 
#define ABS_DIFF(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
 
#define ROUND_DIFF(a, b, total) \
	(MIN(ABS_DIFF((a), (b)), (total) - ABS_DIFF((a), (b))))
 
#define LEFT_RIGHT(name, i, cur) \
	(ROUND_DIFF((i), (cur), (name).size()))
 
#define UP_DOWN(name, i) \
	(ROUND_DIFF('A', (name)[(i)], 'Z' - 'A' + 1))
 
int solution(string name) {
	bms name_bms = 0;
	int cnt = 0, cur = 0;
 
	for (int i = 0; i < name.size(); i++) {
		if (name[i] > 'A') {
			name_bms |= (1 << i);
		}
	}
 
	while (name_bms) {
		int min = MAX_I32;
		int min_idx;
 
		for (int i = 0; i < name.size(); i++) {
			if ((name_bms >> i) & 0x1) {
				int distance = LEFT_RIGHT(name, i, cur);
				if (distance < min) {
					min = distance;
					min_idx = i;
				}
			}
		}
 
		cnt += LEFT_RIGHT(name, cur, min_idx) + UP_DOWN(name, min_idx);
		cur = min_idx;
		name_bms ^= (1 << cur);
	}
 
	return cnt;
}

• Greedy라길래 긴가민가 했지만 현재 위치에서 최소 거리에 있는 놈을 처리했는데, 틀린다.
  • 틀리는 반례는 "FDEAAD" 이다.
• 물론 지금 생각하니 틀린게 맞지만 이 문제가 greedy가 아닌건 거의 확실하다.