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

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

프로그래머스

 

[문제 요약]

• 입력으로 주어진 문자열과 길이가 같은 'A' 로 이루어진 문자열을 조이스틱 이동을 통해 주어진 문자열과 동일하게 만드는 최소 비용을 구하는 문제.
• 커서는 항상 제일 처음 문자에서 시작하며, 양 끝의 커서에서 이동은 반대 끝으로의 이동을 의미한다.

 

[풀이]

• 완전 탐색 문제로, 그리디하게 O(n^2) 풀린다.
• 풀이는 O(n)에 풀었다.
• 조이스틱 이동은 크게 2개의 분류로 나뉜다.
  • 알파벳을 변경시키는 위 아래 이동
  • 커서 위치를 이동시키는 좌 우 이동
  • 각 끝에서의 이동은 ((front or end) ± 1) % size 를 의미한다.
  • ex) "JAZ" 가 주어진 경우 "AAA" 에서 JAZ 를 만들기 위한 최소 비용은
    • "|A|AA" -> "|J|AA" 첫 문자 변경. 위로 9번
    • "|J|AA" -> "JA|A|"  중간 A는 변경하지 않아도 되므로 왼쪽으로 이동. 1번
    • "JA|A|" -> "JA|Z|" 위로 이동하는 경우 25번, 아래로 이동하는 경우 1번 이므로 최소인 아래로 1번 이동.
• 선형적인 자료구조를 생각하기 보단 사이클이 있는 원형 큐를 생각하면 좀 더 생각하기 편하다.
• 시작은 항상 index 0 부터 시작하며, 아래의 그림과 같이 시작점과 중간점의 방향과 중간점과 끝점의 방향에 따라 4가지의 경우 중 최소값을 구하면 된다.

 

• 최장길이의 A를 찾은 이후 최소로 움직일 수 있는 경우는 4가지가 있다.
  • (0, 0) : 시계 방향 시작, 시계 방향 끝 = E
  • (0, 1) :  시계 방향 시작, 반시계 방향 끝 = M * 2 + (sz - E)
  • (1, 0) :  반시계 방향 시작, 시계 방향 끝 = (sz - M) * 2 + E
  • (1, 1) :  반시계 방향 시작, 반시계 방향 끝 = sz - E

 

#include <cstdio>
#include <string>
#include <cmath>
using namespace std;

int solution(string name)
{
	int answer = 0;
	int len = name.size();
	int s = 0, e = 0, lookAheadRight = 0, lookAheadLeft = 0;
	int eNotA = 0;

	bool foundA = false;

	for (int i = 0; i < len; i++)
	{
		int val = (name[i] - 'A');
		answer += min(val, 26 - val);

		if ('A' != name[i])
		{
			eNotA = i;
		}

		if ('A' == name[i] && !foundA)
		{
			foundA = true;
			s = i;
		}

		if ('A' != name[i] && foundA)
		{
			foundA = false;
			e = i;
		}

		if ((lookAheadLeft - lookAheadRight) < (e - s))
		{
			lookAheadRight = s == 0 ? s : s - 1;
			lookAheadLeft = e;
		}
	}

	int sToE = lookAheadRight * 2 + (len - lookAheadLeft);
	int eToS = (len - lookAheadLeft) * 2 + lookAheadRight;

	if (sToE == eToS && 0 == sToE)
	{
		answer += eNotA;
	}
	else
	{
		answer += min(eNotA, min(sToE, eToS));
	}

	return answer;
}

 

[코드 설명]

• "[A]*" 를 주어진 문자열 "[A-Z]*" 로 변경하기 위해서 알파벳 변환과, 커서 이동을 분리해서 해결했다.
• k 번째의 알파벳을 이동하기 위한 최소값을 answer에 더한다.
• 최장 길이의 "A"로 이루어진 문자열을 구한다. 연속된 "A" 로 이루어진 문자열의 시작, 끝 index를 저장한다.
• 저장된 최장길이 A 문자열 앞과 뒤를 저장하여, 위 그림처럼 4개의 경우 중 최소값을 answer에 더해준다.