[Code Tree] TreeSet - 최대로 연속한 숫자 [미해결]

0부터 n까지 숫자들이 정확히 하나씩 놓여 있습니다. 이때 m개의 숫자를 순서대로 하나씩 제거해보며, 제거한 이후 남은 숫자들로 만들 수 있는 수열 중 연속하여 나타나는 숫자들로만 이루어진 수열의 최장 길이를 구하는 프로그램을 작성해보세요.

예를 들어 처음에 [0, 1, 2, 3, 4, 5, 6, 7, 8]이 있었는데 숫자 3을 제거하게 된다면, [0, 1, 2, 4, 5, 6, 7, 8]이 남게 되므로 연속한 숫자들로 만들 수 있는 수열 중 최장 수열은 [4, 5, 6, 7, 8]이 되므로 최장 길이는 5가 됩니다.

입력 형식
첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어집니다.

두 번째 줄에는 m개의 숫자가 공백을 사이에 두고 주어집니다. 이때 주어지는 숫자들은 전부 다름을 가정해도 좋습니다.

1 ≤ n ≤ 10 
9
 

1 ≤ m ≤ min(n-1, 100,000)

0 < 지워지는 숫자들 < n

출력 형식
n번에 걸쳐 해당 숫자를 제거한 이후에 남은 숫자들을 이용해 만들 수 있는 연속한 숫자들로만 이루어진 수열 중 최장 수열의 길이를 한 줄에 하나씩 출력합니다.

입출력 예제
예제1
입력:

8 3
3 6 2
출력:

5
3
2

 

처음부터 쉽지않은 문제였습니다. 물론 지금은 해결하진못했지만 글을 올리는 이유는 이런 문제를 다시 놓치기 않기 위해서입니다. 못푸는 문제는 그저 못푸는 문제가아닌 충분히 풀어야하는 문제로 간주해야합니다.

 

제 접근 방식은 이랬습니다.

 

1.0 ~ N까지의 현재있는 위치에대한 최대갯수를 진행합니다

0 6

1 5

2 4

3 3

4 2 

5 1

에서 왼쪽에서부터 진행하는 최대갯수를 기억하고자 진행했습니다. 이렇게 하지만 N의 범위가 10^9이기때문에 시간복잡도에서 문제가 생기고 맙니다. 이 방법은 포기했습니다.

 

2. M개의 숫자에서 범위를 조정하여 문제를 해결하려했습니다.

맨처음 시작은 TreeSet의 객체를 만들어  (최대길이,왼쪽 인덱스, 오른쪽 인덱스) 로 진행했습니다.

그렇게된다면 9,0,9가 되는것입니다. 현재 이상태를 만들고 

M의 숫자가 현재 TreeSet에 사이에있을때, 맨왼쪽에 있을때, 맨오른쪽에 있을때를 가정하였습니다. 

 

M이 맨왼쪽의 숫자와 똑같다면 (맨왼쪽, 중간값-1,중간값-맨왼쪽), 오른쪽의 숫자와같다면 (중간값+1,맨오른쪽값, 맨오른쪽 - 중간값) 이고 숫자가 맨왼쪽과 맨오른쪽의 숫자가 같다면 그냥 삭제하는 방식으로 진행했습니다.

하지만 이방법또한 모든 객체를 순회해야하기때문에 시간복잡도를 고려한다면 시간초과가 나는 방향이였습니다.  이 방법또한 해결하지 못했습니다.

 

이를 통해 TreeSet의 객체를 만들어 (최대길이, 왼쪽 인덱스, 오른쪽 인덱스)를 이용해야한다는점을 이용해야한다고 생각했습니다. 그렇지만 도무지 생각나진않았습니다. 다음 포스팅때 꼭 해결하러 돌아오겠습니다.