숫자 골라내기 (Picking Out Numbers)

> 문제 출처

https://www.codeground.org/practice/

1 Practice Picking Out Numbers

 

> 문제 설명

N개의 10진수를 입력받아 홀수번 나온 숫자들을 모두 XOR연산하여 결과를 리턴하는 문제.

초등학교교 학생인 정우와 석환이는 최근 학교에서 두 이진수의 XOR 연산에 대해 배웠다.
 둘은 매우 영특한 학생이라 새로 배운 연산을 갖고 이리저리 장난치기 시작했다.
 다만 석환이는 정우에게 일을 시키는 것을 좋아하는지라 다음과 같은 제안을 했다.

“내가 N개의 10진수를 주면, 등장하는 숫자들 중 홀수번만 나타나는 숫자들을 모두 XOR한 결과를 구해줘.”

나는 XOR을 정보처리산업기사 공부하면서 처음 접했는데 이놈들은 초딩때 이런 뻘짓을 하는걸 보니 대단하다.

 

> 접근 방법

처음에는 Global Array를 만들어 arr[입력값] = 나온 횟수로 하면 쉽겠다 했는데,

Test Case가 N <= 3,000,000에 각 숫자는 32bit 양수(unsigned int)라 미친짓인것 같았다.

 

그래서 처음 써보지만 key값으로 조회가 가능한 map을 이용하면 효율적일것 같다고 생각했다.

값을 입력 받을때 해당 키가 이미 존재하면 map에서 erase를 하고 존재하지 않는다면 insert를 하는 방식으로 구현하였다. 이렇게 하면 짝수번 호출된 녀석들은 메모리상에서 아예 없는 상태이기 때문에 iteration시간과 메모리를 효율적으로 관리할 수 있을것 같았다.

 

입력과정이 끝나고 map에 저장된 키값들을 차례대로 XOR연산하여 Anwer값을 리턴하였다.

 

> CODE

 

 

codeground에서 가장 쉬운 문제인데 처음에 XOR을 몰라서 못풀었다가 2년만에 다시 풀었다.

나름 효율적으로 코드를 작성했다고 생각하는데 런타임도 3배 이상 빠르고 메모리도 적게 쓴 사람들도 있다.

 

* 누가 볼것같다는 기대는 크게 안하지만... 댓글로 조언.질문 등 남겨주시면 매우 감사하겠습니다.

---

https://github.com/dongha-yoon/ProgrammingStudy - picking_out_numbers.cpp