[알고리즘 풀이 분석] Programmers 조이스틱

nnnyeong·2021년 5월 5일

algorithm cpp programmers

알고리즘 풀이분석

목록 보기

7/101

프로그래머스 고득점 kit 중 가장 마지막까지 손 대지 않았던,, greedy,, ㅎ
출제가 비교적 많이 되는 편인데 왜 그동안 외면했는가..!

암튼 Greedy 알고리즘을 이용한 조이스틱 문제를 풀어보았다!

워낙 오랜만에 손 댄 greedy 이기도 하고, 내 풀이보다 훨씬 간결하고 직관적인 풀이가 있어 기록해본다!

프로그래머스 조이스틱 (level 2)

문제 링크

제한사항 및 입출력

나의 풀이

"AAA" -> "JAZ"
'A'로만 이루어진 문자열을 조이 스틱을 이용해 주어진 문자열 name으로 변환하기까지 조이스틱의 최소 동작 횟수를 반환하는 문제이다!

처음으로 시도했던 풀이 방식은,
문자열을 forward, backward로 탐색하고, 두가지 방식 중 이동 횟수가 적은 방식의 최소 이동 횟수를 정답으로 채택하는 방식이었다.

이와 같은 방식으로 코드를 작성했지만 마지막 test case 2가지에서 통과하지 못하였고, "ABAAAAABAB" -> 8 과 같은 경우를 고려하지 않았음을 알게 되었다.

사실상 위와 같은 풀이는 그리디를 적용 시킨 것도 아니었기에 당연한 결과였다,
'지금 최선인 선택이 추후에도 최선의 선택' 이라는 그리디의 개념을 이용했고 다음과 같이 풀어 통과하였다.

문자열 name 에서 현재 커서 위치 문자가 'A' 가 아니라면 'A'로 변환하기 위한 이동 횟수를 answer에 더하고, 해당 문자를 'A'로 변환
커서를 이동하기 현재의 위치 기준으로 forward, backward로 이동하였을 때 더 빨리 'A'가 아닌 문자를 만나는 방향을 확인
해당 방향으로 이동하여 문자 변환 반복
더이상 변환 할 문자가 없을 때 까지 진행

이 중 4번을 어떻게 구현하느냐가 (가장 큰 while문 실행 조건) 조금 고민스러웠다. 매번 모든 문자들을 탐색하는 방법은, 뭐 문자열이 길진 않지만 본능적으로 최선이 아닐 것 같았고,,

forward, backward로 변환이 필요한 문자를 탐색할 때, 모든 문자를 탐색하였을 때 변환할 문자가 없다면, 21 (문자열 최대 길이 + 1) 을 반환하고,
이를 반환 받으면 전체 while문을 종료하는 방식으로 구현하였다.

작성한 코드는 아래와 같다.

#include <iostream>
#include <string>

//프로그래머스 greedy - 조이스틱, level 2
using namespace std;

// 앞쪽으로 탐색했을 때 필요한 이동 횟수
int getMoveForward(string name, int start){
    bool exist = false;
    int move = 0, idx = start;
    int len = name.size();

    while (move < len){
        if (name[idx] != 'A'){
            exist = true;
            break;
        }else{
            idx = (idx+1) % len;
            move++;
        }
    }

    if(!exist) move = 21;
    return move;
}

// 뒤쪽으로 탐색했을 때 필요한 이동 횟수
int getMoveBackward(string name, int start){
    bool exist = false;
    int move = 0, idx = start;
    int len = name.size();

    while (move < len){
        if (name[idx] != 'A'){
            exist = true;
            break;
        }else{
            idx = (idx+len-1) % len;
            move++;
        }
    }

    if(!exist) move = 21;
    return move;
}

// 알파벳 변환 횟수 
int getCost(char from){
    int cost = 0;

    if (from <= 78){
        cost = from - 'A';
    }else{
        cost = 'Z' - from + 1;
    }

    return cost;
}

int solution(string name) {
    bool confirmed = false;
    int answer = 0;
    int at = 0, len = name.size();

    while (!confirmed){
        int cost = getCost(name[at]);
        answer += cost;
        name[at] = 'A';

        int forward = getMoveForward(name, at);
        int backward = getMoveBackward(name, at);

        if (forward != 21 && backward != 21){
            if (forward <= backward){
                answer += forward;
                at += forward;
            }else{
                answer += backward;
                at = (at+len-backward) % len;
            }
        }else{
            confirmed = true;
        }
    }

    return answer;
}