문제
길이 N인 수열이 주어질 때, 인접한 원소의 차이로 새 수열을 만드는 변환을 K번 수행한 결과를 출력하라.
입력
첫째 줄에 N과 K, 둘째 줄에 쉼표로 구분된 N개의 정수가 주어진다.
출력
K번 변환 후의 수열을 쉼표로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 1 2,6,1,8 | 4,-5,7 |
풀이
K번 반복하며 매번 인접 원소의 차이로 새 배열을 생성한다.
- 쉼표로 구분된 입력을 정수 배열로 파싱한다
- K번 반복하며 각 반복에서
tmp[i] = A[i+1] - A[i]로 새 배열을 만든다 - 배열 길이가 매번 1씩 줄어든다
- 최종 배열을 쉼표로 연결하여 출력한다
핵심 아이디어: 차분 수열(difference sequence)을 K번 적용하는 시뮬레이션이다.
코드
package day699;
import java.io.*;
import java.util.*;
public class Day691BOJ1551수열의변화 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringBuilder sb = new StringBuilder();
private static StringTokenizer tokens;
private static int N, K;
private static int[] A;
public static void main(String[] args) throws IOException {
tokens = new StringTokenizer(br.readLine());
N = Integer.parseInt(tokens.nextToken());
K = Integer.parseInt(tokens.nextToken());
A = new int[N];
tokens = new StringTokenizer(br.readLine(), ",");
for (int i = 0; i < N; i++)
A[i] = Integer.parseInt(tokens.nextToken());
for (int k = 0; k < K; k++) {
int[] tmp = new int[N - 1];
for (int i = 0; i < N - 1; i++)
tmp[i] = A[i + 1] - A[i];
N--;
A = tmp;
}
for (int i = 0; i < N; i++) {
sb.append(A[i]);
if (i != N - 1)
sb.append(",");
}
System.out.println(sb);
}
}복잡도
- 시간: O(N * K) — 매 변환마다 N-k개의 원소 처리
- 공간: O(N) — 임시 배열