[자료구조] Set과 Array중에 Set이 왜 더 빠른걸까?

⚫️ 이 글을 작성하는 이유

아주 기초적인 문제를 풀다가, 시간초과가 발생했다. 아주 기초적인 것을 내가 간과하고 풀었기 떄문! 꼭 기억해두기 위해서 포스팅을 작성한다.

▪️ 백준 1181번 - 단어정렬 문제

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

이 문제를 풀면서 무슨 문제가 있었냐구??? 

바로, 시간초과를 마주쳐버린 것! 아무리 살펴봐도, 이유는 array를 사용해서 '중복처리'를 해주는 과정에서 시간초과가 난 것 같았다.

▪️ 시간초과 코드를 보자 -> Array를 사용

import Foundation

let n = Int(readLine()!)!
var words = [String]()
for _ in 0..<n {
    let temp = readLine()!
    if !words.contains(temp) {
        words.append(temp)
    }
}

let sortArr = words.sorted {
    if $0.count == $1.count {
        return $0 < $1
    } else {
        return $0.count < $1.count
    }
}

for word in sortArr {
    print(word)
}

문제에서 단순히 결과를 출력할 때 중복을 제외해달라고 했다. 그래서 input에서 입력을 받을 때, contains 메서드를 사용해서 존재하지 않을 경우에만 words 배열에 append 해주는 방식을 채택했다. (이 방법을 사용한 별다른 이유는 없다. 그냥 생각난 그대로 구현해낸것!)

문제를 읽고 무작정 구현하지 않기로 다짐했는데, 쉬운문제라고 너무 무시했나보다 ㅠㅠ 앞으로 꼭 문제를 읽고 냅다 코드를 치지 말고 생각을 거친 후 코드를 작성하자....

▪️ 맞은 코드를 보자. -> Set 사용

import Foundation

let n = Int(readLine()!)!
var words = Set<String>()
for _ in 0..<n {
    words.insert(readLine()!)
}

let sortArr = words.sorted {
    if $0.count == $1.count {
        return $0 < $1
    } else {
        return $0.count < $1.count
    }
}

for word in sortArr {
    print(word)
}

코드는 동일하지만, words 를 자료구조 Set을 활용했다. Set은 집합이기 때문에 중복은 알아서 담기지 않는다는 성질을 이용하기 위해서다. 물론, 처음 코드를 작성할때 set으로 하면 자동 중복처리가 되니까~ 하고 생각하긴 했지만, 그냥 append가 더 편하기 때문에 냅다 append를 갈겼던것이다. 역시나 Set을 이용해야했어.... 왜?

array와 set 두개 모두 데이터를 저장할 수 있는 자료구조이다. 근데 왜 Set이 더 빠른걸까?

 

⚫️ 구조 살펴보기

▪️ Set의 구조 살펴보기

Set에 데이터를 저장하는 순서는 다음과 같다. 

1. 저장할 값의 hash값 구하기
2. hash값에 해당하는 공간 (bucket)에 값을 저장함
   • 저장하고자 하는 해시값에 해당하는 bucket에 저장하기 때문에 순서가 없다. 즉, index가 없다. 
   • 해시값에 기반하여 저장하기 때문에 중복값이 존재할 수 없다.
   • 해시값 기반으로 저장하기 때문에 look up이 빠르다. (set의 길이와 상관 없이 데이터에 대한 단순 해시값을 보고 bucket을 확인하면 되기 때문에)

▪️ Array 의 구조 살펴보기

Array는 일정 크기의 연속된 메모리에 데이터들을 '순차적'으로 저장할 수 있는 자료구조이다. 

⚫️ 그래서 Set이 더 빠른 이유는? 시간초과가 난 이유는?

자료구조에 대해서 조금이나마 공부를 해봤으면, hash가 빠르다는 것은 모두 알고 있을 것이다. set은 array와 다르게 hash를 기반으로 데이터가 저장되고 조회되기 때문에 set이 더 빠르다.

위 코드에서 다른점은 array에서 contain하는 과정의 유무이다. 

Array에 append 하는것도 O(1), set에 insert하는 것도 O(1)이지만, contains 하는 과정에서 확연히 차이가 난다. 
Array에서 특정 값이 있는지 확인하는 Contains 메서드는 O(N)의 시간복잡도를 갖는다. 배열에서는 원하는 데이터가 포함되어있는지 여부를 확인하기 위해서 선형탐색을 진행하면서 N만큼 검색을 진행하기 때문이다. 그래서 더 많은 시간이 걸렸고, 시간초과가 난 것이다.

Set에서도 contains메서드를 똑같이 이용할 수 있다. 하지만, 앞서 말했듯, hash값을 기반으로 데이터를 검색하기 때문에 set에서 contains 해서 특정 값을 탐색하는 것은 해시 충돌이 일어나지 않는 한, O(1)밖에 걸리지 않는다. 

set이 해시함수를 사용하기 때문에 더 빠르다고 하는데, 해시함수가 뭔지 더 궁금하면 아래 참고자료를 살펴보자.

https://analytics4everything.tistory.com/m/180 

Set, Dict의 자료구조가 검색이 빠른 이유? hash 함수