1074: 유일한 수 두개

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

---

1. 문제

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

 

---

2. 문제의 조건

• 1 <= T <= 10
• 1 <= N <= 100,002 (짝수)
• -50,000 <= K <= 50,000

 

---

3. 문제 접근

• 시간 복잡도
  
  10개의 T에다 10만개의 tc이니 총 100만개, 즉 O(N^1.333)에 수행하여야 합니다.

 

• 아이디어
  
  해당 문제는 stack을 이용하면 정렬을 포함하여 O(N log N)에 해결할 수 있는 문제입니다.

 

---

4. 풀이 방법

• 원소들을 정렬합니다. O(n log n)
• stack의 크기가 0이라면 그냥 원소를 추가합니다. O(1)
  0이 아니라면, stack의 마지막과 새로들어온 i를 비교합니다. O(1)
  만약 같으면 stack의 맨 마직막 원소를 빼줍니다 O(1)
• 해당 방식으로 끝까지 돌리면 2개만 남습니다.
  (정답이 없는 경우는 없다.)

 

---

5. 소스코드

• cjw-git.tistory.com/139

 

---

 

cjw.git@gmail.com