네 다른 사이트 질문도 대환영입니다

(스포주의 힌트입니다.)

예를 들어 설명드릴게요

일단 정답이 다음과 같은 경우라고 합시다.

3 1 2 5 4 7 6

입력값은 다음과 같은 경우를 생각해 봅시다.

7

3 2

1 5

0 1

2 4

5 7

7 0

4 6

여기서 맨 앞줄에 있는 사람, 맨 앞에서 두번째 있는 사람, 맨 뒤에 있는 사람, 맨 뒤에서 두번째 있는 사람은

쉽게 알아 낼 수 있습니다.

일단 입력값에 0 1 부분을 보면 1이 앞에서 두번째 있는 사람이라는 건 알 수 있죠

입력값이 7 0 인 부분을 보면 7이 뒤에서 두번째 있는 사람이라는 건 알 수 있죠

맨 앞에서 두번째 있는 사람 : 1

맨 뒤에서 두번째 있는 사람 : 7

다음은 맨 앞에 있는 사람과 맨 뒤에 있는 사람을 찾는 방법 입니다.

입력값 에서 행이 아닌 열을 생각해봅시다.

1열 2열

3 2 (3 뒤에 뒤에는 2가 있음)

1 5 (1 뒤에 뒤에는 5가 있음)

0 1 (0 뒤에 뒤에는 1이 있음)

2 4 (2 뒤에 뒤에는 4가 있음)

5 7 (5 뒤에 뒤에는 7이 있음)

7 0 (7 뒤에 뒤에는 0이 있음)

4 6 (4 뒤에 뒤에는 6이 있음) 아 물론 여기서 0은 진짜 사람이 아니라 빈 자리죠

입력값에 ID로 들어온 숫자들은 0, 1, 2, 3, 4, 5, 6, 7 이죠.

7명의 사람이니 7가지 ID가 있습니다. 0은 ID가 아니라 빈 자리를 뜻하구요.

번호가 연속적이 아닌 경우도 있을거구요.

1열에 나온 숫자들을 봅시다

3 1 0 2 5 7 4

네 0부터 7까지의 숫자들이... 나왔..지 않죠!

6이 빠져 있습니다!! 0 1 2 3 4 5 7 은 있는데 말이죠

만약 6이 뒤에서 두번째라면 6 0이 입력값으로 왔어야 하고

만약 6이 뒤에서 세번째라면 6 x이 입력값으로 왔어야 하고 (x는 6의 뒤에 뒤에 서있는 사람, 즉 x는 맨 뒤에 있는 사람)

만약 6이 뒤에서 네번째라면 6 y이 입력값으로 왔어야 하고 (y는 6의 뒤에 뒤에 서있는 사람, 즉 y는 뒤에서 두번째 있는 사람)

.. 이런식으로 계속 반복 생각해보면 6은 맨 뒤에 말고는 있을 자리가 없죠.

맨 앞에 있는 사람을 찾는 것은 입력값의 2열을 보고 생각하면 됩니다.

2 5 1 4 7 0 6

여기도 역시 0부터 7까지의 숫자들 중 한개가 빠져 있습니다. 바로 3이지요.

이런식으로 줄의 가장 앞에 있는 사람, 앞에서 두번째 있는 사람, 줄의 가장 뒤에 있는 사람, 뒤에서 두번째 있는 사람은 쉽게 찾을 수 있습니다.

input 개수가 짝수일 때는 푸셨다고 하시니 중간에 있는 사람들 찾는 방법은 알고 계실 겁니다.

감사합니다

테스트 케이스 45까진 맞네요..

46부턴 시간초과 ㅠ

코드를 보니 O(N^2)으로 작성하신 것 같네요.

c++에서는 set과 map 을 이용하시면 시간복잡도 O(NlogN)으로 푸실 수 있습니다.