static int table[200000 + 1];
static int N;
static int solution(void)
{
int ret = 0, val;
scanf("%d", &N);
for (int i = 1; i <= N; i++)
{
scanf("%d", &val);
if (!table[val - 1])
{
ret += 1;
table[val] = ret;
}
else
table[val] = table[val - 1];
}
memset(table, 0, sizeof(table));
return ret;
}문제를 읽다보면 단순히 문제에서 하라는 대로 코드만 작성하면 테스트시에는 원하는 답을 구할 수는 있었다.
물론 실제로 채점을 하면 제한시간 초과가 발생하였다. 나름 연결 리스트를 사용하고, 매 스캔마다 그 범위를 줄이기 위해 처리된 구간을 전체 입력을 저장한 연결 리스트에서 제거도 하였지만 말이다.
그래서 이에 대해서 생각을 해보니 최악의 경우가 하나 있었다.
20만부터 1까지 내림차순으로 있는 경우다.
문제에서 하라는 대로 하면
1> 20만번 리스트를 순회하고 1이 제거됨
2> 19만번 리스트를 순회하고 2가 제거됨.
...
200000> 1번 리스트를 순회하고 200000이 제거됨.
이 경우 대략 100000*199999 번 리스트를 순회하게 된다. 대략 39,999,800,000 번이다.
그래서 배열 전체를 보는 방법을 생각해보다가 아래와 같은 방법을 발견하였다.
4 3 5 1 2 6 이 있을 때 연속해서 증가하는 그룹을 찾는 것이다.
(4 (3) 5 (1, 2), 6)
3이 하나의 그룹/ 4, 5, 6 이 하나의 그룹/ 1, 2가 하나의 그룹인 것이다. 이렇게 그룹의 개수를 구하면 답을 구할 수 있다.
그리고 입력의 개수가 200000으로 제한되기 때문에 내가 즐겨쓰는 table을 사용 할 수 있다.
위 경우를 토대로 작성한 코드를 설명하면
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 2 | 1 | 0 | 0 |
| 0 | 0 | 0 | 2 | 1 | 1 | 0 |
| 0 | 3 | 0 | 2 | 1 | 1 | 0 |
| 0 | 3 | 3 | 2 | 1 | 1 | 0 |
| 0 | 3 | 3 | 2 | 1 | 1 | 1 |
이런식으로 흐름이 이어지는 것이고, 매번 입력으로 받을 길이, 최대 200000번만 반복하면 되게 된다.
