문제 설명
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
접근 방법
해당 문제에서는 완성해야 하는 알파벳 이름이 주어졌을 때 이를 만들기 위한 최소한의 조이스틱 조작 횟수를 요구하고 있습니다.
우선 조이스틱의 조작은 크게 알파벳 이름을 조작하는 것과 커서 이동을 조작하는 것 이 두 가지로 나뉜다고 볼 수 있습니다.
알파벳 이름 조작하기
알파벳 이름을 조작하기 위해 먼저 만들어야 할 이름의 문자와 최초 문자(A) 간 아스키 코드 값 차이를 구하도록 했습니다. 이때 이 값(gap)이 13 미만이라면 이 값만큼 조작하는 것이 최소 조작 횟수일 것이고, 13 이상이라면 26이라는 수에 이 값을 빼는 것이 최소 조작 횟수일 것입니다. (26은 알파벳 전체 개수를 의미)
int answer = 0;
int length = name.length();
char[] targetName = name.toCharArray();
int gap;
for (int i = 0; i < length; i++) {
gap = targetName[i] - 'A';
if (gap < 13) {
answer += gap;
} else {
answer += (26 - gap);
}
}
커서 이동 조작하기
나름대로의 직관적으로는 커서를 이동할 수 있는 유형은 총 4가지라고 생각했었습니다. 첫째는 역방향으로만 이동하는 경우, 둘째는 정방향으로만 이동하는 경우, 셋째는 정방향으로 이동하다가 중간에 역방향으로 이동하는 경우, 넷째는 역방향으로 이동하다가 중간에 정방향으로 이동하는 경우입니다. (여기서 정방향이란 왼쪽에서 오른쪽을, 역방향이란 오른쪽에서 왼쪽을 의미합니다.)
우선 역방향으로만 이동하는 경우는 왼쪽에서 두 번재 문자에 가장 가까운 문자 중 A가 아닌 문자까지 커서를 이동하면 될 것 입니다. 이에 대한 조작 횟수를 구하는 로직은 다음과 같습니다.
int temp1 = 20;
boolean flag = true;
// 역방향으로만 탐색 시 마지막 No A 문자
for (int i = 1; i < length; i++) {
if (targetName[i] != 'A') {
temp1 = length - i;
flag = false;
break;
}
}
if (flag) {
return answer;
}
이때 A가 아닌 문자가 하나도 없다면 별도로 커서 이동을 조작할 필요가 없으므로(첫 번째 문자만 이름 변경) 앞서 알파벳 변경 조작 횟수를 그대로 반환해주었습니다. 아울러 temp 값을 20으로 초기화해주었는데, 이는 추후에 각각의 커서 이동 유형별로 최소 조작 횟수를 구하기 위함입니다.
정방향으로만 이동하는 경우에는 반대로 오른쪽 문자에 가장 가까운 문자 중 A가 아닌 문자까지 커서를 이동하면 될 것 입니다. 이에 대한 조작 횟수를 구하는 로직은 다음과 같습니다.
int temp2 = 20;
// 정방향으로만 탐색 시 마지막 No A 문자
for (int i = length - 1; i > 0; i--) {
if (targetName[i] != 'A') {
temp2 = i;
break;
}
}
정방향으로 이동했다가 중간에 역방향으로 이동하는 경우에는 일차적으로 A가 아닌 문자를 찾은 다음 다시 처음으로 돌아왔다고 간주하고 앞서 찾은 문자의 오른쪽을 기준으로 가장 가까운 A가 아닌 문자까지 커서를 역방향으로 커서를 이동하는 횟수를 구하도록 했습니다.
이후 주어진 문자열을 순회하면서 동일한 작업을 반복하면서 커서를 이동하는 횟수의 최솟값을 구하도록 했습니다. 이에 대한 조작 횟수를 구하는 로직은 다음과 같습니다.
int index = 0, temp3 = 20;
int forwardAndReverse;
for (int i = 1; i < length; i++) {
if (targetName[i] != 'A') {
forwardAndReverse = i * 2;
for (int j = i + 1; j < length; j++) {
index = j;
if (targetName[j] != 'A') {
break;
}
}
forwardAndReverse += length - index;
temp3 = Math.min(temp3, forwardAndReverse);
index = 0;
}
}
마지막으로 처음부터 역방향으로 커서를 이동했다가 중간에 정방향으로 이동하는 경우에는 앞서 정방향 후 역방향 커서 이동과 동일한 방법으로 방향만 바꿔서 커서 이동 최소 횟수를 구하도록 했습니다. 이에 대한 조작 횟수를 구하는 로직은 다음과 같습니다.
int reverseAndForward, temp4 = 20;
for (int i = length - 1; i > 0; i--) {
if (targetName[i] != 'A') {
reverseAndForward = (length - i) * 2;
for (int j = i - 1; j > 0; j--) {
index = j;
if (targetName[j] != 'A') {
break;
}
}
reverseAndForward += index;
temp4 = Math.min(temp4, reverseAndForward);
index = 0;
}
}
최종적으로 각각의 커서 이동 유형 중 가장 적은 이동 횟수를 반환하도록 했습니다.
answer += Math.min(Math.min(temp1, temp2), Math.min(temp3, temp4));
전체 소스 코드
class Solution {
public int solution(String name) {
int answer = 0;
int length = name.length();
char[] defaultName = getDefaultName(length);
char[] targetName = name.toCharArray();
boolean hasNoA = validate(targetName);
int gap;
for (int i = 0; i < length; i++) {
gap = targetName[i] - defaultName[i];
if (gap < 13) {
answer += gap;
} else {
answer += (26 - gap);
}
}
if (hasNoA) {
answer += length - 1;
return answer;
}
int temp1 = 20, temp2 = 20, temp3 = 20, temp4 = 20;
boolean flag = true;
// 역방향으로만 탐색 시 마지막 No A 문자
for (int i = 1; i < length; i++) {
if (targetName[i] != 'A') {
temp1 = length - i;
flag = false;
break;
}
}
if (flag) {
return answer;
}
// 정방향으로만 탐색 시 마지막 No A 문자
for (int i = length - 1; i > 0; i--) {
if (targetName[i] != 'A') {
temp2 = i;
break;
}
}
// 정방향 갔다가 다시 역방향
int index = 0;
int forwardAndReverse;
for (int i = 1; i < length; i++) {
if (targetName[i] != 'A') {
forwardAndReverse = i * 2;
for (int j = i + 1; j < length; j++) {
index = j;
if (targetName[j] != 'A') {
break;
}
}
forwardAndReverse += length - index;
temp3 = Math.min(temp3, forwardAndReverse);
index = 0;
}
}
// 역방향 갔다가 다시 정방향
int reverseAndForward;
for (int i = length - 1; i > 0; i--) {
if (targetName[i] != 'A') {
reverseAndForward = (length - i) * 2;
for (int j = i - 1; j > 0; j--) {
index = j;
if (targetName[j] != 'A') {
break;
}
}
reverseAndForward += index;
temp4 = Math.min(temp4, reverseAndForward);
index = 0;
}
}
answer += Math.min(Math.min(temp1, temp2), Math.min(temp3, temp4));
return answer;
}
private boolean validate(char[] targetName) {
for (int i = 1; i < targetName.length; i++) {
if (targetName[i] == 'A') {
return false;
}
}
return true;
}
private char[] getDefaultName(int length) {
char[] defaultName = new char[length];
for (int i = 0; i < length; i++) {
defaultName[i] = 'A';
}
return defaultName;
}
}
참고자료
'Algorithm > Programmers' 카테고리의 다른 글
| [프로그래머스] 게임 맵 최단거리 - Java (0) | 2022.07.11 |
|---|---|
| [프로그래머스] 큰 수 만들기 - Java (0) | 2022.07.11 |
| [프로그래머스] 소수 찾기 - Java (0) | 2022.07.07 |
| [프로그래머스] 행렬 테두리 회전하기 - Java (0) | 2022.07.06 |
| [프로그래머스] [1차] 뉴스 클러스터링 - Java (0) | 2022.07.05 |