프로그래머스 조이스틱

작성일 | In |

Problem : 조이스틱

유형 : 그리디

해결 전략

  • 조이스틱을 최소한 으로 움직여서 답을 찾아보아야한다.

  • 전부 다 A로 만들때 최소 움직임을 찾는다.

  • 위 아래로 움직였을 때 최선의 선택을 구한다.
    • 위로 움직였을때, 아래로 움직였을때, 언제 더 빠르게 원하는 단어를 찾는지 확인한다.
    • X를 찾는 단어라고 하자.
    • X - A 와, Z - X + 1을 비교해보고 최솟값을 찾는다.
  • 좌 우로 움직였을 때 최선의 선택을 구한다.
    • 좌 우로 움직이면서 A가 아닌것을 찾는다.
    • 위 아래로 움직였을 때 최선의 선택을 구한다.

주의할 점

  • 끝 위치 에서 우측으로 이동하는 경우는, 좌측 끝으로 가지 않는다.

풀이

초기 A값을 만든다.

  • 들어온 문자열의 길이와 동일한 연속된 A를 만든다.
  • 만약 맨 처음 위치가 A가 아니라면, 위아래로 움직였을때 최소값을 찾는다.

좌우로 움직여 본다.

  • 현재 문자열이 전부 연속된 A가 아닌경우, A가 아닌 위치를 찾는다.
  • 좌측, 우측으로 움직여본다.
  • 둘 중 적게 움직인 방향을 찾는다.
    • 우측으로 움직일 경우에는 현재 위치에 +
    • 좌측으로 움직일 경우에는 현재 위치에 - 를 해준다.
      • 음수가 되는 경우에는 문자열 길이만큼 더해주어 정상적인 인덱스를 찾도록한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

string cmp_str, name;
int answer;
int cur;

void Init() {
    for (int i = 0; i < name.size(); ++i) {
        cmp_str.push_back('A');
    }
    if (name[cur] != 'A') {
        answer += min(name[cur] - 'A', 'Z' - name[cur] + 1);
        name[cur] = 'A';
    }
}


int left_move(int cur) {
    int cnt = 0;

    while (1) {
        cur--; cnt++;
        if (cur < 0) cur += name.size();
        if (name[cur] != 'A') return cnt;
    }
}

int right_move(int cur) {
    int cnt = 0;

    for (int i = cur + 1; i < name.size(); ++i) {
        cnt++;
        if (name[i] != 'A') return cnt;
    }
    return INT_MAX;
}

int solution(string n) {
    name = n;

    int cur = 0;
    Init();

    while (cmp_str != name) {
        int left_cnt = left_move(cur);
        int right_cnt  = right_move(cur);
        
        if (left_cnt < right_cnt) {
            answer += left_cnt;
            cur -= left_cnt;
            if (cur < 0) cur += name.size();
        }
        else {
            answer += right_cnt;
            cur += right_cnt;
        }

        answer += min(name[cur] - 'A', 'Z' - name[cur] + 1);
        name[cur] = 'A';
    }

    return answer;
}

피드백

좌우측으로 이동할떄, 최소거리를 어떻게 처리할지 조금 고민했었다.