[Java] level2 - greedy_42839 : 조이스틱
문제 링크
풀이
로직
상하 움직임
- A가 아닌 값은 위아래로 몇번 움직이면 되는지 구하면 된다
- A~Z까지
diff
에 위 or 아래로 몇번 움직이는게 최단인지 담아둔다.diff
길이가 알파벳 갯수와 동일하고diff
의 idx는 알파벳에서의 idx와 동일 =>diff
에서 idx 1번은 B를 의미, idx 25번은 Z를 의미
int answer = 0;
int[] diff={0,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}; // A~Z까지 몇번 움직여야하는지 나타냄
// N(13) 다음부터는 거꾸로 움직이는게 빨라 숫자가 작아짐
// 상하 움직임 계산하는 부분
for(char c:name.toCharArray())
answer+=diff[c-'A']; // A로부터의 위아래로 조이스틱을 몇번 움직여야하는지를 계산해줌
좌우 움직임
- 좌우 움직임을 가져가려면 1) 우측 + 우측되돌아가기 + 좌측, 2) 좌측 + 좌측되돌아가기 + 우측 이 두가지가 우측으로만 움직였을때 보다 작아야한다.
- 맨앞쪽 or 맨뒤쪽 연속된 A가 있을경우 => 우측으로만 움직이거나, 좌측으로만 움직이거나 하면된다.
- (참고) 맨앞쪽에 연속된 A가 있는 경우는 아래 코드에서 좌측으로 움직이는 경운 i=0인 경우로 고려됨
- 즉, 우측 0회 + 우측되돌아가기 0회 + 좌측 n회 이렇게 계산되니 => 좌측으로만 몇회 움직였는지로 계산됨
- 중간에 A가 있는 경우 => 이경우가 좌우로 모두 움직임 가져가야하는 경우임
- 맨앞쪽 or 맨뒤쪽 연속된 A가 있을경우 => 우측으로만 움직이거나, 좌측으로만 움직이거나 하면된다.
int length=name.length();
int min=length-1; // 초기값이 length-1인 이유는 우측으로만 움직였을때 length-1번이면 모든 글자들 다 훑을 수 있음
for(int i=0;i<length;i++){
int next=i+1;
while(next<length && name.charAt(next)=='A'){ // 다음글자가 A이면 오른쪽으로 넘어가기때문에 next++해줌
next++;
}
// min에는 최소한의 좌우 움직임이 몇번인지 담기게됨
// i : 우측 움직임 횟수
// length - next : 좌측 움직임 횟수(거꾸로)
// i + length-next + Math.min(i, length-next) : 좌측/우측 움직임 + 되돌아오는 횟수 <- 이때 되돌아 오는 횟수는 좌측/우측 중 작은 횟수
// Math.min(min, i + length-next + Math.min(i, length-next) )
// => 단순히 우측으로만 움직이는 것과 좌측/우측 왔다갔다하면서 움직이는 것 중 가장 더 적게 움직이는 횟수 택하게됨
min = Math.min(min, i + length-next + Math.min(i, length-next) );
Author And Source
이 문제에 관하여([Java] level2 - greedy_42839 : 조이스틱), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@oneofakindscene/Java-level2-greedy42839-조이스틱저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)