Jenikeju

풀이

유클리드 호제법 이용해서 구한다

import Foundation

func gcd(num1: Int, num2: Int) -> Int {
    if num2 == 0 {
        return num1
    } else {
        return gcd(num1: num2, num2: num1 % num2)
    }
}

let count = Int(readLine()!)!

for i in 0..<count {
    var nums = readLine()!.split(separator: " ").map{ Int(String($0))!}
    if nums[0] > nums[1] {
        print(nums[0] * nums[1] / gcd(num1: nums[0], num2: nums[1]))
    } else {
        print(nums[0] * nums[1] / gcd(num1: nums[1], num2: nums[0]))
    }
}

최대공약수 GCD

두 자연수의 공통된 약수 중 가장 큰 수

ex) 30 과 45 의 최대공약수는 15

최소공배수 LCM

두 자연수의 공통된 배수 중 가장 작은 수

최소공배수 = 두 자연수의 곱 / 최대공약수

ex) 6과 10의 최소공배수는 30

유클리드 호제법

2개의 자연수 a,b에 대해 (a > b) a를 b로 나눈 나머지를 r이라 하면

a와 b의 최대공약수는 b와 r의 최대공약수와 같다

이 성질을 이용해,

b를 r로 나눈 나머지를 r0라 하고, r을 r0으로 나누는 과정을 반복해서 나머지가 0일때 

나눈수가 a와 b의 최대공약수가 된다. 

func gcd(num1: Int, num2: Int) -> Int {
    if num2 == 0 {
        return num1
    } else {
        return gcd(num1: num2, num2: num1 % num2)
    }
}

시간복잡도: O(logN)

풀이

1. 문자의 부분문자열을 Set에 저장

2. Set.count 출력

import Foundation

var strArr = readLine()!.map{String($0)}
var strSet = Set<String>()

for i in 0..<strArr.count {
    var str = ""
    for j in i..<strArr.count {
        str = str + strArr[j]
        strSet.insert(str)
    }
}
print(strSet.count)

<시간초과>

import Foundation

var str = readLine()!.map{String($0)}
var strSet = Set<String>()
var length = 0

for i in 0..<str.count {
    var count = str.count - i
    for j in 0..<count {
        let str = str[j...j+length].joined(separator: "")
        strSet.insert(str)
    }
    length += 1
}
print(strSet.count)

처음 시간초과가 났을때 부분문자열을 만드는 과정이 문제라 생각했었다

부분문자열의 길이를 1씩 증가시켜 각 인덱스마다 부분문자열을 추출하는 방식을 사용했다가,

더 간단하게 부분문자열을 추출하는 방법이 있어서 그 방법을 사용했지만

둘 다 2중 for문을 사용해서 결국 O(n^2) 라 생각한다

아마 문제는 배열에서 범위 추출하는 과정이 문제라 생각이 든다

배열에 대해서 따로 정리를 해봐야겠다

입력

1. 각 집합을 Set에 저장한다

2. Set.subtracting 으로 차집합을 구한다

3. 각각 구해진 차집합을 합한다 union

import Foundation

let counts = readLine()!.split(separator: " ").map{ Int(String($0))! }
var set1 = Set(readLine()!.split(separator: " ").map{Int(String($0))!})
var set2 = Set(readLine()!.split(separator: " ").map{Int(String($0))!})

var subSet1 = set1.subtracting(set2)
var subSet2 = set2.subtracting(set1)

print(subSet1.union(subSet2).count)

1. N개 이름을 set에 저장하고, M개 이름을 set에 저장

2. 두개의 Set의 교집합 출력

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int(String($0))!}
var set1 = Set<String>()
var set2 = Set<String>()

for i in 0..<inputs[0] {
    set1.insert(readLine()!)
}
for i in 0..<inputs[1] {
    set2.insert(readLine()!)
}
var result = set1.intersection(set2).sorted{ $0 < $1}
print(result.count)
for i in result {
    print(i)
}

풀이

1. 소지하고 있는 숫자와 숫자의 갯수를 Dictionary에 저장

2. 주어진 숫자배열을 Dictionary에 대입 후 출력

import Foundation

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

let getNum = Int(readLine()!)!
var getCards = readLine()!.split(separator: " ").map{ Int(String($0))! }

for i in cards {
    if dict[i] == nil {
        dict[i] = 1
    } else {
        dict[i] = dict[i]! + 1
    }
}

print(getCards.map{ (num: Int) -> String in
    if dict[num] == nil {
        return "0"
    } else {
        return "\(dict[num]!)"
    }
}.joined(separator: " "))

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

풀이

1. Dictionary에 포켓몬번호와 이름 저장

2. Array에 포켓몬번호 index에 맞게 이름 저장

3. 포켓몬이름이 주어지면 Dictionary에서 value, 번호가 주어지면 Array에서 출력

Dictionary 단일로 저장하고 filter를 이용해 key값을 불러왔는데 시간초과가 떴다

더 줄이는 방법으로 아예 두가지 컬렉션으로 접근하는 방식을 이용했다

import Foundation

let inputs = readLine()!.split(separator:" ").map{ Int(String($0))!}
var pokemonsDict = [String: Int]()
var pokemonsArr = Array(repeating: "", count: inputs[0]+1)

for i in 1...inputs[0] {
    let pokemon = readLine()!
    pokemonsDict[pokemon] = i
    pokemonsArr[i] = pokemon
}

for j in 0..<inputs[1] {
    var quest = readLine()!

    if Int(quest) == nil {
        print(pokemonsDict[quest]!)
    } else {
        print(pokemonsArr[Int(quest)!])
    }
}