|| 문제설명 ||
-
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있다.
-
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
- ▲ : 다음 알파벳
- ▼ : 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
- ◀ : 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
- ▶ : 커서를 오른쪽으로 이동
-
이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 작성하라.
- name : 만들고자 하는 이름
_ name : 알파벳 대문자
_ name의 길이 : 1 이상 20 이하|| 문제해결방법 ||
- 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번의 이동
[2021.02.20]
#include <string>
#include <vector>
using namespace std;
int find(int& i, string name) {
int cnt = 0;
for(; name[i] == 'A'; i = (i + 1) % name.size()) {
if(cnt == name.size() - 1) break;
cnt++;
}
return (cnt > name.size() - cnt - 1) ? name.size() - cnt - 1 : cnt;
}
int solution(string name) {
int answer = 0, cnt;
for(int i=0;; i = (i + 1) % name.size()) {
if(name[i] == 'A') {
if((cnt = find(i, name)) == 0) return answer -1;
answer += cnt;
}
else answer++;
int min = name[i] - 'A';
answer += min < 26 - min ? min : 26 - min;
name[i] = 'A';
}
return answer;
}기대값보다 1 작은 경우(return answer - 1;)와 기대값과 같은 경우(return answer;) 딱 두가지로 나뉜다.
1) return answer - 1;
2) return answer;
맨 처음 FOR문 안으로 들어왔을 때 A인 경우와 아닌 경우 중 아닐 때 ANSWER++된 상태로 시작하기 때문에 따로 예외를 만들어줘야 할 것 같다.
