01/24 [TIL] Swift, 백준 문제풀이

Swift

KeyPath

• 문자열 방식으로 속성에 간편하게 접근하기 위해서 사용한다.

Algorithm

패션왕 신해빈

리팩토링

• 같은 이름을 가진 의상은 존재하지 않으므로, 딕셔너리에 이름이 아닌 호출된 횟수만 저장해도 된다.

var input = Int(readLine()!)!

//1. 테스트 케이스를 입력받아 반복한다.
for _ in 0..<input {
    var dict: [String: Int] = [:]


    //2. n을 입력받는다.
    input = Int(readLine()!)!
    for _ in 0..<input {

        //3. 이름과 종류를 입력받고, 종류를 key에 저장한다. 이름은 중복될 수 없으므로, 횟수를 저장한다.
        let data = readLine()!.split(separator: " ").map { String($0) }
        let key = data[1]
        if dict.keys.contains(key) {
            dict[key]! += 1
        } else {
            dict[key] = 1
        }
    }

    //4. 딕셔너리의 종류들 간 조합의 수를 계산하고 1을 빼서 출력한다 (알몸인 경우 제외)
    let result = dict.values.map { $0 + 1 }.reduce(1, *) - 1
    print(result)
}
    /*
     3 -> 1 : 3가지
     hat headgear
     sunglasses eyewear
     turban headgear

     headgear = [hat, turban] -> 3
     sunglasses = [eyewear] -> 2
     -> 6 - 1 = 5
     */

주몽

리팩토링

• m의 최댓값은 10,000,000 (천만)이다.
• 하단에 조건이 하나 있다. 고유한 번호는 100,000보다 작거나 같다는 것이다.
• 그렇다면, 고유한 번호 100,000만을 두 번 더하면 200,000이 된다.
• 즉, 200,000보다 m이 더 크다면, 유효한 값옷을 만들 수 없다. 이런 조건을 추가하자.
• //1. n을 입력받는다. let n = Int(readLine()!)! //2. m을 입력받는다. let m = Int(readLine()!)! //3. 재료들을 입력받는다. var materials = readLine()!.split(separator: " ").map { Int($0) } //4. 모든 조합을 구하며, 합이 m 일 때에만 조합으로 취급한다. var result = 0 for i in 0..<n { for j in **i+1..<n** { guard let first = materials[i], let second = materials[j] else { continue } if first + second == m { result += 1 materials[i] = nil materials[j] = nil } } } //5. 나온 결과의 수를 계산하여 출력한다. print(result)

좋은 단어

리팩토링

• 6번 과정은 불필요한 과정이라는 것을 알게 되었다.
• 스택에 넣을 때마다 top을 검사하기때문에, 의미가 없다.

알고리즘

1. 문자열을 입력받는다.
2. stack에서 제일 위에 있는 단어를 꺼낸다.
3. 만약 동일하다면, 둘 다 제거한다.
4. 다르다면, push 한다.
5. 마지막에 Stack에 아무것도 남아있지 않다면, 좋은 단어이다.

//1. n을 입력받는다.
let n = Int(readLine()!)!
var result = 0
for _ in 0..<n {
    result += isGoodWord() ? 1 : 0
}
print(result)

func isGoodWord() -> Bool {
    var stack: [Character] = []

    //2. 만약 문자열의 길이가 홀수라면 0을 리턴한다. (무조건 좋은 단어가 아님)
    let string = readLine()!.map { $0 }
    if string.count % 2 != 0 { return false }

    // stack 연산으로, 같은 문자가 연속으로 나온다면 Pop 한다.
    for char in string {
        if stack.isEmpty {
            stack.append(char)
        } else {
            if stack.last! == char {
                stack.removeLast()
            } else {
                stack.append(char)
            }
        }
    }
    return stack.isEmpty
}

곱셈

문제 푸는 방법

• A와 B의 최댓값이 20억이므로, 반복문으로 문제를 풀 수 없게 된다.
• 곱하기 연산에 대한 시간복잡도를 줄여야하고, 오버플로우를 신경써야한다.

1. 시간복잡도를 줄이는 방법 → 수학적 개념 (지수 법칙)
   • 2의 8승 = 2의 4승 * 2의 4승
   • = 2의 4승 * 2의 2승 * 2의 2승 = 2의 4승 * 2의 2승 * 2의 1승 * 2의 1승
   • 각 결과를 변수에 담는다면, 시간 복잡도가 O(logN)이 된다.
2. 오버플로우를 줄이는 방법 → 정수론
   • 모듈러 연산에 대한 개념을 이용할 수 있다.
   • (a + b)%c = a%c + b%c
   • (a * b)%c = (a%c) * (b%c)
3. b가 홀수인 경우인 경우 처리 방법
   • 만약 b가 3이라면 a를 한 번 더 곱해주어야한다.
   • 코드 보면 더 이해가 쉬울 것임!

코드

let input = readLine()!.split(separator: " ").map { Int($0)! }
let (a, b, c) = (input[0], input[1], input[2])
print(go(a, b))

func go(_ a: Int, _ b: Int) -> Int {
    if b == 1 { return a % c }
    var result = go(a, b/2)
    result = result * result % c
    if b % 2 != 0 { result = result * a % c }
    return result
}

1

문제 푸는 방법

• 각 변수들의 범위를 보았을 때, 1이 21이상만 되어도 오버플로우가 발생한다.
• 이에 모듈러 연산의 법칙을 활용한다.
  • (A + B) % c == (A%C + B%C)%C 이다.
  • 계산 중 모듈러 연산을 하는 것과 계산 후 모듈러 연산을 하는 것이 동일함을 알 수 있다.
• 1로 이루어진 수를 만드는 방법
• var count = 1 while true { count = (count * 10) + 1 // 1 -> 11 -> 111 ... }

코드

while let input = readLine() {
    let n = Int(input)!
    var count = 1, result = 1

    while true {
        if count % n == 0 {
            print(result)
            break
        } else {
            count = (count * 10) + 1
            count %= n
            result += 1
        }
    }
}