[programmers] 42860번 - 조이스틱 (구현, 그리디, LEVEL.2)

1. 문제 및 예제

 

 그리디와 구현을 살짝 섞은 듯 했다. Queue를 사용하긴 했는데 차마 BFS느낌은 아니었다. 카테고리가 Greedy에 있는데 이건 어디까지나 알파벳을 바꾸는 비용을 구하는 과정이지 전체적인 정답은 BFS 혹은 구현으로 구해야한다는 생각이 든다. 이런 분류 때문에 정답률이 낮은건지...

 

 설계한 내용 그대로 한 큐에 정답이 맞아 기분이 좋았던 문제이다. 물론 풀이시간은 좀 길었다. 여러가지 예외를 생각해서 설계하느라 그런 것 같다. 어떤 사람들은 그냥 자동으로 예외처리가 된다던데... 그런 사람들이 부러울 뿐이다. ㅎㅎ

---

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

프로그래머스

---

2. 풀이과정

 

문제를 나눠보았다.

1. 기본 문자열 생성

- name 문자열의 길이만큼 "A" 문자열 생성

2. 'A'에서 목표 문자로 가는 최단거리 구하기

- 해당 부분이 그리디인듯 하다...

3. 오른쪽과 왼쪽으로 가는 길을 계산 하고 그대로 queue에 push

 

 다음은 정답 코드이다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(string name) {
    int answer = 0;
    queue<pair<int, pair<int, string>>> q;
    string str = "";

    for (int i = 0; i < name.size(); i++) {
        str += "A";
    }

    q.push(make_pair(0, make_pair(0, str)));

    while (true) {

        int index = q.front().first;
        int count = q.front().second.first;
        string name_tmp = q.front().second.second;

        q.pop();

        //해당 문자열 맞추기
        char current = name_tmp[index];
        char goal = name[index];
        int count_tmp = 0;

        if (current < goal)
            count_tmp = min(goal - current, (current - 'A') + 1 + ('Z' - goal));
        else
            count_tmp = min(current - goal, (goal - 'A') + 1 + ('Z' - current));

        name_tmp[index] = name[index];
        count += count_tmp;

        if (name_tmp == name) {
            answer = count;
            break;
        }

        //왼쪽으로 한번 가기
        if (index == 0)
            q.push(make_pair(name.size() - 1, make_pair(count + 1, name_tmp)));
        else 
            q.push(make_pair(index - 1, make_pair(count + 1, name_tmp)));

        //오른쪽으로 한번 가기
        if (index == name.size() - 1)
            q.push(make_pair(0, make_pair(count + 1, name_tmp)));
        else
            q.push(make_pair(index + 1, make_pair(count + 1, name_tmp)));

    }

    return answer;
}

 

3. 결어

 

 첫 설계로 풀기까지 약 40분 그러나 이 방법에서 오류가 나니까 바로 엄청난 시간이 들었다.. 역시 이런 복잡한 구현문제는 설계부분부터 확실하게 잡고 들어가는 것을 연습해야겠다.