03 사전 체험용 코딩테스트 해설
1번 문제 - 정주행
수열로 주어지는 데이터에서 꼭 따져야 하는 내용은 다음과 같습니다.
- 중복여부
- 정렬여부
- 원소의 범위
- 특이한 규칙성 혹은 순환성
문제에서 주어지는 수열이 가지는 이런 특징들로 인해 가능한 풀이들이 존재하니 꼭 확인하셔야 합니다. 문제의 설명과 입력 형식을 잘 보고 위와 같은 데이터의 특징을 꼭 캐치하시기 바랍니다.
이 문제는 실제로 정렬하여 풀 수도 있지만, 데이터에 중복이 없다는 성질을 이용해 효과적으로 풀 수 있습니다. 동영상 해설을 참고하여 아래의 두 풀이에 대한 소스코드를 이해하고 자신의 것으로 만들어봅시다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//정렬을 사용한 O(N log N) 풀이
import java.util.*;
import java.io.*;
public class Main{
public static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args)
{
//데이터 입력
int n = scanner.nextInt();
int[] data = new int[n];
for(int i = 0 ; i < n ; i ++){
data[i] = scanner.nextInt();
}
//데이터를 정렬한다
Arrays.sort(data);
//정답이라고 가정한다
boolean flag = true;
for(int i = 0 ; i + 1 < n ; i ++){
if(data[i] + 1 != data[i+1])
{
//왼쪽(i)숫자가 오른쪽 숫자(i+1)보다 1 작아야 한다.
//주어진 조건을 한 번이라도 만족하지 않으면 연속적인 수열이 아니다
flag = false;
//이미 불가능하므로 더 이상 볼 필요 없다.
break;
}
}
if(flag){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}실행하여 결과를 확인하세요!
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//정렬을 사용하지 않은 O(N) 풀이
//입력 데이터에 중복이 없기에 가능하다.
import java.util.*;
import java.io.*;
public class Main{
public static final Scanner scanner = new Scanner(System.in);
public static int getMaximum(int[] data){
//배열의 최대값을 반환하는 함수
int max = data[0];
for(int i = 0 ; i < data.length; i++){
if(max < data[i]){
max = data[i];
}
}
return max;
}
public static int getMinimum(int[] data){
//배열의 최소값을 반환하는 함수
int min = data[0];
for(int i = 0 ; i < data.length; i++){
if(min > data[i]){
min = data[i];
}
}
return min;
}
public static void main(String[] args)
{
//데이터 입력
int n = scanner.nextInt();
int[] data = new int[n];
for(int i = 0 ; i < n ; i ++){
data[i] = scanner.nextInt();
}
//에피소드 중 가장 빠른 번호와 늦은 번호를 계산한다
int max = getMaximum(data);
int min = getMinimum(data);
//그 범위에 존재하는 편의 수를 계산한다
int btw = max - min + 1;
//그 범위에 존재하는 편의 수와 내가 본 편의 수가 같다면
//그 사이의 모든 편의 수가 존재한다 => 자연수 이므로 연속적이다.
if(btw == n){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}실행하여 결과를 확인하세요!
