조이스틱 C++(그리디, 탐욕법)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 조이스틱 | 프로그래머스

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

 

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동

 

문제!!

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한사항

name은 알파벳 대문자로만 이루어져 있습니다. name의 길이는 1 이상 20 이하입니다.

 

 

예시

name	return
"JAN"	23
"JEROEN"	56
"AABAAAAAAAB"	6
"AAAAAAAA"	0
"ABBBBAAAABAA"	14
"ABAAAAAAABA"	6
"AAB"	2
"AABAAAAAAABBB"	12
"ZZZ"	5

 

예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

---

2. 문제풀이

처음에는 엄청 고생하면서 풀었었습니다. 왼쪽이동 오른쪽이동 따로 계산했었거든요. 블로그 포스팅하려고 한번 정리하니까 깔끔하게 나왔습니다. 하나하나 풀어보겠습니다.   1. 처음 A로만 이루어진 문자열을 만듭니다. 비교를 하기 위해서 입니다. 보이는 화면이라고 지칭하겠습니다.   2. 어디가 가까운지 보기위해서는 구해야되는 값에 'A'를 빼거나 'Z' +1 에 구해야되는 값을 빼서 둘중 적은값만큼 횟수를 추가시키면 됩니다. 위나 아래로 반복문을 이용해서 하나하나 이동해볼수도 있지만 연산횟수가 늘어나므로 배제합니다. 이 문제에서는 효율성 테스트가 없지만 다른 문제에서 떨어질 수 있기 때문입니다.   3. 바꾸고 나면 바꾼후 문자열이 최종 문자열과 같은지 비교하고 같다면 리턴합니다.   4. 왼쪽과 오른쪽을 체크하면서 현재 화면에 보이는 값과('A'로 도배된 문자열) 구해야 되는값이 다르게 나오는쪽으로 이동을 시키고 이동한 횟수만큼 추가합니다.   5. 위 과정을 반복하면 문제는 끝이납니다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <string>
 
using namespace std;
 
int solution(string name) {
    int answer = 0, i = 0;
    string temp(name.length(), 'A');
    while (true) {
        temp[i] = name[i];
        name[i] - 'A' > 'Z' + 1 - name[i] ? answer += 'Z' + 1 - name[i] : answer += name[i] - 'A';
        if (temp == name)    break;
        for (int move = 1; move < name.length(); move++) {
            if (name[(i + move) % name.length()] != temp[(i + move) % name.length()]) {
                i = (i + move) % name.length();
                answer += move;
                break;
            }
            else if (name[(i + name.length() - move) % name.length()] 
                != temp[(i + name.length() - move) % name.length()]) {
                i = (i + name.length() - move) % name.length();
                answer += move;
                break;
            }
        }
    }
    return answer;
}

3.2 주석있는 코드

#include <string>
 
using namespace std;
 
int solution(string name) {
    int answer = 0, i = 0;
    //A로 구성된 화면
    string temp(name.length(), 'A');
    while (true) {
        //바꾸고 있는 화면에 반영하고
        temp[i] = name[i];
        //둘중에 적은걸로 결과에 추가하기
        name[i] - 'A' > 'Z' + 1 - name[i] ? answer += 'Z' + 1 - name[i] : answer += name[i] - 'A';
        //바꾼후 문자열이 동일하다면 계산 종료
        if (temp == name)    break;
        //왼쪽으로 갈지 오른쪽으로 갈지 계산하기 
        for (int move = 1; move < name.length(); move++) {
            //오른쪽 이동이 빠르다면 오른쪽으로 이동하고 이동횟수 반영
            if (name[(i + move) % name.length()] != temp[(i + move) % name.length()]) {
                i = (i + move) % name.length();
                answer += move;
                break;
            }
            //왼쪽으로 이동이 빠르다면 왼쪽으로 이동하고 이동횟수 반영
            else if (name[(i + name.length() - move) % name.length()] 
                != temp[(i + name.length() - move) % name.length()]) {
                i = (i + name.length() - move) % name.length();
                answer += move;
                break;
            }
        }
    }
    return answer;
}

3.3 테스트 코드 추가

 

#include <iostream>
#include <string>
 
using namespace std;
 
int solution(string name) {
    int answer = 0, i = 0;
    //A로 구성된 화면
    string temp(name.length(), 'A');
    while (true) {
        //바꾸고 있는 화면에 반영하고
        temp[i] = name[i];
        //둘중에 적은걸로 결과에 추가하기
        name[i] - 'A' > 'Z' + 1 - name[i] ? answer += 'Z' + 1 - name[i] : answer += name[i] - 'A';
        //바꾼후 문자열이 동일하다면 계산 종료
        if (temp == name)    break;
        //왼쪽으로 갈지 오른쪽으로 갈지 계산하기 
        for (int move = 1; move < name.length(); move++) {
            //오른쪽 이동이 빠르다면 오른쪽으로 이동하고 이동횟수 반영
            if (name[(i + move) % name.length()] != temp[(i + move) % name.length()]) {
                i = (i + move) % name.length();
                answer += move;
                break;
            }
            //왼쪽으로 이동이 빠르다면 왼쪽으로 이동하고 이동횟수 반영
            else if (name[(i + name.length() - move) % name.length()] 
                != temp[(i + name.length() - move) % name.length()]) {
                i = (i + name.length() - move) % name.length();
                answer += move;
                break;
            }
        }
    }
    return answer;
}
 
void print(string name, int answer) {
    int a = solution(name);
    cout << a << " ";
    if (answer == a)    cout << "정답" << endl;
    else    cout << "틀림 " << endl;
}
 
int main() {
    print("JEROEN", 56);
    print("JAN", 23);
    print("AABAAAAAAAB", 6);
    print("AAAAAAAA", 0);
    print("ABBBBAAAABAA", 14);
    print("ABAAAAAAABA", 6);
    print("AAB", 2);
    print("AABAAAAAAABBB", 12);
    print("ZZZ", 5);
    return 0;
}

---

4. 결과