Set을 잘 쓰자.

옛 말 틀린거 하나 없다.

머리가 멍청하면 몸이 고생한다는 말 .. 완전 TRUE

 

이 글이 과연 알고리즘 카테고리에 들어가야 하는지 .. Swift 카테고리에 들어가야 하는 지 한 3초 고민했지만 .. 그냥 알고리즘에 넣었음 .. ㅇㅉ 내 공간임 .. (아무도 뭐라고 안함 ㅇㅋㅇㅋ.)

 

그래서 왜 Set을 써야 하는지 썰 푼다. ㅇㅇ 

백준 알고리즘 문제를 풀다가. 2480번: 주사위 세개 문제를 풀게 되었음. 근데 문제가 쉬운 것임? ㅋ ㅋ (당연함. 아직 단계2 조건문임.) 신나서 또 풀었음. 

 

문제는 대충 이랬음.

문제 링크임 

문제 요약 

입력) 3개의 숫자가 빈칸을 사이에 두고 각각 주어진다. ex, 6 4 8
출력) 첫째 줄에 게임의 상금을 출력한다.

조건) 3개의 숫자 중 같은 숫자가 있다면 그것에 맞게 상금 계산 / 3개 다 다른 숫자라면 제일 큰 숫자로 상금 계산

 

 

근데 .. 코드가 제법 긴 것임. 

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }

let a = input[0]
let b = input[1]
let c = input[2]

if (a == b) && (b == c) {
    print(10000 + a * 1000)
} else if (a == b) {
    print(1000 + a * 100)
} else if (a == c) {
    print(1000 + a * 100)
} else if (b == c) {
    print(1000 + b * 100)
} else {
    if a > b && a > c {
        print(a * 100)
    } else {
        if b > c { print (b * 100 ) }
        else { print (c * 100) }
    }
}

내가 제출한 코드임.

 

근데 문제가 쉬운데 이렇게 코드가 좀 .. 더럽다고?

라는 생각에 다른 사람들은 어떻게 풀었나 찾아봤음.

 

그리고 충격을 먹음.

let values = readLine()!
    .split(separator: " ")
    .map { Int($0)! }
    .sorted(by: >)

let set = Set<Int>(values)

if set.count == 3 {
    print(values[0] * 100)
} else if set.count == 2 {
    print(1000 + values[1] * 100)
} else {
    print(10000 + values[0] * 1000)
}

이런 풀이가 있는 것임.

와싀.

 

코드를 뜯어보면,

- 입력값을 " "로 구분해서 받고 문자열 배열을 map 함수로 Int로 바꿈 -> ㅇㅋ. 여기까진 나도 함.

- 그리고 그걸 sorted 했음. -> 아 생각 못함 ㅈㅅ 

=> 그러면 여기까지 했을 때 입력 받은 숫자 3개가 큰 순서대로 정렬되어 있겠지? 

*왜 큰 순서로 정렬을 했는가 -> 세개의 숫자가 모두 다르다면 큰 숫자로 계산을 하기 때문에. 

 

- 그리고 이제 Set을 사용함 -> 대가리 빡빡침. 난 아직 미물이라는 것을 다시 한번 느낌.

그래서 알아보는 Set이 무엇인가. (이제서야 이 글의 본론이 나옴)

 

셋 .. 하나 둘 셋 .. 은 아니고 .. ㅈㅅ ..

간단명료하게 말하자면, Set은 집합이라고 생각하면 된다.

 

Set 

• 정렬되지 않은 컬렉션
• 배열과 다르게 중복 요소를 허용하지 않는다.
• 해시를 통해 값을 저장하기 때문에 배열에 비해서 검색 속도가 빠르고, 저장되는 자료형은 Hashable 프로토콜을 준수하고 있어야 한다.
• Swift는 타입에 민감하므로 저장되는 자료형은 모두 동일한 자료형이어야 한다.

Set 생성

var set1 = [1, 5, 3, 2, 1] // Set이 아닌 배열로 추론됨
 
// 1. 타입 Annotation으로 생성하기
var set2: Set<Int> = []
 
// 2. 생성자로 생성하기
var set3 = Set<Int>()

 

Set은 배열과 동일하게 []로 생성는데, 이렇게 생성하면(= 타입 추론으로 생성하면) 배열로 추론되므로 명시적으로 선언해야 한다.

 

