2개씩 나오는 숫자들 중 하나만 나오는 숫자 찾는 문제 + ⍺

이 알고리즘도 면접에서 단골 문제중 하나이다. 면접을 10군데가 안되게 봤었는데 2군데에서 토씨 하나 안 틀리고 이 문제를 물어봤다 😅

개인적으로 좋은 문제는 아니라고 생각하는 이유중 하나가, 알면 그냥 풀고 모르면 못 푸는 식의 문제라는 것이다. 그럼에도 불구하고, 변형 문제는 꽤 재밌는 편이다. 이진검색(투포인터?)을 활용하는 점이 꽤 인상깊기 때문이다. (덤으로 헷갈리기 쉬운 분할 정복)

그리고 Space Complexity가 알고리즘별로 천차만별로 다른 것도 흥미로운 요소 중 하나이다.

아무튼 재미있는 문제로 기억하고 있어 적어둔다.

2개씩 나오는 숫자중 하나만 나오는 숫자 찾기

Example Data:

arr = [1, 1, 2, 3, 2, 4, 5, 4, 5]

Ans is '3'

가장 Naive한 solution은 매 숫자 하나하나를 검사하는 것이다. 2중 for loop로 배열을 쭉 훑으면서 해당 숫자와 동일한 숫자가 나타나지 않는다면 그 숫자를 return할 수 있다.

2중 for loop를 돌기 때문에 Time Complexity는 무난하게 O(n^2) 이다.

하지만 한 번만 훑을 수 있다면 더 낫지 않을까? 이를테면 배열을 Sort한 후 배열을 돌게 된다면 for loop를 한 번으로 간소화시킬 수 있을 것이다.

이 경우 Time Complexity는 O(nlogn) , 즉 sorting만큼이 소요된다.

대부분은 “Hash를 이용하면 중복된 숫자를 쉽게 찾을 수 있어요!”라고 이야기할 것이다. 나 스스로도 그랬고. 이 경우 이상적인 Time Complexity는 O(n) 이고, Space Complexity도 O(n) 이다. 물론 해싱 방식에 따라서 쏠림 현상이 일어난다거나 하는 문제가 있을 수 있겠지만 보통은 그런 걱정은 배제해도 괜찮으니…

사실 해시 정도면 훌륭한 자료구조고 실무에서 많이 쓰는 방식이라서 난 이 정도만 되어도 좋다고 생각한다.

하지만 기가막힌 해답은 바로 XOR 비트연산을 이용해서 푸는 방법이다. 중복된 숫자끼리 XOR을 하면 0이 되니, 처음부터 마지막 숫자를 모조리 XOR 연산하면 한 번 나오는 숫자를 자연스럽게 확인할 수 있다.

for loop 한번만 타면 되니 Time complexity O(n) 에, XOR 담을 변수 하나만 있으면 되니 Space complexity O(1) 로 아주 완벽한 방법이다. 근데 실무에서 하등 쓸모도 없는거… 이 문제 풀 때 이외에 쓸 일이 있나? 심지어 모르면 못 푸는 유형이다. 그래서 나는 이 해답을 그렇게 좋아하지는 않음.

참고: GeeksforGeeks 에서도 이 문제를 다루고 있다.

Sabun: 2개씩 나오는 정렬된 숫자 배열에서 하나만 나오는 숫자 찾기

사골 문제라 그런지 변형 기출이 좀 있다.

Example Data:

arr = [1, 1, 2, 2, 3, 4, 4, 6, 6]

Ans is '3'

Naive한 방법으로는 처음부터 끝까지 읽어들이는 방법이 있다. 즉 O(n) 의 방법이 있는데…

여기서 핵심은 "이미 정렬된 배열” 이라는 것이다. 여기서 의문을 가져야 할 부분은 “과연 모든 배열을 다 읽을 필요가 있을까?” 라는 것이다. 즉 투포인터(이진검색)를 써서 접근할 수 있는 문제이다.

pseudocode를 쓰면 대충 아래와 같을 것이다.

1. l == r이면 exit
2. l+1 == r 이면 바로 정답 리턴
3. 가운데 지점 n = (l + r) / 2 를 찾고, arr[n] == arr[n+1] 인지 확인해본다.
=> 아니라면 하나만 나오는 숫자!
4. 아니라면 f(l, n)과 f(n+2, r)로 재귀호출 수행.
=> 사실 이것도 더 최적화가 가능한 게, (n-l)%2 == 0 이면 앞 배열은 굳이 안살펴봐도 되고,
   (n-l)%2 == 1 이면 뒷 배열은 굳이 안살펴봐도 된다. 짝수개의 숫자가 있다면 볼 필요가 없지...

시간복잡도 O(logn) 이 된다.

Sabun: 1 to N 숫자중 2번 나오는 숫자 찾기

GeeksforGeeks 에 비슷한 문제가 있으나, 조금 다르다. 나름 꽤나 유명한 문제인데, 사실 이 문제가 진국이라고 생각한다.

Example Data:

arr = [1, 2, 4, 3, 6, 5, 4]

ans is "4"

유사한 문제라서 앞 문제와 solution은 비슷하다. 2중루프로 array 훑기, sort 하기, hash table 만들기…

다만 여기서 유의할 것은 최대 숫자가 고정되어 있다는 점이다. 최대 숫자가 고정되어있기 때문에 아래와 같은 시도가 가능하다.

• count array를 만들어서 풀 수도 있을 것이다. (단 이 경우 space complexity가 작살이 남…)
• XOR: 1 to N까지 XOR한 값과, 주어진 list를 XOR 한번 더 하면 2번 나오는 숫자를 찾을 수 있다. 그 숫자 혼자서 3번 XOR이 되기 때문이다.

Sabun: 위 유형에서 “정렬" 추가

또 다른 유형으로는, 아예 sorted된 1~N 숫자들 중에서 2번 나오는 숫자를 찾는 것이다.

Example Data:

arr = [1, 2, 3, 4, 4, ..... 999, 1000]

ans is "4"

위에서 이야기했던 문제처럼 모든 배열을 읽을 필요가 없다. 전체 숫자의 개수와 최대값을 알고 있으니, 분할정복을 수행하면 어떤 범위에 2번 나오는 숫자가 있을지 알 수 있기 때문에, O(logn) 에 찾을 수 있다.

Sort의 중요성과 모든 값을 읽지 않고 푸는(혹은 투포인터) 자료구조, 혹은 알고리즘에 익숙한지를 묻는 좋은 문제 유형인 것 같다.

쓰는 자료구조도 그닥 안 복잡해서(세그먼트 트리 같은거에 비하면 상양반…) 1시간 컷으로 물어보기 딱 좋음. 괜히 면접 단골 알고리즘이 된 게 아니다.

해시는 무적이다 어쩌고 짤로 만들기 귀찮다...

... 그리고, Sort와 해시는 무적이다. 실무는 말할것도 없고, 어디에 쓰든 중간은 간다. 꼭! 쓰자.