Jenikeju

풀이

주어진 가로수 위치를 배열에 넣었을때 가로수 시작점은 배열의 첫번째값, 종료점은 배열의 마지막값 이다

1. 가로수 위치를 배열에 넣는다.

2. 가로수와 가로수의 간격을 구해서 배열에 넣는다

3. 구한 간격들의 최소공배수를 구한다.

-> 시작점에서 최소공배수를 계속 더해서 도착점까지 갔을때 가로수의 위치가 모든 간격이 같은 가로수 위치가 된다.

-> 시작점부터 최소공배수를 더해가고, 더한값이 배열에 존재하는지 셌는데 시간초과떴다..

-> 간격이 최소공배수보다 작거나 같다면 가로수를 설치하지 않아도된다.

4. 간격이 있는 배열의 총합을 최소공배수로 나누고 배열의 갯수를 빼면 설치해야 하는 가로수의 수가 나온다.

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()!)!
var trees = [Int]()
var treeDistances = [Int]()
var gcd1 = Int()
var needTreeCount = 0

for i in 0..<count {
    var tree = Int(readLine()!)!
    trees.append(tree)
    if i > 0 {
        treeDistances.append(trees[i] - trees[i-1])
    }
}
var sortedDistances = treeDistances.sorted(by: <)

if sortedDistances.count == 1 {
    gcd1 = sortedDistances.first!
} else if sortedDistances.count == 2 {
    gcd1 = gcd(num1: sortedDistances[1], num2: sortedDistances[0])
} else {
    gcd1 = gcd(num1: sortedDistances[1], num2: sortedDistances[0])
    for i in 2..<sortedDistances.count {
        gcd1 = gcd(num1: sortedDistances[i], num2: gcd1)
    }
}
var sum = sortedDistances.reduce(0, +)
print((sum / gcd1) - sortedDistances.count)

풀이

1. 분모의 최소공배수를 구한다.

2. 최소공배수에서 분모를 나눈값을 분자에 곱한다

3. 분자들을 더한다

4. 분자와 분모의 최대공약수를 구하고 나눈다 

import Foundation

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

let input1 = readLine()!.split(separator: " ").map{ Int(String($0))! }
var upNum1 = input1[0]
var downNum1 = input1[1]

let input2 = readLine()!.split(separator: " ").map{ Int(String($0))! }
var upNum2 = input2[0]
var downNum2 = input2[1]

var gcd = Int()

if downNum1 > downNum2 {
    gcd = gcd(num1: downNum1, num2: downNum2)
} else {
    gcd = gcd(num1: downNum2, num2: downNum1)
}
var lcm = downNum1 * downNum2 / gcd

upNum1 = upNum1 * (lcm / downNum1)
upNum2 = upNum2 * (lcm / downNum2)

gcd = gcd(num1: lcm, num2: upNum1 + upNum2)
print((upNum1 + upNum2) / gcd)
print(lcm / gcd)

풀이

유클리드 호제법 이용

import Foundation

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

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

var num1: Int64 = Int64(nums[0])!
var num2: Int64 = Int64(nums[1])!

if num1 > num2 {
    print(num1 * num2 / gcd(num1: num1, num2: num2))
} else {
    print(num1 * num2 / gcd(num1: num2, num2: num1))
}

풀이

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

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]))
    }
}

풀이

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: " "))