class Solution {
public int solution(String name) {
int answer = 0;
int nameLen = name.length();
boolean[] changed = new boolean[nameLen];
int tmp = 0;
int trueCount = 0;
for(int i = 0; i<nameLen;++i) {
if(name.charAt(i) != 'A') {
tmp = name.charAt(i)-'A';
if(tmp < 13)
answer += tmp;
else
answer += (26-tmp);
changed[i] = true;
trueCount++;
}
}
changed[0] = false;
trueCount--;
int min = nameLen;
int minIndex = -1;
//0,1,2,3
//4-3-cursor = 1
//4-2-cursor = 2
//4-1-cursor = 3
//
int cursor = 0;
int distance = 0;
while(trueCount > 0) {
min = nameLen;
minIndex = -1;
for(int i = 0; i<nameLen;++i) {
if(changed[i] == true) {
distance = (cursor > i) ? cursor-i:i-cursor;
if(cursor < i) {
distance = (nameLen-distance < distance) ? nameLen-distance : distance;
}
if(min > distance) {
min = distance;
minIndex = i;
}
}
}
changed[minIndex] = false;
answer += min;
trueCount--;
cursor = minIndex;
}
return answer;
}
}
아 이게 어떻게 레벨2짜리 문제인건지..;;
예전에 문제를 풀었을 때는 글자를 바꾸고 한 칸 옮기고 글자를 바꾸고 한 칸 옮기는 식으로 했었는데 책을 본 효과인지는 모르겠지만.. 글자가 다른 경우를 미리 다 처리하고 나서 옮기는 것에 대해서만 고려할 수 있도록 코드를 짜보니 확실히 깔끔해졌다.
다만 테스트케이스 11에서 틀렸다고 나오는데 다른 사람들 질문 내용을 봐도 감이 안온다. 그리디 알고리즘이라고 할 때 가장 가까운 값으로 이동을 하는 것 외에 고려할게 없을텐데.. 문제가 약간 이상하다고 생각해서 여기까지 하고 넘긴다.
지금은 마땅히 생각나는 문제점을 못찾고 있으니 다음에 한 번 더 봐야겠다.
'문제풀이' 카테고리의 다른 글
프로그래머스(모의고사) (0) | 2021.06.10 |
---|---|
프로그래머스(섬 연결하기) (0) | 2021.06.08 |
프로그래머스(체육복) (0) | 2021.06.07 |
프로그래머스(큰 수 만들기) (0) | 2021.06.07 |
프로그래머스(구명보트) (0) | 2021.06.07 |