[릿코드] 1806. Minimum Number of Operations to Reinitialize a Permutation

문제 출처

https://leetcode.com/contest/weekly-contest-234/problems/minimum-number-of-operations-to-reinitialize-a-permutation/

문제 설명

짝수인 양의 정수 n이 주어진다.

크기가 n인 수열 perm은 perm[i] == i이라고 초기화한다. (단, 0-indexed. i는 0부터)

수열 perm에 대해 연산을 1회 실행하면 새로운 수열 arr은 각 i에 대해 다음과 같이 정의한다.

• i % 2 == 0라면, arr[i] = perm[i / 2]이다.
• i % 2 == 1라면, arr[i] = perm[n / 2 + (i - 1) / 2]이다.

 

처음의 perm에서 연산을 몇번 해야 다시 처음의 perm으로 돌아오는 지 구하라.

문제 풀이

n을 4부터 10까지 시뮬레이션해봤다.

n의 증가에 따라 어떤 패턴이 보이긴하는데 이 패턴을 이용해서 연산을 줄이는 방법은 떠올리지 못했다.

하지만 특별한 로직없이 완전탐색만으로 통과할 수 있는 문제였다.

코드

코드 해설

return IntStream.range(0, n).toArray();

자바 8에 익숙하지 않다면 생소한 코드이다. 이 코드는 아래 코드와 동일하다.

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
    arr[i] = i;
}
return arr;

자바 8 이전이라면 네 줄로 표현해야한다. 자바 8의 Stream 클래스를 사용하면 대부분의 반복문들을 간결하게 만들 수 있다. 코드가 간결하면 직관력이 좋아지고, 오타의 위험이 적어지며, ArrayIndexOutOfBoundsException의 위험도 없어진다. 단점으로는 디버깅이 어려워진다.

 

나머지는 정말 문제대로만 구현했기때문에 생략한다.