[고득점Kit][그리디] 조이스틱 ⭐⭐

[그리디] 조이스틱

난이도 ⭐⭐

문제

내 풀이 ⭕

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

int solution(string name) {
    
    int answer = 0;

    unordered_map<char, int> alphabet;
    for(int i = 0; i < 13; i++)  
        alphabet['A' + i] = i;   
    for(int i = 13; i < 26; i++)
        alphabet['A' + i] = 26 - i;
    
    
    int left = 0;
    int right = 0;
    int index = 0;
    
    while(true)
    {
        answer += alphabet[name[index]];
        name[index] = 'A';
        
        for (int i = index + 1, count = 1; count < name.length(); i++, count++)
        { 
            if (i >= name.length())
                i = 0;
            if (name[i] != 'A')
            {
                right = count;
                break;
            }
        }
        
        for (int i = index - 1, count = 1; count < name.length(); i--, count++)
        { 
            if (i < 0)
                i = name.length() - 1;
            if (name[i] != 'A')
            {
                left = count;
                break;
            }
        }
        
        if (left < right)
        {
            answer += left;
            index = index - left;
            if (index < 0)
                index += name.length();
        }
        else
        {
            answer += right;
            index = index + right;
            if (index > name.length())
                index -= name.length();
        }
        
        if (right == 0 || left == 0)
            break;
        
        right = 0;
        left = 0;
    }
    
    return answer;
}

• 초기값은 AAAA... 로 시작되므로 A를 기준으로 했을 때, 알파벳 26개 중 A ~ M 까지는 🔻방향으로 A부터 찾는게 더 빠르고 N ~ Z 까지는 🔺방향으로 Z부터 찾는게 더 빠르다. 따라서 map을 사용하여 A ~ M Key 값은 0, 1, 2, ..., 13 의 Value를 부여하고 N ~ Z Key 값은 13, 12, 11, ..., 0 의 Value를 부여하였다. 추후 이 map은 해당 알파벳으로 접근하면 A를 해당 알파벳으로 바꾸기 위해선 🔺혹은 🔻 방향으로 조이스틱을 얼마나 움직여야 하는지 알 수 있다.

  unordered_map<char, int> alphabet;
  for(int i = 0; i < 13; i++)  
      alphabet['A' + i] = i;   
  for(int i = 13; i < 26; i++)
      alphabet['A' + i] = 26 - i;
  

• 최소한의 조이스틱 조작으로 다음 알파벳으로 설정하기 위해 left와 right을 비교하여 더 작은 방향의 다음 알파벳으로 향할 것이다. 그리고 그에 따라 index를 업데이트 할 것이다.

    int left = 0;   // 현재 `name`을 가리키고 있는 위치
    int right = 0;  // `index`로부터 왼쪽 방향으로 `A`가 아닌 알파벳까지의 거리
    int index = 0;  // `index`로부터 오른쪽 방향으로 `A`가 아닌 알파벳까지의 거리
  

