Lv.1arraybit-manipulationmath
짝 없는 양말 한 짝
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
빨래를 개다 보니 양말 무늬 번호가 배열 socks로 정리되었습니다. 모든 무늬는 정확히 두 짝씩 있는데, 단 하나의 무늬만 한 짝뿐입니다.
짝이 없는 양말의 무늬 번호를 반환하세요. 양말은 아무 순서로나 놓여 있습니다.
입출력 예
| socks | result |
|---|---|
[2, 2, 1] | 1 |
[4, 1, 2, 1, 2] | 4 |
[-7] | -7 |
입출력 예 설명
예 1 — 2는 두 짝, 1은 한 짝입니다.
예 2 — 1과 2는 두 짝씩이고 4만 한 짝입니다.
예 3 — 양말이 한 짝뿐이면 그것이 답입니다. 무늬 번호는 음수일 수도 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(socks: int[]) → int
제한 사항
-
socks.length(항상 홀수) -
socks[i] - 한 값만 정확히 한 번, 나머지 값은 모두 정확히 두 번 나타납니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| socks | 기대 출력 |
|---|---|
[2,2,1] | 1 |
[4,1,2,1,2] | 4 |
[-7] | -7 |
힌트
힌트
XOR의 성질을 떠올려 보세요.
x ^ x = 0x ^ 0 = x- 순서를 바꿔도 결과가 같습니다(교환·결합 법칙).
배열의 모든 값을 XOR하면 두 번 나온 값은 서로 지워지고 한 번 나온 값만 남습니다. 음수도 비트 단위로 똑같이 동작합니다.
복잡도 목표
원소마다 같은 값이 몇 개인지 배열 전체를 다시 세면 으로 시간 초과입니다. XOR 한 번 훑기로 시간, 공간에 풀 수 있습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1124 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 3 | 판정만 |