오답노트 #1337 : 올바른 배열

풀이방법 및 문제점

2022.03.21

주어진 수열을 오름차순 정렬한 뒤,

정렬된 주어진 수열에 포함된 가장 긴 연속하는 수열을 찾아서,

그 수열의 길이가 5 이상이라면 0을 출력하고, 5 미만이라면 5에서 해당 수열의 길이를 뺀 값을 출력하였다.

그러나, 이렇게 하면

1 2 3

위와 같은 연속되는 수열이 있을 때에는 2를 잘 출력하지만

1 3 5

위와 같은 경우를 캐치하지 못한다. 2, 4를 넣으면 연속되는 길이 5의 수열이 될 수 있다는 것을 알아내고 2를 출력해야 하는데, 그냥 무의미한 수들로 판단해버리기 때문이다.

 

저렇게 띄엄띄엄 연속되는 경우를 어떻게 해야 잡아낼 수 있을까?

알고리즘 분류에 투 포인터가 있던데 그걸 힌트 삼아서 잘 생각해봐야겠다.

 

2022.03.23

해결되었다.

정답 게시물 바로가기

 

코드

Java(2022.03.21)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for(int i = 0; i< n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		
		int cnt = 1;
		int max_cnt = 1;
		for(int i = 1; i<n; i++) {
			if(arr[i] - arr[i-1] == 1) {
				cnt++;
				max_cnt = Math.max(cnt, max_cnt);
			}
			else cnt = 1;
		}
		if(max_cnt>=5)System.out.print(0);
		else System.out.print(5-max_cnt);
	}

}