[프로그래머스 lv2] 조이스틱 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

가장 먼저, 조이스틱을 상하로 움직일 때 각 자리에서 필요한 이동 횟수를 쉽게 구할 수 있다.

조이스틱을 윗쪽으로 움직이는 방법과 아랫쪽으로 움직이는 방법 중에서 이동 횟수가 더 작은 방법을 선택하면 되기 때문에,

각각의 자리 name[i]에 대하여 min(name[i]-'A', 'Z'-name[i]+1) 을 더하면 된다.

 

문제는 조이스틱을 좌우로 움직이는 것인데, 결론부터 말하자면 연속된 'A' 구간을 찾고 해당 구간을 지나지 않는 이동 횟수 중에서 최솟값을 구하면 된다.

 

특정 인덱스 i에 대하여, i 이후로 'A'가 연속적으로 등장한 구간을 지난 포인트를 nexti라고 해보자. 

 

 

이 때, A가 연속된 구간은 지나지 않아도 됨으로 다음 두가지 이동방법이 가능하다.

 

첫번째 방법

1) 0번에서 i번까지 오른쪽으로 이동 ➡️ 

2) i번에서 0번까지 왼쪽으로 다시 이동 ⬅️

3) 0번에서 n-1번까지 왼쪽으로 이동 후 n-1번에서 nexti까지 왼쪽으로 이동 ⬅️

해당 방법으로 이동하는 경우 이동 횟수는 2*i+1+(n-1-nexti) = 2*i+(n-nexti) 가 된다.

 

두번째 방법

1) 0번에서 n-1번까지 왼쪽으로 이동 후 n-1번에서 nexti까지 이동 ⬅️

2) nexti에서 0번까지 오른쪽으로 이동 ➡️

3) 0번부터 i번까지 오른쪽으로 이동  ➡️

해당 방법으로 이동하는 경우 이동 횟수는 1+(n-1-nexti)+(n-1-nexti)+1+i = 2*(n-nexti)+i 가 된다.

 

즉, i와 nexti를 지정했을 때 가능한 이동 최소 이동횟수는 min(2*i+(n-nexti), 2*(n-nexti)+i) 이다.

0부터 n-1까지 name의 인덱스를 순회하면서 i와 nexti를 지정하고 가능한 최소 좌우 이동 횟수를 구한다.

 

이전에 구한 최소 상하 이동 횟수와 최소 좌우 이동 횟수를 더하여 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(string name) {

    int ans = 0;
    for (auto x : name) //상하이동
        ans += min(x-'A', 'Z'-x+1);

    //좌우이동
    int n = name.size();
    int mn = n-1;
    for (int i=0; i<name.size(); i++) {
        int nexti = i+1;
        while (nexti < n && name[nexti] == 'A') nexti++;
        mn = min({mn, 2*i+(n-nexti), 2*(n-nexti)+i});
    }
    ans += mn;
    return ans;
}

 

 

다른 lv2 문제들보다 어려워서 백준에 비슷한 문제가 있는지 찾아봤더니 티어가 골3 였다.

기분좋게 BOJ에도 제출해보자.

 

3663번: 고득점