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

** 시작하기에 앞서 이번 문제는 문제의 해결보단, Greedy로 오인한 저의 오답에 대한 Trouble Shooting에 가깝습니다.

 

 

조이스틱

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

프로그래머스

위 문제에 대한 해설입니다.

 

 

우선, 각 문자(' A') 를 지정한 문자로 변환하는 것은 아스키 코드로 변환하면 쉽게 횟수를 찾을 수 있습니다.

저의 경우는 각 문자에 대해 일일이 아스키값을 구해서 계산한 뒤, 변환해야하는 횟수를 구했지만,단순히

 

[1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1]  

B                                                                                    Z 

 

이런식으로 배열에 각 문자 변환 값을 넣어서 하면 더 구현시간과 효율을 단축 시켰을 것 같습니다.

 

이렇게 변환횟수를 모두 구한 뒤, 남은 문제는 몇번 이동해야 문제가 해결되는 것인가? 입니다. 

이는 문자 'A' 는 변환할 필요가 없기에 방문할 필요가 없지만, 'A' 외의 문자는 방문하여 변경해주어야 하기에,

"모든 'A'가 아닌 문자를 방문하기 위한 최소 이동 횟수" 

를 찾으면 됩니다.

 

여기서 이 문제의 허점(?) 이 나오게 됩니다.

이문제는 Greedy 알고리즘으로 분류가 되어있지만, 이 방식으로는 정답을 맞출 수 없습니다.

만약 Greedy로 해결하려면, 그 이후를 고려하지 않은 채, 당장 최소 이동횟수를 가진 Non 'A' 위치로 이동하는 것으로 답이 구해져야하지만, 다음과 같은 예시를 보면 Greedy로 이 문제를 해결할 수 없다는 것을 알 수 있습니다.

 

"CANAAAAANAN"

 

greedy를 사용한다면,     C에서 왼쪽으로 한칸 이동하여 가장 먼저 만나는 Non 'A' 값인 N을 찾을 것입니다. 

그 뒤로 쭉 Greedy의 방문 과정을 하이라이트로 표시해보겠습니다.

 

CANAAAAANAN          :왼쪽으로 1회 이동

 

CANAAAAANAN          :왼쪽으로 2회 이동

 

CANAAAAANAN           : 오른쪽으로 5회 이동

 

이렇게 총 1+2+5=8회가 소요됩니다.

 

하지만, 이것은 최소 이동 횟수가 아닙니다. 적절한 최소 이동 횟수의 flow는 아래와 같습니다.

 

CANAAAAANAN       :오른쪽으로 2회 이동

 

CANAAAAANAN       :왼쪽으로 3회 이동

 

CANAAAAANAN       : 왼쪽으로 2회 이동

 

2+3+2=7회가 최소 이동 횟수입니다.

 

따라서 이 문제는 Greedy가 아닌 완전탐색을 통해 푸는 것이 일반적인 방법입니다 ( DFS 등)

(단 완전 탐색보다 쉬운 풀이도 존재하기는 합니다)

 

Greedy 분류라는 편견에 Greedy로만 해결하려고 하여 결국 solve하지 못하였습니다.

아래는 다른 분의 정답 코드입니다.

 

#include <string>
#include <vector>

using namespace std;

int move(string name,int idx) {
	int answer;
	int l, r;
	int c_l, c_r,i_l,i_r;

	l = r = c_l = c_r = 0;
	if (name[idx] != 'A') name[idx] = 'A';
	if (name == string(name.size(), 'A')) return 0;

	for (int i = idx+1;; i++) {
		r++;
		if (i == name.size()) i = 0;
		if (name[i] != 'A') break;
	}
	i_r = r + idx > name.size() ? r+idx-name.size() : r + idx;
	for (int i = idx-1;; i--) {
		l++;
		if (i < 0) i = name.size()-1;
		if (name[i] != 'A') break;
	}
	i_l = idx - l < 0 ? idx - l + name.size() : idx - l;

	c_r += r+move(name, i_r);
	c_l += l+move(name, i_l);

	c_r > c_l ? answer = c_l : answer = c_r;

	return answer;
}

int solution(string name) {
	int answer = 0;
	int size = name.size();
	
	for (char i : name) {
		if (i != 'A') i - 65 > 12 ? answer += 26 - (i - 65) : answer += i - 65;
	}

	answer += move(name,0);

	return answer;
}
[출처] [프로그래머스/C++] 조이스틱|작성자 영꿀

 

*** 아래의 코드는 오답코드 입니다.

#include <string>
#include <vector>

#include<iostream>
using namespace std;



int count=0;
int num[21];
int cvt[21];
int solution(string name) {
    int answer = 0;
    vector<int> asky;
    int len=name.size();
    for(auto c:name){
        asky.push_back((int) c);
    }
    
    for(int i=0;i<asky.size();i++){ //각 알파벳을 변환시키는 최소 횟수
        if(asky[i]!='A'){
            cvt[i]=1;
            count++;
        }
        num[i]=asky[i]-'A'; //오른쪽으로 이동시 횟수
        if(num[i]>13) num[i]=26-num[i];//왼쪽으로 이동시 횟수. 중간을 넘어가면 왼쪽이동이 더 빠르다.
        answer+=num[i];
    }
    int left_idx=0,right_idx=0,idx=0,rmax,lmax;
    int test=0;
  //  cout<<count<<endl;
    cvt[0]=0; // ==0 : 변환 완료, 혹은 변환할 필요가 없는 것.
    count--;
    
   while(count>0){
       // cout<<"loop"<<endl;
        left_idx=idx;
        right_idx=idx;
        lmax=0;
        rmax=0;
         while(cvt[left_idx]==0){ //왼쪽이동시 가장 먼저 만나는 변환값
             left_idx--;
             if(left_idx<0) left_idx=len+left_idx; 
             lmax++;   
         }
         while(cvt[right_idx]==0){ //오른쪽이동시 가장 먼저 만나는 변환값
             right_idx++;
             right_idx%=len;
             rmax++;
         }
        if(lmax<rmax) {
            idx= left_idx;
            answer+=lmax;
            cvt[left_idx]=0;
            test+=lmax;
        }
        else{
            idx=right_idx;
            answer+=rmax;
            test+=rmax;
            cvt[right_idx]=0;
        }
        count--;
        //cout<<lmax<<" "<<rmax<<endl;
        
        
    }
    cout<<test<<endl;

    return answer;
}