Jenikeju

문제 설명

풀이

1. [name: yearning] 의 Dictionary 생성

2. 사진마다 dict에 대입

3. 합산한 점수들을 출력

import Foundation

func solution(_ name:[String], _ yearning:[Int], _ photo:[[String]]) -> [Int] {
    var dict = [String: Int]()
    for i in 0..<name.count {
        dict[name[i]] = yearning[i]
    }
    var result = [Int]()
    
    for i in 0..<photo.count {
        var arr = photo[i]
        var points = arr.map{ (name: String ) -> Int in
                                if dict[name] == nil {
                                    return 0
                                } else {
                                    return dict[name]!
                                }                           
                           }
        result.append(points.reduce(0, +))
    }
    return result
}

문제 설명

풀이

1. player를 Dictionary에 선수 이름과, 순서를 입력한다.

2. callings 배열을 반복해서 부르는 선수의 순서를 차감하고, 앞의 순서의있는 선수의 순서를 증감

3. 바뀐 선수들의 순서 출력

Dictionary는 선수들의 현재 위치를 저장하기위해 선언했다.

처음에는 for문대신 while callings.count > 0  을 이용해 

callings.removefirst() 함수를 사용했는데 시간초과가 떴다.

array.removefirst() 함수의 시간복잡도는 O(n) 이므로 반복문 안에서 실행시켜서 O(n^2) 시간초과가 난듯 하다.

그래서 for문으로 바꿔 접근방식으로 바꿨다 

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var player = players
    var calls = callings
    var dict = [String: Int]()
    
    for i in 0..<player.count {
        dict[player[i]] = i 
    }
    for i in 0..<calls.count {
        var call = calls[i]
        var idx1 = dict[call]!
        let name = player[idx1 - 1]
        player[idx1 - 1] = call
        player[idx1] = name
        dict[call]! -= 1
        dict[player[idx1]]! += 1
        
    }
    return player
}

문제

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
2. 정사각형의 중심에 점을 하나 추가한다.

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다. 과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

풀이

점의 수 규칙을 찾아서 출력했다

• n = 1 일때, 정사각형의 갯수: (2^1)^2 , 점의 갯수: (2^1+1)^2
• n = 2 일때, 정사각형의 갯수: (2^2)^2 , 점의 갯수: (2^2+1)^2
• n = 3 일때, 정사각형의 갯수: (2^3)^2 , 점의 갯수: (2^3+1)^2
• n = k 일때, 정사각형의 갯수: (2^k)^2 , 점의 갯수: (2^k+1)^2

import Foundation

var num = Int(readLine()!)!
var count = 1

for i in 0..<num {
    count = count * 2
}

print((count+1) * (count+1))

풀이

큰 단위부터 나눈 몫을 저장하고 출력한다

import Foundation

let count = Int(readLine()!)!
var moneyStr = ["quar", "dime", "nick", "penn"]
var dict = ["quar": 25, "dime": 10, "nick": 5, "penn": 1]


for i in 0..<count {
    var money = Int(readLine()!)!
    var result = [String]()
    for j in moneyStr {
        let mStr = String(j)
        var num = 0
        
        while dict[mStr]! * (num+1) <= money {
            num += 1
        }
        money = money - (dict[mStr]! * num)
        result.append(String(num))
    }
    print(result.joined(separator: " "))
}

풀이

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

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 이후로 같은 수식이 이어지므로 제곱근 까지 반복해 소수 판별을 하였다.