[Lesson 2] OddOccurrencesInArray

문제

---

 

코드

---

fun solution(A: IntArray): Int {
    var unpaired = 0
    for(e in A) {
        unpaired = unpaired xor e
    }
    return unpaired
}

 

 

풀이

---

fun solution(A: IntArray): Int {
    val sortedA = A.sorted()
    // i , i + 1 확인 -> 같음 -> +2 해서 확인
    // i, i+1 다름 -> sortedA[i] 출력 후 break
    // i + 1 >= A.size 이면 [A.size-1] 출력
    var i = 0
    while(i < A.size-1) {
        if(sortedA[i] == sortedA[i+1]) i += 2
        else {
            return sortedA[i]
        }
    }
    return sortedA[A.size-1]
}

시간 복잡도가 O(n^2) 으로 탐색됐다고 뜬다

아마 sort 연산 때문인 것 같다

sort 없이 pair로 풀어봐야겠다 

 

fun solution(A: IntArray): Int {
    val list = mutableListOf<Int>()
    for (e in A) {
        if (list.contains(e)) list.remove(e)
        else list.add(e)
    }
    return list[0]
}

이렇게 작성했더니 점수가 더 떨어졌다..ㅋㅋ

 

fun solution(A: IntArray): Int {
    val set = A.toList().groupingBy{ it }.eachCount().filter{ it.value == 1 }.keys
    return set.first()
}

groupingBy와 eachCount(), filter를 활용해서 작성해봤다.

 

 

점수가 더 떨어졌다🥲

 

결국 혼자 해결하지 못하고 gpt에게 물어봤다.

비트연산으로 쉽게 해결할 수 있더라

각 숫자를 XOR 연산을 하면 짝이 맞는 숫자는 모두 0이 되고, 결국 홀수 번 나타나는 숫자만 남게 됩니다. 이는 O(n) 시간 복잡도로 문제를 해결할 수 있는 방법입니다.

 

이 말을 들으니까 같은 숫자를 xor하면 0이 된다는 것이 기억났다.

1011 XOR 1011 = 0000

XOR은 입력이 같으면 0, 다르면 1이기 때문이다.

 

시간 복잡도가 눈에 띄게 줄었다..

비트연산에 대해서도 더 공부해야겠다😥