• while 반복문 👉 1️⃣ name 각각의 문자들을 A로부터 설정하는데 소요된 조작 횟수, 2️⃣ 문자간의 최소 이동 횟수 를 연산하여 최종적인 answer를 도출한다. 1️⃣ 2️⃣ 연산 횟수 계산이 완료된 문자는 A로 바꾼다. `name`의 모든 문자가 `A`가 되면 모든 문자의 연산횟수를 다 계산한 것이 되므로 종료한다.
  • 1️⃣ name 각각의 문자들을 A로부터 설정하는데(위아래 방향) 소요된 조작 횟수

    answer += alphabet[name[index]];  // answer에 필요한 조작 횟수를 더해준 후
    name[index] = 'A';  // 'A'로 바꿔준다.
    

  • 2️⃣ 문자간(오른쪽 왼쪽 방향)의 최소 이동 횟수
    • (1) right 구하기
      • index + 1부터 오른쪽 방향으로 순회하여 처음으로 A가 아닌 문자를 만나게 될 때까지의 거리. count로 이동 거리를 세는데 이때의 거리는 count이므로 right = count하고 그만 순회하고 빠져나오면 된다.
      • 오른쪽으로 계속 가다가 인덱스가 name.length()를 넘어버리면 i = 0으로 바꿔준다.
      • A가 아닌 문자를 한번도 만나지 못하면 count는 name.length()에 도달하여 for문이 종료되고 right은 0인 상태로 유지된다.

          for (int i = index + 1, count = 1; count < name.length(); i++, count++)
          { 
              if (i >= name.length())
                  i = 0;
              if (name[i] != 'A')
              {
                  right = count;
                  break;
              }
          }
        

    • (2) left 구하기
      • index - 1부터 왼쪽 방향으로 순회하여 처음으로 A가 아닌 문자를 만나게 될 때까지의 거리. count로 이동 거리를 세는데 이때의 거리는 count이므로 left = count하고 그만 순회하고 빠져나오면 된다.
      • 왼쪽으로 계속 가다가 인덱스가 0를 넘어 음수가 되버리면 최대 인덱스인 i = name.length() - 1으로 바꿔준다.
      • A가 아닌 문자를 한번도 만나지 못하면 count는 name.length()에 도달하여 for문이 종료되고 left은 0인 상태로 유지된다.

        for (int i = index - 1, count = 1; count < name.length(); i--, count++)
        { 
            if (i < 0)
                i = name.length() - 1;
            if (name[i] != 'A')
            {
                left = count;
                break;
            }
        }
        

    • (3) right과 left 중 최소 거리인 방향으로 선택
      • left가 더 작다면
        • left는 현재 위치에서 A가 아닌 설정이 필요한 다음 알파벳으로 가기 위한 최소 이동 거리가 되므로 answer에 더해준다.
        • A가 아닌 설정이 필요한 다음 알파벳은 현재 인덱스에서 left만큼 빼주면 되는 곳에 있다.
          • 만약 인덱스가 left를 빼고 음수가 되어 버렸다면 name.length()를 더하여 보정
      • right가 더 작다면
        • right는 현재 위치에서 A가 아닌 설정이 필요한 다음 알파벳으로 가기 위한 최소 이동 거리가 되므로 answer에 더해준다.
        • A가 아닌 설정이 필요한 다음 알파벳은 현재 인덱스에서 rightt만큼 더해주면 되는 곳에 있다.
          • 만약 인덱스가 right를 더해주고 name.length()을 넘어 버렸다면 name.length()를 빼주어 보정
  • 이제 name이 모두 A가 되버려서 더 이상 설정할 글자가 없다면 right = 0 & left = 0 상태가 된다. 이때 무한 루프문을 빠져나와 종료한다.
  • 아직 설정할 글자가 남아있다면, 즉 break되지 않았다면 다시 right과 left를 0 으로 꼭 초기화 해준다.
    • 이부분을 생략하면 무한루프에 빠져버린다..

이 문제로 알게된 소소한 사실

int a = 0, int b = 0;  // ❌ 에러
int a = 0, b = 0;      // ⭕

int a = 0; int b = 0;  // ⭕

int a = 0, float b = 0; // ❌ 에러

• 선언할 땐 ;로 구분해야 한다.
• 단, 같은 타입일 땐 ,로 구분하여 같은 타입의 변수를 또 선언한다는 것을 나타낸다.
• 처음엔 아래와 같이 for문의 초기식을 설정했어서.. 왜 오류가 나는지 몰라 당황했었다. for문은 ;로 초기식, 반복식, 증감식을 구분하기 때문에 ,로 구분해 여러 초기식을 구분해주어야 했다. (그럴려면 또 같은 데이터 타입이어야겠죠!) int = index + 1, int count = 1가 아닌 int = index + 1, count = 1로 정정해주었다.

  for (int i = index + 1, count = 1; count < name.length(); i++, count++)
  

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기