Set은 Hashable 프로토콜을 채택한 자료형만 저장할 수 있으므로 Any를 자료형으로 선언할 수 없다. 

 

Set 요소 확인

var set1: Set<Int> = [1, 2, 5, 0]
 
let count: Int = set1.count // 4
let isEmpty: Bool = set1.isEmpty // false

Set이 비었는지 확인하는 방법은 배열과 마찬가지로 .isEmpty를 통해서 확인할 수 있다.

 

set1.contains(1) // true
set1.contains(10) // false

특정 요소가 포함되었는지 확인하는 방법 역시 배열과 마찬가지로 contains() 메서드를 사용할 수 있다.

 

여기서 배열과 다른 점은

Set은 딕셔너리와 마찬가지로 해시로 구현되어 있기 때문에 해시 충돌이 일어나지 않는다면 시간 복잡도가 O(1)만큼만 걸린다. 그래서 배열보다 빠르게 처리될 수 있다.

 

Set 값 추가 및 삭제

값 추가

var set1: Set<Int> = [1, 2, 5, 0]
 
// 1. insert : 값을 추가하고, 추가된 결과를 튜플로 리턴 (중복이면 false, 추가된 값)
set1.insert(1) // (false, 1)
set1.insert(10) // (true, 10) 
 
// 2. update : 값이 존재하지 않으면 추가 후 nil 리턴, 존재할 경우 덮어쓰기 후 덮어쓰기 전 값 리턴
set1.update(with: 1) // Optional(1)
set1.update(with: 120) // nil

insert() 와 update() 메서드 모두 upsert(= insert + update) 작업을 하지만 결과 값의 차이가 있다.

 

값 삭제

// 1. remove() : 한 가지 요소 삭제할 때 사용, 삭제 후 삭제한 값 return (없는 요소 삭제 시 nil 리턴)
set1.remove(1)              // Optional(1)
set1.remove(10)             // nil
 
// 2. removeAll() : 전체 요소 삭제
set1.removeAll()

 

앞서 Set은 집합이라고 말했기 때문에 집합의 포함관계 등도 확인할 수 있다.

 

부분 집합 : isSubSet(of:)

var set1: Set<Int> = [1, 2, 5, 0]
var set2: Set<Int> = [1, 2]
 
set1.isSubset(of: set2) // false 
set2.isSubset(of: set1) // true

set1이 set2를 포함하고 있는 관계이므로 위와 같은 결과가 나온다.

 

상위 집합 : isSuperSet(of:)

var set1: Set<Int> = [1, 2, 5, 0]
var set2: Set<Int> = [1, 2]
 
set1.isSuperset(of: set2)               // true
set2.isSuperset(of: set1)               // false

 

서로수 집합 : isDisjoint(with:)

var set13: Set<Int> = [1, 2, 5, 0]
var set14: Set<Int> = [1, 2, 5, 0]
var set15: Set<Int> = [3, 7, 9, 10]
 
set13.isDisjoint(with: set14)               // false (같은 집합 : 모든 요소가 동일한 집합)
set15.isDisjoint(with: set13)               // true  (서로수 집합 : 모든 요소가 다른 집합)

두 집합이 모두 다를 경우에 (= 서로수 집합일 때) true를 반환한다.

 

Set 연산

 

그래서 .. 다시 돌아와서 알고리즘 문제 해결 코드를 보면

let set = Set<Int>(values)

입력 받은 값에 대해서 Set으로 선언하여 중복되는 값이 없도록 저장을 했다.

= 중복된다면 그 값만 저장된다.

= 같은 눈이 나온 주사위의 값을 의미한다.

 

✅ 그러므로 그 값이 3개라면 모두 다른 눈이 나온 것이므로 그 중 0번째 인덱스는 (앞에서 sorted() 메서드를 통해 정렬을 했으니) 가장 큰  수이다.

✅ 2개 또는 1개라면 같은 수가 나온 것이므로 그에 맞게 상금을 계산하면 된다. 

✅ 2개 -> 3개 중 2개가 같은 눈

✅ 1개 -> 3개 모두 같은 눈 

 

.. 그래서 훨씬 시간복잡도고 줄어들고 코드도 간결해진 것을 확인할 수 있다 ..

 

끝 ..

Set을 머리 속에 기억하자.