[Java] 연속적인 수열 검사

개발 문법만 알고 있다면 이해할 수 있게 쉽게 작성
단순 일반적인 방법이 아닌 성능을 고려하여 작성
새로운 접근 방법을 알 수 있다

목차

1. 문제 설명
2. 알고리즘 접근방법
3. 최종 코드

1. 문제 설명

데이터(N)를 입력받아 데이터를 정렬하면 연속적인 수열인지 판단해보자
연속적인 수열이란 항상 i번째 숫자의 값이 (i+1)번째 숫자보다
1이 작은 정수로 이루어진 수열을 의미한다(1, 4, 5, 2, 3) -> 1, 2, 3, 4, 5
조건 : 데이터 N은 중복이 아니다

2. 알고리즘 접근방법

위 알고리즘의 접근방법은 간단하다

1. 데이터 정렬 (sort)
2. 연속수열 판단 = [i] + 1 == [i + 1]

그러나 위 방식은 뻔하기도 하고 정렬 알고리즘에 따라 O(n Log n), O(N^2)의 시간복잡도를 가지는데 우리는
O(N)의 시간 복잡도를 가지는 알고리즘으로 풀어보겠다

a를 입력받은 데이터, b를 A의 수열이라고 가정한면
a의 집합이 b와 같다 = a를 정렬하면 b가 된다
즉 a, b의 차이는 원소의 순서 이다
우리는 언제 정렬을 써야하냐?
-> 순서를 통해서 유의미한 캐치가 가능할 때
-> 순서에 대한 정보가 필요없다면 정렬을 안써도 된다 (현 문제 케이스)

아이디어 1

주어진 배열의 최소값을 Min, 최댓값을 Max라고 하면
배열에 Min보다 작고, Max보다 큰 값은 없다
배열[Min, Max] 범위의 모든 정수가 하나씩 존재한다면 정렬 했을 때 연속 수열이 된다
해당 범위에는 M = (Max - Min + 1)가지의 정수가 존재
ex) [1, 2, 3, 4, 5] => 5 - 1 + 1 = 5 = M

M : 배열에서 최대값 - 최소값 + 1
N : 입력 데이터 개수

• M < N의 경우 = data[1, 2, 2, 3] = M : 3, N : 4
  - 배열에 중복이 반드시 포함(1, 2, 2, 3) -> 연속 수열 x
• M > N 의 경우
  - [Min, Max] 범위의 연속 수열이 되기 위해선 M개의 원소가 필요한데
  배열의 크기(N)가 M개의 원소가 들어갈 수 없기에 연속 수열 x
• M == N의 경우
  - [Min, Max] 범위의 숫자가 정확히 하나씩 들어갈 수 있다
  • 중복이 들어갈 수 있다(1, 2, 2, 4, 5)

그러나 문제 조건에서 입력에서 중복이 들어가지 않기 때문에 위 방식을 사용할 수 있다!!

즉 m = n이라면 -> (Max - Min + 1) = N이라면 연속 수열

3. 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q2I {
    private static boolean inConsecutive(int[] data, int n) {
        // 정렬을 통해 풀지 않고 중복되지 않는 연속 순열의 케이스에 대해 O(N) 시간복잡도를 가진 알고리즘으로 풀어보자
        int Max = data[0];
        int Min = data[0];

        for(int i = 0; i < n; i++){
            if(Max < data[i]){
                Max = data[i];
            }
            // else if를 하지 않는 이유는 최대값 최소값을 안쓰는 값으로 초기화 할 수 있고 원소가 1개라면 둘다 최소최대가 되기 때문
            if(Min > data[i]){
                Min = data[i];
            }
        }
        return Max - Min + 1 == n;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 데이터의 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine()); // 데이터 입력

        int[] data = new int[n]; // 데이터의 수 만큼 배열 할당
        for(int i = 0 ; i < data.length; i++){
            data[i] = Integer.parseInt(st.nextToken()); // 배열에 데이터 삽입
        }

        boolean result = inConsecutive(data, n); // 연속 순열 판별 함수

        if(result){ // 결과에 따른 출력 구분
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

후기

처음에 이 문제를 봤을 때 "아 이거 정렬해서 풀면 되겠네~~"라고 단순히
생각했는데 이런 알고리즘이 있구나 깨닫는 시간이 됐다
단 이 알고리즘은 입력에 중복이 없다는 조건이 들어갈 때 쓸 수 있으니
문제의 조건의 중요성을 다시 한번 깨닫는 시간이 됐다.