1007: 유일한 수

Link : judge.koreatech.ac.kr/problem.php?id=1007

---

1. 문제

• 텔동 한쪽에 있는 마을 "짝" 에는 모든 숫자들이 두개씩 쌍을 이루어 존재하고 있습니다. 하지만 어디에도 솔로는 존재하듯, 이곳에도 짝을 이루지 못한 숫자 하나가 있지요. 그나마 다행인건 단 하나의 숫자만 짝이 없을 뿐, 나머지는 짝이 있어요.
  짝을 만들어주기 위하여 단 하나만 있는 숫자를 찾아 주세요.

 

---

2. 문제의 조건

• 1 <= N <= 100001 인 홀수
• K ∈ singed int
• 반드시 짝이아닌 유일한 정수가 존재함

 

---

3. 문제 접근

• 시간 복잡도
  
  시간 제한 1초에 n의 범위는 100001이므로 O(N^1.6) 이내의 시간안에 풀면 되므로 "O(N log N)의 시간이면 충분하지 않을까?" 하고 생각했습니다.

 

• 아이디어
  
  정렬이 되어있으면 짝을 판별하기에 편하다고 생각하여 정렬을 진행 하였습니다.
  그 후 0번째부터 0과 1이 짝인지 비교하고 짝이라면 2과 3을 비교합니다. 즉, 0 2 4 6 ... n 까지 진행합니다.
  1과 2를 비교할 필요 없는 이유는 0과 1이 짝이라면 1과 2는 당연히 짝이 아니기때문에 2씩 뛰어넘습니다.
  만약 다르다면 그게 정답이므로 바로 출력하고 IndexOutOfRange 오류가 난다면 그것은 arr[-1] 맨 끝자리가 유일한 정수 이므로 그것을 출력하면 됩니다.
  
  즉, n log n + n / 2 이므로 O(N log N)의 시간으로 해결할 수 있습니다.

 

---

4. 풀이 방법

• 데이터를 오름차순으로 정렬한다.
• i = 0부터 len(arr)까지 2씩 증가하며 탐색한다.
• 만약 arr[i]와 arr[i+1]이 다르면 그것이 짝이 아닌 수이다.
• 만약 i가 len(arr) - 1 까지 접근하여 if 의 arr[i+1]가 IndexOutOfRagne 오류가 난다면, 맨 끝 원소가 유일한 수이므로 그것을 출력한다.

 

---

5. 소스코드

• cjw-git.tistory.com/15

 

---

 

cjw.git@gmail.com