[프로그래머스/C++] 조이스틱

(6/17 - X)

 

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

 

코딩테스트 연습 - 조이스틱

 

 

 

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;

    int size = name.size();
    int updown = 0, leftright = size - 1;

    vector<char> v(size);
    int i = 0;
    for (auto& s : name) {
        v[i++] = s;
    }

    // left-right
    for (int start_idx = 0; start_idx < size; start_idx++) {
        updown += min(abs('A' - v[start_idx]), abs('Z' - v[start_idx]) + 1);

		int end_idx = start_idx + 1;
		while (end_idx < size && v[end_idx] == 'A') {
			end_idx++;
		}
		leftright = min(leftright, 2 * start_idx + (size - end_idx));
		leftright = min(leftright, 2 * (size - end_idx) + start_idx);
	}

    answer = leftright + updown;
    return answer;
}

 

 

1. updown

조이스틱 상하(A-Z)로 이동하는 횟수. 아스키코드를 이용하여 'A'와 문자, 'Z'와 문자의 차이 값을 구하고, 그 중 가장 적게 움직일 수 있는 횟수를 선택한다.

2. leftright

조이스틱을 좌우로 움직이는 횟수. (여기에서 많이 애먹었다)

비교할 경우는

• 순방향으로 이동 시 : name.length() - 1
• > 방향으로 먼저 이동 후 A를 만났을 때 <로 방향 전환 : 2 * start_idx + (size - end_idx)
• < 방향으로 먼저 이동 후 A를 만났을 때 >로 방향 전환 : 2 * (size - end_idx) + start_idx

문자열 중간에 많은 수의 A가 있다면 >로 가다가 다시 유턴해서 <로 가는 방법이 더 이동 횟수가 적다. 그 반례로 'ABABAAAAAAABA'가 있다. 따라서 경우가 위처럼 세 가지.

3. answer

updown, leftright를 더해 주면 된다.

 

 

효율성

아주 미세한 차이지만, string에 직접 접근하는 방식보다 vector<char>에 name의 원소를 하나하나 넣어서 그 벡터에 접근하는 방식이 조금 더 메모리를 덜 잡아 먹는다. (테케5나 테케25에서 특히)

string 자체에 접근해서 푸는 방식

vector에 접근해서 푸는 방식

 

출처

https://inuplace.tistory.com/1091

[알고리즘 연습] 조이스틱 (프로그래머스 lv2, 스위프트)

 

이 분의 글을 보고 많은 도움을 얻었다.