Funcia
Lv.1arraybit-manipulationmath

짝 없는 양말 한 짝

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

빨래를 개다 보니 양말 무늬 번호가 배열 socks로 정리되었습니다. 모든 무늬는 정확히 두 짝씩 있는데, 단 하나의 무늬만 한 짝뿐입니다.

짝이 없는 양말의 무늬 번호를 반환하세요. 양말은 아무 순서로나 놓여 있습니다.

입출력 예

socksresult
[2, 2, 1]1
[4, 1, 2, 1, 2]4
[-7]-7

입출력 예 설명

예 1 — 2는 두 짝, 1은 한 짝입니다.

예 2 — 1과 2는 두 짝씩이고 4만 한 짝입니다.

예 3 — 양말이 한 짝뿐이면 그것이 답입니다. 무늬 번호는 음수일 수도 있습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(socks: int[]) → int

제한 사항

  • 1≤1 \le socks.length ≤199,999\le 199{,}999 (항상 홀수)
  • −109≤-10^9 \le socks[i] ≤109\le 10^9
  • 한 값만 정확히 한 번, 나머지 값은 모두 정확히 두 번 나타납니다.

기대 복잡도

시간
O(N)
공간
O(1)

입출력 예

socks기대 출력
[2,2,1]1
[4,1,2,1,2]4
[-7]-7

힌트

힌트

XOR의 성질을 떠올려 보세요.

  • x ^ x = 0
  • x ^ 0 = x
  • 순서를 바꿔도 결과가 같습니다(교환·결합 법칙).

배열의 모든 값을 XOR하면 두 번 나온 값은 서로 지워지고 한 번 나온 값만 남습니다. 음수도 비트 단위로 똑같이 동작합니다.

복잡도 목표

원소마다 같은 값이 몇 개인지 배열 전체를 다시 세면 O(N2)O(N^2)으로 시간 초과입니다. XOR 한 번 훑기로 O(N)O(N) 시간, O(1)O(1) 공간에 풀 수 있습니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251124 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.