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

1. 문제 설명

 

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

프로그래머스

그리디 문제 유형인데, 그리디 유형은 다른 유형처럼 어떠한 풀이법이 정해져있는 것이 아니어서, 더 어렵게 느껴진다. 처음에 문제를 풀었을 때 자꾸 반례가 발생해서 결국 다른 사람들의 풀이법을 참고하고 다시 풀었다. 

 

2. 트러블 슈팅

처음에 내가 짠 코드는 굉장히 복잡하고 긴데, 잘못 짠 부분은 다음과 같다.

이 문제는 크게 두 가지를 고려해야 한다. (1) 방향키 위 아래 (2) 방향키 좌우

위 아래를 고려하는 것은 그리 어렵지 않다. 하지만 방향키 좌우를 결정하는 데에 어려움이 있는데, 

왜냐하면 (1) 방향기 좌로 가는 경우 (2) 방향키 우로 가는 경우 (3) 방향기 좌/우로 가던 도중 꺾어서 우/좌로 가는 경우

 

나는 (1), (2)는 고려했는데 (3)을 고려하지 못해 계속해서 반례가 발생했다.

 

또한, 나는 매번 한글자씩 좌로 한번 우로 한번 가보고 더 거리가 짧은 것을 고르는 식으로 코드를 짰다.

문제를 전체적으로 살펴보면 이렇게 복잡하게 짤 필요는 없는게, 어차피 2번 이상은 방향을 꺾지 않을 것이기 때문이다. 왜냐하면 최소로 간 경우의 수를 따지는 것인데 2번 꺾으면 제자리로 돌아가므로 비효율적인 코드가 된다. 따라서 "매번"이를 계산할 필요가 없고, 반복문을 꺾는 지점을 기준으로 해서 두고 어디서 꺾으면 가장 짧을지를 고려하면 되는 것이다. 

 

아마도 내가 매번을 고려한 이유는, 그리디 알고리즘은 매 선택에 최선을 다해야한다고 생각했기 때문이다. 오히려 유형에 머리가 묶여 제대로 생각하지 못한 것 같다.  

 

그리고 사소한 이슈가 있었는데, 변수명을 min으로 하다보니 최솟값을 뽑는 함수와 충돌이 있었다. 절대 변수명은 함수명과 같게 짜지 않도록 주의하자 ! 그리고 c++에서 3개 이상의 값을 비교하고 싶으면 () 안에 {}로 묵으면 된다. 

 

3. 문제 해결

 

(1) 조이스틱 위 아래 : 'A'를 빼준 값이 13보다 크면 26에서 뺀다. (꺼꾸로 가는 것이 더 쉬우므로) 

(2) 조이스틱 왼 오 : index를 "꺾는 위치"의 다음 위치로 초기화하고, A가 안나올때까지 앞으로 이동한다. 그리고 좌로 갔다가 오로 꺾는 경우, 오로 갔다가 좌로 꺾는경우, 일방향으로 가는 경우 세 경우의 수에서 최솟값을 구한다. 꺾는 위치를 기준으로 반복문을 돌고, 최솟값을 결과에 더해주면 된다. 

 

4. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string name) {
    int answer = 0;
    int min_num = 300;
    int index;
    int length = name.size();
    
    for (int i = 0; i < length; i++)
    {
        int updown = name[i] - 'A';
        if (updown > 13) updown = 26 - updown;
        answer += updown;
        
        index = i + 1;
        while (name[index] == 'A') index++;
        int tmp = min({length - 1, i * 2 + length - index, i + (length - index) * 2});
        if (min_num > tmp) min_num = tmp;
    }
    answer += min_num; 
    return answer;
}