문제
부터 까지의 정수를 한 번씩만 사용하여 다음 조건을 만족하는 수열 , , , 을 출력하라.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다.
둘째 줄부터 각 테스트 케이스마다 개의 줄에 양의 정수 , 가 공백으로 구분되어 주어진다. ;
모든 테스트 케이스의 의 합은 을 넘지 않는다.
출력
각 테스트 케이스마다 주어진 순서대로 개의 줄에,
- 만약 조건을 만족하는 수열이 있다면 수열 , , , 을 공백으로 구분하여 출력한다.
- 만약 조건을 만족하는 수열이 없다면 -1을 출력한다.
풀이
조건을 식으로 따라가 보면 에서 시작해 값을 따라가며 수열 전체를 한 번씩 순회해야 한다. 현재 구현은 가능한 경우가 매우 제한적이라는 점을 이용해 만 바로 처리하고, 일반적인 경우에는 일 때만 2, 3, 4, ..., N, 1 형태를 만들어 출력한다.
실제로 이 배열에서는 값이 다음 인덱스를 가리키는 사슬이 2 -> 3 -> 4 -> ... -> N -> 1로 이어진다. 조건을 만족하는 구조가 사실상 하나뿐이라는 관찰이 구현의 전부라고 볼 수 있다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
while (T-- > 0) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
String ans = solve(N, K);
sb.append(ans).append('\n');
}
System.out.println(sb);
}
static String solve(int N, int K) {
if (N == 1)
if (K == 1) return "1";
else return "-1";
if (K != 2) return "-1";
StringBuilder ans = new StringBuilder();
for (int i = 0; i < N; i++) {
if (i == N - 1) ans.append(1);
else ans.append((i + K)).append(" ");
}
return ans.toString();
}
}복잡도
- 시간 복잡도: 각 테스트 케이스에서 길이 의 수열을 출력하므로 전체 의 합을 라 할 때 이다.
- 공간 복잡도: 출력 버퍼를 제외하면 추가 자료구조를 사용하지 않으므로 이다.
마무리
조건을 식으로 따라가 보면 에서 시작해 값을 따라가며 수열 전체를 한 번씩 순회해야 한다.
