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

<질문하기>란에 질문이 많은 문제는 풀때마다 즐겁다. 이녀석은 얼마나 날 또 미쳐버리게 만들까? 다른 사람들은 또 얼마나 머리를 싸매가며 이 문제를 풀었을까? 하지만 진짜 무서운건 질문조차 없는 문제들

프로그래머스

---

이 문제는 2가지 부분으로 나눌 수 있습니다.

1. 상/하 조작을 통해 알파벳을 변경할때의 알파벳별 최적값을 찾아서 더해주기
2. 방문하지 않아도 되는(=A인) 알파벳들을 피해 얼마나 짧게 타겟 알파벳들을 순회할 수 있는지 계산

1번은 비교적 간단하며, 첫번째 반복문은 그 과정입니다.

물론 똑같은 name에 대한 반복문이기 때문에 1,2과정을 한 반복문 안에서 처리해도 되지만 직관성을 위해 나눠서 풀었습니다. name의 길이도 최대 20이라고 문제에 나와있기 때문에 크게 문제될 부분은 아니라고 생각합니다.

 

2번이 문제인데, 과정을 설명하면 아래와 같습니다.

포인트 i와 j를 매 루프마다 설정하고,

1. i 먼저 갔다가 j로 가는 거리

2. j 먼저 갔다가 i로 가는 거리

를 각각 구합니다.

0	1	2	3	4	5
J	E	A	A	R	N
i	j

길이가 6인 name[]에 이렇게 저장되있고, 현재 i,j는 아래와 같다고 할때

1번 거리는 0-> i -> 0 -> (역방향 이동) j

2번 거리는 0 -> (역방향 이동) j -> 0(정방향 이동. 이동 방향 : 1>2>3>4>5>0) -> i

이렇게 진행되고 수식으로 표현하면

1번 거리 : i + i + (name.size() - j)

2번 거리 : (name.size() - j) * 2 + i

index가 0부터 시작하기 때문에 이렇게 계산할 수 있습니다.

 

그럼 이제 j를 설정하는 방법인데요.

애초에 왜 j를 따로 설정해서 저렇게 돌리냐 하면, 1번 이상 연속하는 A가 존재하는 구간은 탐색할 필요가 없기 때문이며, i 와 j 사이에 A를 두게 되면 그 구간을 제외한 거리를 계산하게 됩니다. 따라서 i 와 j는 연속하는 A가 있을때 그 시작점과 끝점이며, 그부분을 제외한 거리를 계산하는 과정이라고 생각할 수 있습니다.

 

아래는 전체 코드입니다.

세 값의 최소값을 구하고싶을땐 간단하게 min(a, min(b,c))하면 됩니다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string name) {
    int swapp = 0;
    for(int i = 0; i < name.size(); i++) {
        int move = name[i] - 'A';
        int rmove = 'Z' - name[i]+1;
        swapp += min(move,rmove);
    }
    
    int moving = name.size();
    for(int i = 0; i < name.size(); i++) {
        int j = i+1;
        while(j < name.size() && name[j] == 'A') j++;
        
        int dir1 = i*2 + name.size()-j; //1번 거리계산
        int dir2 = (name.size()-j)*2 + i; //2번 거리계산
        moving = min(moving, min(dir1, dir2));
    }
       
    cout << "swap "<<swapp<< endl;
    cout << "mov "<<moving << endl;
       
    return swapp + moving;
}

마지막에 moving에 들어오는 값은 특정 구간을 i/j로 설정하고 탐색을 진행할때의 최소값입니다.