3월 7일 TIL

프로그래머스 코딩테스트 [ 가장 큰 수]

Github 링크

• 이 문제는 주어진 숫자 배열의 있는 각 숫자들을 조합해서 제일 큰 숫자를 찾는것이다.
• 처음으로 생각했던 방법은 sort를 custom 해서 각 숫자의 자리수를 비교하는것이다.
  - 두 숫자가 같은 자리수를 갖고 있다면 큰걸 앞으로
  • 두 숫자가 다른 자리수를 갖고 있다면, 첫번째 자리부터 비교 시작
  • 예를 들어 9, 30 이면 첫번쨰 자리 를 비교했을때 9가 더 크기 때문에 9 가 앞으로
  • 문제는 이제 자리수가 같다면?
  • 예를 들어 30, 34 인 경우, 첫번째 자리 3은 같기 때문에 넘어가고, 두번째 자리 0 vs 4이니깐, 4가 더 크니깐 앞으로.
  • 다만 이렇게 풀면 문제점은 각 숫의 자리를 구해야 하고, 숫자는 최대 1000까지 가능하고, 숫자는 최대 10000개가 주어지는 상황에서, 시간초과가 발생할꺼 같다는 생각이 들었다.
  • 그래서 생각해보니 굳이 자리수마다 비교할 필요없이, 그냥 합쳐보고 큰걸 리턴하면 되지 않을까? 라는 생각이었다.
• 예를 들면 30, 34 인 경우, 3034 vs 3430 이런식으로 비교를 해서, 3430이 더 크니 34가 앞으로 와야된다는 것이다.
• 마지막에 String으로 return해야 하기 때문에, 정렬한 배열을 reduce를 통해 다 합치는 작업을 하는데,예외 상황으로 모든 배열의 숫자가 0 인경우, [0,0,0,0] 로 예시를 들면, "0000"을 리턴하게 된다. 따라서 정렬한 배열의 0번째 요소가 0인 경우, 즉 0이 이 배열에서 제일 큰 숫자인 경우, 0 을 리턴하도록 예외처리를 하였다.

import Foundation

func solution(_ numbers:[Int]) -> String {
    let sorting : (Int, Int) -> Bool = {(lhs,rhs) in
        let combine1 = Int(String(lhs)+String(rhs))!
        let combine2 = Int(String(rhs)+String(lhs))!
        return combine1 > combine2
    }
    let sortedNumbers = numbers.sorted(by: sorting)
    if sortedNumbers[0] == 0{
        return "0"
    }
    let ans = sortedNumbers.reduce(""){$0 + "\($1)"}
    return ans
}

프로그래머스 코딩테스트 [ 소수 찾기 ]

Github 링크

• 이 문제는 이름에서는 소수 찾는게 메인인 문제 같지만, 사실은 주어진 문자열 (숫자로 구성됨) 을 쪼개서, 각 숫자로 조합 가능한 모든 숫자를 찾고 ( 중복 없이 ), 그 숫자들 안에서 소수만 출력하면 되는것이다.
• 즉 permutation 순열을 찾아야하는 문제다
• permuatation vs combination

  Permutation은 순서가 다르면 다른걸로 간주하고
  Combination은 순서와 상관없다.

• Permutaion인 이유는 0,1,3 인 경우, 아래와 같은 조합을 만들어야 하기 때문이다.
• 0,1,3,10,13,31,31,103,130,310,301
• 기존에 모음 사전 에서 풀었던 방식은 요소를 중복 사용의 상관없이 길이 위주로 단어를 만드는거였다면, 이번 문제에서는 중복 사용이 안되기 떄문에 다르게 접근해야했다.

func genertesNumHelper(_ currentWord : String, _ temp: [String]){
        if let newWord = Int(currentWord) {
             numSet.insert(newWord)
        }
       
        for num in temp {
            let newWord = currentWord + num
            var newArr = temp
            if let index = newArr.firstIndex(of: num){
                newArr.remove(at: index)
            }
            genertesNumHelper(newWord, newArr)
        } 
    }
    
    genertesNumHelper("", number)

• 기존에 모음사전에서 풀었던 방법과 다른 점은 , 중복 사용을 방지하기 위해, newArr.remove(at: index)를 사용해서 사용했던 숫자는 지워줬다.

import Foundation

func solution(_ numbers:String) -> Int {
    let number = numbers.map{String($0)}
    var numSet : Set<Int> = []
    
    func genertesNumHelper(_ currentWord : String, _ temp: [String]){
        if let newWord = Int(currentWord) {
             numSet.insert(newWord)
        }
       
        for num in temp {
            let newWord = currentWord + num
            var newArr = temp
            if let index = newArr.firstIndex(of: num){
                newArr.remove(at: index)
            }
            genertesNumHelper(newWord, newArr)
        } 
    }
    
    genertesNumHelper("", number)
    
    
    func isPrime(_ number :Int) -> Bool{
        if number <= 1 {
            return false
        }
        if number == 2 {
            return true
        }
        
        let sqrtValue = Int(Double(number).squareRoot()) + 1
        
        for i in 2...sqrtValue {
            if number % i == 0 && i != number {
                return false
            }
        }
        return true
    }
    
    var ans = 0 
    for element in numSet {
        if isPrime(element) {
            ans += 1
           
        }
    }
    return ans
}