[Lv.2] 조이스틱 ( 알고리즘 고득점 Kit Greedy)

조이스틱 문제

- 링크

프로그래머스

 

문제 핵심

1. 

"조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA"

 

이말인 즉, 전부 'A'부터 시작한다는 점을 알야둬야함

 

2.

"▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)"

 

처음 이것 때문에 헷갈렸는데 '◀' 와 '▶'는 문자열 인덱스를 옮기는 것임

예를 들어 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

초기 상태: [A][A][A]
                  ↑
                   커서 위치 0

상하 이동 ▲ 9번: [J][A][A]
                                ↑
                                 커서는 여전히 위치 0
좌우 이동 ◀ 1번: [J][A][A]
                                     ↑
                                      커서가 위치 2로 이동

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

라는 것이죠

 

문제풀이

public int solution(string name) 
{
    int answer = 0;
    var maxcount = name.Length;
    for(int i = 0; i < maxcount; i++)
    {
        var updowncount = name[i] - 'A';
        var downupcount = 'Z' - name[i] + 1;//+1은 A에서 왼쪽 또는 아래 버튼을 이용하여 이동하는 횟수
        answer += Math.Min(updowncount, downupcount);
    }

    return answer;
}

- updowncount는 'A'에서 부터 name[i]까지 도달하는 횟수

- downupcount는 'Z'에서 부터 name[i]까지 도달하는 횟수 'A'에서 'Z'로 이동하는 횟수 +1

*'A'는 아스키코드로 계산

 

설명

- updowncount와 downupcount중에 더 작은 횟수를 찾아서 answer에 추가

 

var mincount = maxcount - 1;//오른쪽으로 한칸씩 이동했을때 횟수
for(int i = 0; i < maxcount; i++)
{
    var updowncount = name[i] - 'A';
    var downupcount = 'Z' - name[i] + 1;//+1은 A에서 왼쪽 또는 아래 버튼을 이용하여 이동하는 횟수
    answer += Math.Min(updowncount, downupcount);

    //연속 'A'구간 넘어가기 위한 처리
    int next = i + 1;
    while(next < maxcount && name[next] == 'A')
    {
        next++;
    }

    //매 위치마다 여기서 돌아갈지를 체크
    mincount = Math.Min(mincount, i * 2 + maxcount - next);//우좌
    mincount = Math.Min(mincount, (maxcount - next) * 2 + i);//좌우
}

- 여기서 핵심은 좌우이동에 관련된 로직이라는 점입니다. 

◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

도 전부 횟수에 추가가 되기 때문에 감안하고 추가해야합니다.

 

맨처음 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

var mincount = maxcount - 1;

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

오른쪽으로 한칸씩 이동 시켰을때 총 횟수 입니다.

이것을 기반으로 여러 방법들중 제일 작은 횟수를 answer에 추가해줄 것입니다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

//연속 'A'구간 넘어가기 위한 처리
int next = i + 1;
while(next < maxcount && name[next] == 'A')
{
    next++;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

를 이용해서 'A'인 구간들은 뛰어 넘어줍니다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

//매 위치마다 여기서 돌아갈지를 체크
mincount = Math.Min(mincount, i * 2 + maxcount - next);//우좌
mincount = Math.Min(mincount, (maxcount - next) * 2 + i);//좌우

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

를 이용하여 총 두가지 방식에 대한 것을 비교 해줄 것입니다.

 

첫번째 i * 2 + maxcount - next는 

"0 → 1 → 2 → 0 → 7
(R까지 2번) + (시작으로 돌아가기 2번) + (N으로 1번) = 5번"

이러한 방식으로 오른쪽으로 갔다 왼쪽으로 돌아오는 방식입니다.

 

두번째 (maxcount - next) * 2 + i는

"0 → 7 → 0 → 1 → 2  
(N으로 1번) + (시작으로 돌아가기 1번) + (R까지 2번) = 4번"

로 왼쪽갔다가 오른쪽으로 이동하는 방식입니다.

 

이 두가지 방식을 이용해 어느구간이 제일 짧게 하는지 매번 문자열의 index위치마다 체크하여 제일 짧은 구간을 answer에 넣어주면 끝

 

최종코드

using System;

public class Solution 
{
    public int solution(string name) 
    {
        int answer = 0;
        var maxcount = name.Length;
        var mincount = maxcount - 1;//오른쪽으로 한칸씩 이동했을때 횟수
        for(int i = 0; i < maxcount; i++)
        {
            var updowncount = name[i] - 'A';
            var downupcount = 'Z' - name[i] + 1;//+1은 A에서 왼쪽 또는 아래 버튼을 이용하여 이동하는 횟수
            answer += Math.Min(updowncount, downupcount);
            
            //연속 'A'구간 넘어가기 위한 처리
            int next = i + 1;
            while(next < maxcount && name[next] == 'A')
            {
                next++;
            }
            
            //매 위치마다 여기서 돌아갈지를 체크
            mincount = Math.Min(mincount, i * 2 + maxcount - next);//우좌
            mincount = Math.Min(mincount, (maxcount - next) * 2 + i);//좌우
        }
        
        return answer + mincount;
    }
}