티바이트


문제 링크 : http://judge.koreatech.ac.kr/problem.php?id=1007


32bit 크기의 정수 N개 (N은 1<=N<100001인 홀수)가 입력으로 주어진다.


하나를 제외한 나머지 수는 모두 짝이 있다. (짝수 번 중복된다.)


예시 

입력 : -1 2 0 -1 2

출력 : 0


입력 : 2 2 2 2 5

출력 : 5


입력 : 2 2 2 2 2

출력 : 2

(2와 2가 짝, 다시 2와 2가 짝이 되면 2 하나가 남는다.)



생각 1

integer범위 길이만큼의 배열을 만들어서 각각 몇 번 나왔는지 센다.

=> 메모리 용량 4GB가 필요하므로 비효율적


생각 2

입력이 들어올 때마다 리스트에 넣는다.

리스트에 넣을 때, 리스트를 선형탐색하여 자신과 같은 수가 있으면 그 수를 뺀다.

마지막에 남은 수를 출력한다.

시간복잡도 : O(n^2)

공간복잡도 : O(n)


생각 3

생각2에서 리스트 대신 트리를 사용한다.

시간복잡도 : O(nlogn)

공간복잡도 : O(n)


생각 4

임의의 정수 a, b, c에 대해 a xor b xor c xor b = a xor c 인 성질을 이용한다.

(어떤 정수에 임의의 정수를 짝수 번 xor 하면 원래대로 돌아온다.)

문제에서 한 수를 제외한 나머지 수들은 모두 짝수 번 반복되므로

들어오는 입력을 모두 xor연산하여 누적시키면 답이 나올 것이다.

시간복잡도 : O(n)

공간복잡도 : O(1)



소스코드 (C++)


#include <cstdio>


using namespace std;


int main(void)

{


int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int leng;

scanf("%d",&leng);


int acc = 0;

int num;

for (int i = 0; i < leng; i++) {

scanf("%d",&num);

acc ^= num;

}

printf("%d\n", acc);

}

return 0;

}






 





 


댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

Statistics Graph