자료구조,문자열,트리_백준_14425

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

14425번: 문자열 집합

 

문제 접근

1. 간단하게 nDict: [Character:[String]]을 선언하고, N만큼 reaLine()하여 Dictionary에 삽입한다.

2. mDict또한 마찬가지.

3. nDict의 요소들로 mDict를 검사하던, 그 반대던, 시간소요는 같을것이라고 생각했으므로, 큰 의미를 두지않고 탐색하였다.

4. 요소 검사는 해당 요소의 첫 글자를 통해서 다른 Dictionary에 접근해서 포함 여부를 확인한다.

 

틀린 코드

import Foundation

let nums = readLine()!.components(separatedBy: " ")
let n = Int(nums[0])!
let m = Int(nums[1])!

var sol = 0
var nDict = [Character:[String]]()
var mDict = [Character:[String]]()

for _ in 0..<n {
    let line = readLine()!
    if nDict[line.first!] == nil {
        nDict[line.first!] = []
    }
    nDict[line.first!]?.append(line)
}

for _ in 0..<m {
    let line = readLine()!
    if mDict[line.first!] == nil {
        mDict[line.first!] = []
    }
    mDict[line.first!]?.append(line)
}

for target in mDict {
    target.value.forEach({ a in
                          if nDict[target.key]?.contains(a) == true {
                              sol += 1
                          }
                         })
}
print(sol)

시간 초과 발생.

 

개선 1

굳이 Dictonary를 두개나 만들 필요가 없음.

//var mDict = [Character:[String]]()
var mArray = [String]()


/*
for word in mWord {
	if mDict[word.first!] == nil {
    	mDict[word.first!] = []
	}
	mDict[word.first!]?.append(word)
} */


for _ in 0..<m {
    let line = readLine()!
    mArray.append(line)
}

/*
for target in mDict {
            target.value.forEach({ a in
                guard let index = nDict[target.key]?.firstIndex(of: a) else { return }
                
                sol += 1
                nDict[target.key]?.remove(at: index)
                
            })
        }
*/

for target in mArray {
    if nDict[target.first!]?.contains(target) == true {
        sol += 1
    }
}

기존 : 주석 코드, 변경 : 주석이 아닌 코드

-> 별 의미 없었다. 하면서도 알 고 있었다.

 

개선 2

Set을 만들어 S집합을 만들고, insert 결과를 받는다.

.inserted가 false일 경우, S집합에 존재한단 것이므로, sol += 1 한다.

true일 경우, 새로운 요소가 nSet에 삽입된 것, 이는 원치 않는 결과를 초래 할 수 있으므로, 삭제한다.

import Foundation

let nums = readLine()!.components(separatedBy: " ")
let n = Int(nums[0])!
let m = Int(nums[1])!

var sol = 0
var nSet = Set<String>()


for _ in 0..<n {
    let line = readLine()!
    nSet.insert(line)
}

for _ in 0..<m {
    let line = readLine()!
    
    let result = nSet.insert(line).inserted
            if result == false {
                sol += 1
            } else {
                nSet.remove(line)
            }
    
}

print(sol)

 

회고

SideEffect를 잘 고려해야한다. 처음, inserted가 true일 경우를 확인하지 않아서, 문제가 해결되지 않았었다...!

Dictionary로 hash하는 것이 빠를 거라고 생각했는데, 다시보니 Collection순회와, 반복문이 있어서 전혀 빠르지 않다...!

다른 풀이한 분들은 

트리와 트라이? 를 사용한 것 같은데, 다른 언어 해독이 어려워서 ㅎㅎ,,, 보는것은 포기했다!