leetcode 932 - Beautiful Array
https://leetcode.com/problems/beautiful-array/ 풀이 $i < k < j$ 일 때 $2\cdot A[k] = A[i] + A[j]$ 를 만족하는 i, k, j가 없는 배열을 구해야 한다. 길이 n짜리 배열 [1, 2, 3, ..., n]이 있을 때 이 조건을 만족하는 배열을 찾기 위해 문제를 나눌 수 있다. [1, 3, 5, ..., (n+1)/2] 배열과 [2, 4, 6, ..., n/2]로 문제를 나눈 다음에 각 배열의 beautiful array를 구했다고 생각해보자. 각 배열 안에서는 정의 그대로 위 조건에 해당하는 i, k, j가 없다. 이때 두 배열을 concat 한 배열에도 그런 i, k, j는 없음이 보장된다. 앞 배열에 i, 뒷 배열에 j가 있을 때 A..
2020. 10. 6.
