[알고리즘] Swift -백준 #4158 (CD)

문제링크

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

4158번: CD

 

문제

상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. CD의 번호는 십억을 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0 0이 주어진다.

상근이와 선영이가 같은 CD를 여러장 가지고 있는 경우는 없다.

출력

두 사람이 동시에 가지고 있는 CD의 개수를 출력한다.

 

 

---

분석

1) 집합 이용

상근이n)와 선영이(m)의 씨디의 수를 받는다.

0.0이 나올때까지 계속 반복하여 숫자를 받는다. 받으면서 n까지는 상근이의 세트에 넣고 나머지는 선영이의 세트에 넣는다

교집합을 구하여 출력한다

let num = readLine()!.split(separator: " ").map{ Int($0) }
var seta = Set<Int>()
var setb = Set<Int>()

while true {
    let cd = readLine()!.split(separator: " ").map{ Int($0)! }
    let a = cd[0]
    if a == 0 && cd[1] == 0 {
        break
    }
    
    if seta.count != num[0]!  {
        print(a)
        seta.insert(a)
    } else {
        setb.insert(a)
    }
}

var result = Set<Int>()
result = seta.intersection(setb)
print(result.count)

 

2) 딕셔너리 이용

키를 씨디번호로 넣고 밸류값을 0으로 추가해준다 그리고 키가 있다면 그 키를 삭제한다 이떄 (삭제할때) 카운트를 +1 해준다

let num = readLine()!.split(separator: " ").map{ Int($0) }
var dict: [Int: Int] = [:]

var count = 0
while true {
    let cd = readLine()!.split(separator: " ").map{ Int($0)! }
    let a = cd[0]
    if a == 0 && cd[1] == 0 {
        break
    }
    
    if !dict.keys.contains(a) {
        dict[a] = 1
    } else {
        count += 1
    }
}
print(count)

 

 

집합과 딕셔너리에 삽입하는 시간복잡도는 O(1) -> n번 반복하므로 O(n)

전체시간복잡도는 O(n)이겠지

최대 입력이 십억!!!이었군!!!!

그래서 시간초과..!

 

입력은 여러 개의 테스트 케이스로 이루어져 있다!!!!!

테스트 케이스가 여러개

그래서 마지막에 0, 0으로 끝내주는 거였음 ..

3 3
1
2
3
1
2
4

이러한 케이스가 짱많이 나온다는 얘기였음

위에 작성한 코드는 그냥 한개의 테스트케이스를 가지고 한거여서 출력이 제대로 나온 거였다

근데 또 집합을 두개를 가지고 하니까 시간초과가 나온다 (진짜 너 힘든 아이구나)

let fIO = FileIO()
var dict: [Int: Int] = [:]

while true {
    let a = fIO.readInt()
    let b = fIO.readInt()
    if a == 0 && b == 0 {
        break
    }
    
    var seta = Set<Int>()
    for _ in 0..<a {
        let num = fIO.readInt()
        seta.insert(num)
    }
    
    var setb = Set<Int>()
    for _ in 0..<b {
        let num = fIO.readInt()
        setb.insert(num)
    }
    var result = Set<Int>()
    result = seta.intersection(setb)
    print(result.count)
}

그래서 그냥 하나만 만들어주고 포함되어있는 수를 더해주었다.

드디어... 성공

 

풀이 

FileIO() = 라이노님

let fIO = FileIO()
var dict: [Int: Int] = [:]

while true {
    let a = fIO.readInt()
    let b = fIO.readInt()
    if a == 0 && b == 0 {
        break
    }
    
    var count = 0
    var set = Set<Int>()
    for _ in 0..<a {
        let num = fIO.readInt()
        set.insert(num)
    }
    
    for _ in 0..<b {
        let num = fIO.readInt()
        if set.contains(num) {
            count += 1
        }
    }
    print(count)
}

 

결과

 

 

문제를 잘 읽자!

테스트케이스를 잘 생각하자!