[탐욕법] 조이스틱

yerin6860·2020년 9월 4일
0

프로그래머스

목록 보기
21/30

|| 문제설명 ||

  1. 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있다.

  2. 조이스틱을 각 방향으로 움직이면 아래와 같습니다.

    • ▲ : 다음 알파벳
    • ▼ : 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
    • ◀ : 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
    • ▶ : 커서를 오른쪽으로 이동
  3. 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 작성하라.

  • name : 만들고자 하는 이름
_ name : 알파벳 대문자
_ name의 길이 : 1 이상 20 이하

|| 문제해결방법 ||

  1. O(n)
각 단어와 처음 시작 'A'와 몇 단계 차이나는지 확인
'A'와 'Z'가 바로 위아래로 연결되어있으므로 알파벳 26개에 max를 빼서 어느 것(max | 26 - max)이 더 작은지 비교
각 단어의 위치를 변경해야하므로 answer에 ( name.size() - 1 )을 더함.

|| 코드 ||

[2020.09.04] 실패
#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;
    
    for(int i=0; i<name.size(); i++) {
        int max = name[i] - 'A';
        max = max < 26 - max ? max : 26 - max;
        answer += max;
    }
    answer += name.size() - 1;
    
    return answer;
}

  • 예외발견
좌, 우로 움직일때, name[i] == 'A'일 경우 오른쪽이 아닌 왼쪽으로 갈 수 있다.
ex) name = "JAZ" 인 경우 ('J' → 'A' → 'Z')이 아닌 'J'에서 'Z'로('J' → 'A') 바로 이동 할 수 있기 때문, 해당 name[i]의 이동 커서 값이 0일 때를 고려하여 왼쪽 오른쪽으로 이동하게 해야함.

[2020.09.04]
- for문이 아닌 while문으로 돌려서 넘어가기 전에 다음 값이 0인지 아닌지를 판단하여 왼쪽, 오른쪽 판별
- 중복되는 길을 만들지 않기 위하여 들른 곳은 따로 vector<bool> chk(name.size(), true); 생성하여 체크
  • 예외발견
1. 양쪽이 "A"인 경우 어느 쪽으로 시작하는게 더 효율적인지
ex) name = "SAAOA" 일경우,
	1) 0:'S' → 1:'A' → 2:'A' → 3:'O'	: 3번의 이동
	2) 0:'S' → 4:'A' → 3:'O' 		: 2번의 이동

2. name[0] == 'A'인 경우 시작 점을 어디로 설정할 것인가 시작이 무조건 0이 아니어야 함. → if(name[i] == 'A') 이면 이동 answer--를 하고 chk[i] = false; i--;
(모든 이동 다음에 다음으로 넘어가기 전에 answer++를 한다는 전제)
ex) name = "ABCD"
	1) 0:'A' → 1:'B' → 2:'C' → 3:'D'	: 3번의 이동
    	2) 1:'B' → 2:'C' → 3:'D'		: 2번의 이동

0개의 댓글