C# - 조이스틱
https://school.programmers.co.kr/learn/courses/30/lessons/42860
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
해당 문서는 PC에서 작성되었으므로 모바일 환경에서는 줄이 잘 맞지 않을 수 있습니다.
이 문제를 둘로 나눠서 생각해봅시다
/* 1. 좌우 조작
* 0번째(가장 왼쪽) 문자부터 시작
* 0번째 문자에서 왼쪽으로 조작하면 마지막 문자로 커서 이동, 역도 성립
* 옆 글자로 넘어갈 때 조이스틱 1번씩 조작
*
* 문자 'A'가 있을 때 최소 좌우 조작 횟수에 변동이 있는 경우가 생김 -> 규칙을 알아내자
* 앞으로 문자열 중 'A'가 하나 이상 연달아 나올 때 이를 A 묶음으로 정의한다.
* (A 가 아닌 문자 or 문자열 끝) + 'A' 묶음 + (A가 아닌 문자 or 문자열 끝) ......
*
* 최소 조작 횟수를 구하기 위해 모든 이동하는 경우를 4가지로 정리하면,
* (1) 오른쪽으로만 이동
* (2) 왼쪽으로만 이동
* (3) 가장 긴 A 묶음 왼쪽의 문자까지 오른쪽으로 이동했다가,
* 반대로 조작하여 가장 긴 A 묶음 오른쪽의 문자까지 왼쪽으로 이동
* (4) 가장 긴 A 묶음 오른쪽의 문자까지 왼쪽으로 이동했다가,
* 반대로 조작하여 가장 긴 A 묶음 왼쪽의 문자까지 오른쪽으로 이동
* 결과값을 비교하여 그 중 최소를 고르면 된다.
*
* 이를 수식으로 정리하면,
* (1) 가장 마지막 문자가 A가 아닌 경우 -> 문자열 길이 -1
* 가장 마지막 문자가 A인 경우 -> 문자열 길이 -1 - 마지막 A 묶음 길이
*
* (2) 1번째 문자가 A가 아닌 경우 -> 문자열 길이 -1 (항상 (1) 이하의 값이 나오므로 계산할 필요는 없음)
* 1번째 문자가 A인 경우 -> 문자열 길이 -1 - 첫 A 묶음 길이
*
* (3), (4)에 대해,
* 1번째 ~ 마지막 문자 중 'A'가 하나도 없는 경우는 계산하지 않음
* 길이가 같은 가장 긴 A 묶음이 여럿 있으면 그 중 어떤 것을 이용하여 계산을 수행하여도 결과는 동일
*
* 0번 문자 위치(처음 위치)로부터 가장 긴 A 묶음의
* ㄴ 오른쪽의 문자까지 스틱 왼쪽 조작으로만 이동할 때 조작 횟수
* x = 가장 긴 A 묶음 시작 위치 - 1
* ㄴ 왼쪽의 문자까지 스틱 오른쪽 조작으로만 이동할 때 조작 횟수
* y = 문자열의 길이 - 가장 긴 A 묶음 시작 위치 - 가장 긴 A묶음 길이
*
* (3) 2 * x +y
* (4) 2 * y + x
* x > y 라면 (4)가, x < y 라면 (3)이 두 경우 중 최소의 조작 횟수이다.
* x = y일 경우, (3), (4) 동일
* 이를 이용하여 (3), (4) 중 작은 값 하나만 계산하게 하면 계산 횟수를 줄일 수 있다.
*
* 수식에 들어가는 변수들을 정리하면,
* 문자열의 길이
* 1번째 문자가 'A'인가? -> 이 때의 첫번째 A 묶음 길이
* 마지막 문자가 'A'인가? -> 이 때의 마지막 A 묶음 길이
* 가장 긴 A 묶음 시작 위치
* 가장 긴 A 묶음 길이
*
* 따라서, 위 7개를 알아야 해를 구할 수 있다.
*
* + 예제를 통한 수식 검증은 코드 블럭 아래를 참조
*/
/* 2. 상하 조작
*
* 알파벳은 A~Z까지 총 26자
* A부터 시작하므로
*
* 조이스틱을 위로 입력한다면 M 까지 12번 조작 -> B~M까지는 위로 조이스틱 조작
* N 은 13번 조작(중간 지점) -> 위아래 어디든 상관없이 13번
* 조이스틱을 아래로 입력한다면 O 까지 조이스틱 12번 조작 -> Z~O까지는 아래로 조이스틱 조작
*
* 아스키 코드표를 통해 문자 간에 크기 비교로 위아래 조작 판별 가능함을 알 수 있음
* 'A' = 65 ~ 'Z' = 90
* '[' = 91 이므로 아래로 조작하는 계산에 쓰겠음
*/
using System;
public class Solution
{
public int solution(string name)
{
int answer = 0;
// 입력해야 할 알파벳 문자열의 길이
int name_Length = name.Length;
// 마지막 문자의 위치
int last_word_position = name_Length - 1;
// 가장 긴 A 묶음의 시작 위치, 길이
int[] max_A_group_info = new int[2] { 0, 0 };
// 현재 체킹중인 A 묶음의 시작 위치, 길이
// -> 루프가 끝날 때는 가장 오른쪽 A 묶음의 시작 위치, 길이가 된다
// -> 따라서, 문자열 마지막에 A가 올 때 그 묶음의 길이는 자동적으로 구해진다.
int[] temp_A_group_info = new int[2] { 0, 0 };
// A그룹 체킹이 진행 중인지 여부
bool is_A_group_made_complete = true;
// 1번째 문자가 A인지 여부
bool is_1st_char_A = false;
// 1번째 A를 포함하는 A묶음의 길이
int length_of_A_group_contain_1st_position = 0;
// 마지막 문자가 A인지 여부
bool is_last_char_A = false;
// 각 글자에 대해
for (int i = 0; i < name_Length; i++)
{
// 1. 최소 좌우 조작 횟수 산출에 필요한 요소를 구함
// 해당 자리가 A일 경우
if (name[i] == 'A')
{
// 0번째 자리는 좌우 스틱 조작 계산에 영향을 미치지 않으므로 제외
if (i != 0)
{
// 문자열의 1번째 글자가 A일 경우, 체크
if (i == 1)
is_1st_char_A = true;
// 문자열의 마지막 문자가 A일 경우, 체크
if (i == last_word_position)
is_last_char_A = true;
// 새로운 A 묶음을 체킹할 수 있는 상태라면
if (is_A_group_made_complete)
{
// 해당 A 묶음의 시작점 저장
temp_A_group_info[0] = i;
// 묶음의 길이 1로 초기화
temp_A_group_info[1] = 1;
// 현재 A 묶음을 체킹하는 중임을 표시
is_A_group_made_complete = false;
}
// 현재 A 묶음을 체킹하는 중이라면
else
// 묶음의 길이 +1
temp_A_group_info[1] += 1;
}
}
// 해당 자리가 A가 아닐 경우
else
{
// 실행 중이던 A 묶음 체킹을 중단
if (!is_A_group_made_complete)
{
is_A_group_made_complete = true;
// 문자열의 1번째 글자가 A고,
// 1번째 A로 시작하는 A 묶음 체킹이 완료되었다면,
// 그 길이를 저장
if (is_1st_char_A && temp_A_group_info[0] == 1)
length_of_A_group_contain_1st_position = temp_A_group_info[1];
// 체킹 완료한 A묶음의 길이가 기존 최대 길이보다 길다면
if (temp_A_group_info[1] > max_A_group_info[1])
{
// 가장 긴 A 묶음의 시작점, 길이를 갱신
max_A_group_info[0] = temp_A_group_info[0];
max_A_group_info[1] = temp_A_group_info[1];
}
}
// 2, 상하 조작 횟수
// B ~ N일 경우
if (name[i] <= 'N')
answer += (name[i] - 'A');
// O ~ Z일 경우
else
answer += ('[' - name[i]);
}
}
// 3. 좌우 조작하는 경우의 수 4가지로 최소 조작 횟수를 산출
// 현재 산출한 좌우 조작 횟수
int temp_LR_operate = 0;
// 좌우 조작 최소 횟수
int LR_operate_min = 0;
// (1) 오른쪽으로만 조작할 때 최소 조작 횟수
// 최솟값에 (1)의 결과로 나온 값을 넣어줌
// 마지막 문자가 A인 경우, 문자열 길이 -1 - 마지막 A 묶음 길이
if (is_last_char_A)
LR_operate_min = last_word_position - temp_A_group_info[1];
// 마지막 자리가 A가 아니라면, 문자열 길이 -1
else
LR_operate_min = last_word_position;
// (2) 왼쪽만 조작할 때 최소 조작 횟수(1번째 문자가 A인 경우만 계산)
// 1번째 문자가 A인 경우, 문자열 길이 -1 - 가장 왼쪽 A 묶음의 길이
if (is_1st_char_A)
{
temp_LR_operate = last_word_position - length_of_A_group_contain_1st_position;
// 이전의 해와 비교하여 작은 해를 채택
if (LR_operate_min > temp_LR_operate)
LR_operate_min = temp_LR_operate;
}
// (3) 가장 긴 A 묶음 왼쪽의 글자까지 오른쪽으로 이동했다가
// 반대로 조작하여 가장 긴 A 묶음 오른쪽의 글자까지 왼쪽으로 이동
// (4) 가장 긴 A 묶음 오른쪽의 글자까지 왼쪽으로 이동했다가
// 반대로 조작하여 가장 긴 A 묶음 왼쪽의 글자까지 오른쪽으로 이동
// 1번째~문자열 마지막까지 A가 하나라도 있어야 (3), (4) 계산 수행
// 하나라도 A 묶음이 있을 때만,
if (max_A_group_info[0] != 0)
{
// 0번 문자 위치(처음 위치)로부터 가장 긴 A 묶음의
// 오른쪽의 문자까지 스틱 왼쪽 조작으로 이동할 때 조작 횟수
int operate_left = max_A_group_info[0] -1;
// 왼쪽의 문자까지 스틱 오른쪽 조작으로 이동할 때 조작 횟수
int operate_right = name_Length - max_A_group_info[0] - max_A_group_info[1];
// 왼쪽 조작 횟수가 오른쪽 조작 횟수 초과일 때,
if (operate_left > operate_right)
// (3)만 계산 수행
temp_LR_operate = 2 * operate_right + operate_left;
// 왼쪽 조작 횟수가 오른쪽 조작 횟수 이하일 때,
else
// (4)만 계산 수행
temp_LR_operate = 2 * operate_left + operate_right;
// 이전의 해와 비교하여 작은 해를 채택
if (LR_operate_min > temp_LR_operate)
LR_operate_min = temp_LR_operate;
}
// 상하 최소 경로에 좌우 최소 경로를 더해주면 정답!
answer += LR_operate_min;
return answer;
}
}
/* 예제를 통해 위의 수식 검증
* 1) BBBBB
* (1) 오른쪽으로 한방향 이동 = 5 -1 = 4 (답)
* (2) 왼쪽으로 한방향 이동 = 5-1 = 4 (답)
* (3),(4) 첫 문자를 제외한 나머지 글자가 모두 A 가 아니면 계산할 필요가 없다
*
* 2) ABBBB
* (1) 오른쪽으로 한방향 이동 = 5-1 = 4 (답)
* (2) 왼쪽으로 한방향 이동 = 5-1 = 4 (답)
* (3),(4) 첫 문자를 제외한 나머지 글자가 모두 A 가 아니면 계산할 필요가 없다
*
* 1), 2)의 케이스로 0번째 문자는 좌우 이동에 영향을 미치지 않음을 알 수 있다
* -> 0번째 문자가 A라도 가장 왼쪽의 A 묶음 시작 및 구성 요소로 포함시키지 않는다.
*
* 3) 1번째 문자가 'A' 인 경우 -> 첫 A 묶음이 왼쪽 이동의 끝에 위치하므로
* 그 길이만큼 (2)의 조작 횟수를 줄일 수 있다
* BABBB
* (1) 오른쪽으로 한방향 이동 = 5-1 = 4
* (2) 1번째 문자가 A인 경우, 왼쪽으로 한방향 이동 = 5 -1 -1 = 3 (답)
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 5 +1 -1 -2 = 3(답)
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2*(5-1)-1-1 = 6
*
* BAABB
* (1) 오른쪽으로 한방향 이동 = 5-1 = 4
* (2) 1번째 문자가 A인 경우, 왼쪽으로 한방향 이동 = 문자열의 길이 - 가장 긴 A 묶음의 길이 -1 = 5 -2 -1 = 2 (답)
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 5 +1 -2 -2 = 2(답)
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2*(5-2)-1-1 = 4
*
*
* 4) 마지막 문자가 'A' 인 경우 -> 마지막 A 묶음이 오른쪽 이동의 끝에 위치하므로
* 그 길이만큼 (1)의 조작 횟수를 줄일 수 있다
* BBBBA
* (1) 가장 마지막 문자가 A인 경우, 오른쪽으로 한방향 이동 = 5-1-1 = 3(답)
* (2) 왼쪽으로 한방향 이동 = 5-1 = 4
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 5 + 4 -1 -2 = 6
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2*(5-1)-4-1 = 3 (답)
*
* BBBAA
* (1) 가장 마지막 문자가 A인 경우, 오른쪽으로 한방향 이동 = 5-2-1 = 2(답)
* (2) 왼쪽으로 한방향 이동 = 5-1 = 4
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 5 + 3 -2 -2 = 4
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2*(5-2)-3-1 = 2 (답)
*
*
* 5) 1번째, 마지막 문자가 모두 'A' 가 아닌 경우, 여러 예시로 수식대로 일치함을 확인
* BBAAB
* (1) 오른쪽으로 한방향 이동 = 5 -1 = 4
* (2) 왼쪽으로 한방향 이동 = 5-1 = 4
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 5 + 2 -2 -2 = 3 (답)
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2*(5-2) -2-1 = 3 (답)
*
* 6) 1번째, 마지막 문자가 모두 A인 경우, (1), (2) 모두 계산 횟수를 줄일 수 있다
* BABBA
* (1) 가장 마지막 문자가 A인 경우, 오른쪽으로 한방향 이동 = 5 -1 -1 = 3 (답)
* (2) 1번째 문자가 A인 경우, 왼쪽으로 한방향 이동 = 5 -1 -1 = 3 (답)
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 5 + 4 -1 -2 = 6
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2* (5 -1) -4 -1 = 3(답)
*
* 7) 테스트 케이스 중 오답이 나온 것 (논리 에러 수정 완료)
* BBBBAAAABA -> 12
* 상하 조작 -> 5번
* 좌우 조작
* (1) 10-1-1 = 8번
* (2) 10-1 = 9번
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 10 + 4 - 4 -2 = 8
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1 = 2 * (10- 4)- 4-1 = 7 (답)
*
* AABAAAAAAABBB -> 11
* 상하 조작 -> 4번
* 좌우 조작
* (1) 13-1 =12
* (2) 13-1 =12
* (3) 문자열의 길이 + 가장 긴 A 묶음 시작 위치 - 가장 긴 A 묶음 길이 - 2 = 13 + 3 - 7 -2 = 7 (답)
* (4) 2*(문자열의 길이 - 가장 긴 A 묶음 길이) - 가장 긴 A 묶음 시작 위치 -1= 2 * (13 -7) - 3-1 = 8
* /