네 다른 사이트 질문도 대환영입니다
(스포주의 힌트입니다.)
예를 들어 설명드릴게요
일단 정답이 다음과 같은 경우라고 합시다.
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 개수가 짝수일 때는 푸셨다고 하시니 중간에 있는 사람들 찾는 방법은 알고 계실 겁니다.
코드를 보니 O(N^2)으로 작성하신 것 같네요.
c++에서는 set과 map 을 이용하시면 시간복잡도 O(NlogN)으로 푸실 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
dudn134 6년 전 1
http://codeforces.com/problemset/problem/490/B
input 개수가 짝수일 경우에는 0을 기준으로 갱신하니까 정답이 구해지긴 하는데.
문제가 input이 홀수일 경우 어떻게 구하는지 모르겠네요...
혹시 푸신분들 있으시면 팁좀 주세요!