Jenikeju

풀이

주어진 n을 n부터 1씩 증가시키면서 소수 판별을 한다

2를 제외한 모든 소수의 일의자리는 1, 3, 7, 9 라서 1씩증가시켜도 금방 찾을꺼라 시간이 오래걸리지 않을꺼라 생각했다.

소수인지 판별할때, 2부터 N의 제곱근까지 약수인지 확인해보았다.

import Foundation

func isPrimeNum (num: Int) -> Bool {
    if num < 2 {
        return false
    } else {
        var idx = 2
        while idx * idx <= num {
            if num % idx == 0 {
                return false
            } else {
                idx += 1
            }
        }
        return true
    }
}

let count = Int(readLine()!)!

for i in 0..<count {
    var num = Int(readLine()!)!
    while !isPrimeNum(num: num) {
        num += 1
    }
    print(num)
}

풀이

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

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

최대공약수 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)