문제
정수 배열 arr가 주어집니다. arr의 각 원소에 대해 값이 50보다 크거나 같은 짝수라면 2로 나누고, 50보다 작은 홀수라면 2를 곱하고 다시 1을 더합니다.
이러한 작업을 x번 반복한 결과인 배열을 arr(x)라고 표현했을 때, arr(x) = arr(x + 1)인 x가 항상 존재합니다. 이러한 x 중 가장 작은 값을 return 하는 solution 함수를 완성해 주세요.
단, 두 배열에 대한 "="는 두 배열의 크기가 서로 같으며, 같은 인덱스의 원소가 각각 서로 같음을 의미합니다.
- 제한사항
- 1 ≤ arr의 길이 ≤ 1,000,000
- 1 ≤ arr의 원소의 값 ≤ 100
풀이
처음에는 문제를 완전히 잘못 이해해서 반복횟수가 아닌 인덱스 값을 구하고 있었다. 그러다 입출력 예제를 꼼꼼히 읽고 무엇을 구해야 하는지 제대로 알게 되었음.. 미쳐미쳐
루프를 반복할 때마다 변화하는 정수 배열 arr을 기록하기 위해 새로운 배열 int[] newArr을 만들고, 배열을 복사하기 위해 Arrays.copyOf()를 사용했다. 이전 예제들에서부터 꾸준히 이용하는 거다만 java.util.Arrays 패키지에 있는 메서드를 참 유용한 듯.
암튼 조건이 충족될 때까지 무한 루프를 돌도록 while(true) 안에 for문을 선언한다. 그 다음 문제에 주어진 조건 대로 arr[i]의 값을 바꾸어 준다. 이때 배열끼리 값을 비교할 때 Arrays.equals() 메서드를 사용하고, 같다면 break;로 while문을 빠져 나온다.
Arrays.equals()는 arr과 newArr의 원소 값들을 효율적으로 비교할 방법이 없을까 하여 구글링을 하다가 발견했다.
==사용 시, 문자열을 비교할 때와 마찬가지로 heap 영역에 있는 배열의 참조값들을 비교하기 때문에Arrays.equals()를 사용해야 배열의 값들을 온전히 비교할 수 있다고 한다.
같지 않다면, for문을 돌며 값이 변경된 int[] arr을 Arrays.copyOf()를 활용해 int[] newArr에 다시 복사해둔다. 그리고 최소한의 반복횟수를 구하기 위해 증감식을 활용해 answer++;와 같이 값을 더해준다.
import java.util.Arrays;
class Solution {
public int solution(int[] arr) {
int answer = 0;
int[] newArr = Arrays.copyOf(arr, arr.length);
while(true){
for(int i=0;i<arr.length -1;i++){
if(arr[i]%2 == 0 && arr[i] >= 50){
arr[i] /= 2;
}else if(arr[i]%2 == 1 && arr[i] < 50){
arr[i] = (arr[i] * 2) + 1;
}
}
if(Arrays.equals(arr, newArr)){
break;
}
newArr = Arrays.copyOf(arr, arr.length);
answer++;
}
return answer;
}
}결과
