Jenikeju

풀이

진법 변환 문제의 알고리즘 순서를 역순으로 하면 된다.

1. 0...35 까지 Dictionary에 저장한다. [Int: String]

2.정수 N의 자릿수를 구한다. ( B를 i만큼 곱하고 B^i >= N 인  i를 구함)

3. 각 자리수에서  N / B^j 한 후 배열에 저장 (  j 는 0..< i )

4. Dictionary에 대입해서 문자열로 변환 후 출력

import Foundation

var inputs = readLine()!.split(separator: " ").map{ Int64(String($0))}
var number = inputs[0]!
var rad = inputs[1]!
var strArr = [String]()
var count = 0
var num: Int64 = 1
var dict = [Int: String]()

while num <= number {
    num = num * rad
    count += 1
}
var arr = [Int64]()

for i in 0...35 {
    var num = 55
    if i >= 10 {
        dict[i] = String(UnicodeScalar(num+i)!)
    } else {
        dict[i] = String(i)
    }
    
}

for i in 0..<count {
    var num1: Int64 = 1
    for j in i+1..<count {
        num1 = num1 * rad
    }
    if num1 > number {
        arr.append(0)
        continue
    } else {
        arr.append(number / num1)
        number = number - ((number / num1) * num1)
    }
}

strArr = arr.map{ dict[Int($0)]!}
print(strArr.joined(separator: ""))

풀이

1. A:10, B:11, .... , Z: 35 를 Dictionary에 저장한다.

2. B진법으로 주어진 N을 배열에 넣는다.

3. 각 자리마다 Int 변환이 되면 숫자 그대로 변환, 변환이 되지 않으면 Dictionary에 대입해서 숫자로 변환한다.

4. 각자리 진법 변환 후 합산한 결과 출력

진법 변환 후 합산 

ex) 2진법 1010 을 10진법으로 변환할때 [1, 0, 1, 0] 으로 저장

(2^3  x 1) + (2^2  x  0) + (2^1  x 1) + (2^0 x 0)  = 8 + 0 + 2 + 0 = 10

import Foundation

var inputs = readLine()!.split(separator: " ").map{ String($0)}
var number = Array(inputs[0]).map{ String($0) }
var rad = Int(inputs[1])!
var result = 0
var dict = [String: Int]()

for i in 10...35 {  // Dictionary에 A:10,....,Z:35 저장
    var num = 55
    dict[String(UnicodeScalar(num+i)!)] = i
}

for i in 0..<number.count {
    var n = number.count - i - 1
    var num1 = Int()
    if Int(number[i]) == nil {  // 알파벳이면 숫자로 변환, 숫자면 그대로 숫자변환
        num1 = dict[number[i]]!
    } else {
        num1 = Int(number[i])!
    }
    var num2 = 1
    for j in 0..<n {
        num2 = num2 * rad
    }
    result = result + ( num2 * num1)
}

print(result)

풀이

입력된 N의 제곱근을 정수로 변환해서 출력한다.

이 문제를 처음 봤을때, N의 최댓값이 21억인것을 보고, 배열과 for반복문을 이용하지 않고 단순히 계산으로 풀어야 한다는걸 알았다.

규칙을 찾는 중 n= 1 부터 4까지 했을때,

n = 1  정답: 1

• 1번 -> (1)

n = 2 일때 정답: 1

• 1번 ->  (1, 1)
• 2번 ->  (1, 0)

n = 3 일때 정답: 1

• 1번 -> (1, 1, 1)
• 2번 -> (1, 0, 1)
• 3번 -> (1, 0, 0)

n = 4 일때 정답: 2

• 1번 -> (1, 1, 1, 1)
• 2번 -> (1, 0, 1, 0)
• 3번 -> (1, 0, 0, 0)
• 4번 -> (1, 0, 0, 1)

여기까지 직접 찾았을땐, n의 제곱근이 정답일 줄 몰랐는데 n = 9 일때 창문의 수가 3개이고 ,예제 입력 중 24를 입력했을때 √24 = 4.xx 인데 4인걸 보고 알았다.

import Foundation

var num = Double(readLine()!)!

print(Int64(sqrt(num)))

풀이

1. 2부터 주어진 수 N까지의 소수를 찾는다.

2. 반복문을 통해 2부터 N / 2 까지 파티션 수 찾아서 갯수 출력한다.

처음에 Set, Dictionary 여러가지 사용을 해봤는데 계속 시간초과가 떴다.

<시간초과가 뜬것 중 하나의 코드>

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()!)!
    var set = Set<Int>()
    var result = 0
    
    for j in 2..<num {
        var sub = num - j
        if set.contains(j) {
            continue
        } else {
            if isPrimeNum(num: j) && isPrimeNum(num: sub) {
                set.insert(j)
                set.insert(sub)
                result += 1
            }
        }
    }
    print(result)
}

소수 판별하는법

1. 정수 N을 2부터 N-1까지 나눠서 나누어 떨어지지 않으면 정수 N은 소수다. ( O(n) )

2. 정수 N을 2부터 N / 2 까지 나누어 떨어지지 않으면 정수 N은 소수다 .( 1/2N -> O(n) )

3. 정수 N을 2부터 √N 까지 나누어 떨어지지 않으면 정수 N은 소수다. ( O(√N) )  ** 제일 효율적이다 **

정수 N까지의 소수들을 구할 때 for i in 2..<N 까지 3번을 이용해서 소수를 구했었는데, 이게 시간초과의 원인이 되었던것 같다.

소수인지 판별하고, 소수들을 구할때는 에라토스테네스의 체 를 이용했다

에라토스테네스의 체

1. 정수 N이 주어졌을 때, 1부터 N까지 나열한다.

2. 1은 지운다.

3. i = 2 , i부터 √N 까지 i의 배수를 지워나간다. (i 는 제외한다.)

4. 더이상 지울 수 없을 때 까지 지운다.

예시)

18까지의 소수를 구할 때 √18 = 4.24264068712...

1. 1을 지운다

2.  2를 제외한 2의 배수를 지운다.

3.  3를 제외한 3의 배수를 지운다.

4.  4를 제외한 4의 배수를 지운다.

5. 나머지남은 수의 배수는 정수 N보다 크기 때문에 스킵

-> 2부터 18까지의 소수는 2, 3, 5, 7, 11, 13, 17

에라토스테네스의 체 알고리즘의 시간복잡도는  O(NloglogN)으로 선형시간에 가깝다.

하지만 많은 메모리가 필요하기 때문에, 10억이상의 소수를 찾는 매우 높은 수 에서는 사용하기 어렵다.

<정답 코드>

import Foundation

func primeNums (num: Int) -> [Int] {
    var arr = Array(0...num) // 정수 num까지 나열
    var count = Int(sqrt(Double(num))) + 1
    arr[1] = 0  // 1을 지운다.
    for i in 2..<count {    //정수 num의 제곱근까지 배수를 지운다.
        if arr[i] != 0 {
            var idx = 2
            while idx * i <= num {
                arr[idx * i] = 0
                idx += 1
            }
        }
    }
    return arr
}

let count = Int(readLine()!)!

for i in 0..<count {
    var num = Int(readLine()!)!
    let set = primeNums(num: num)
    var result = 0
    
    for j in 2...num / 2 { 
        let sub = num - j
        if set[j] != 0 {
            if set[sub] != 0 {
                result += 1
            }
        }
    }
    print(result)
}

제곱근까지 반복한이유

예시) 20의 약수

• 1 x 20 = 20
• 2 x 10 = 20
• 4 x 5 = 20
• 5 x 4 = 20
• 10 x 2 = 20
• 20 x 1 = 20

이렇게 나타냈을때 1 x 20 = 20  <=> 20 x 1 = 20 으로 대칭 구조를 이루고있다.

따라서 √20 = 4.472135955 으로 4 이후로 같은 수식이 이어지므로 제곱근 까지 반복해 소수 판별을 하였다.

풀이

주어진 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))
}