2월 29일 TIL

프로그래머스 코딩테스트 [ 롤케이크 자르기 ]

GitHub 링크

• 이 문제는 주어진 배열을 자르고, 잘라진 두 배열의 요소들의 종류가 같은 방법의 수를 찾는 문제이다.
• 당연히 처음에는 slice를 해봤다, 역시나 시간초과가 뜬다.
• 인터넷에서 검색을 하니 자료구조를 배열이 아니라, dictionary와 set를 쓰면 된다고 한다.
• 전체적인 논리는 아래와 같다.
• 우선 주어진 배열에서 요소의 종류 및 개수를 dictionary에 저장한다.
• 배열을 순회하면서, 각 요소를 set에 넣어주고, dictionary에서 해당 요소의 개수를 -1 해주고, 만약 해당 요소의 개수가 0 이면 해당 요소는 dictionary에서 삭제한다. 그리고 set의 개수와 dictioanry의 개수를 비교해서 같은면 answer +1 하면 된다.
• 처음에는 Dictionary에서 삭제 해버리면 나중에 nil 문제가 생기는거 아니야? 생각했는데, 어쩌피 처음에 Dictionary에 배열 전체의 요소 종류와 개수를 넣기 때문에, 그리고 배열을 순회하면서 확인하는거니깐, dictionary에서 요소의 개수가 0이되고 지우면, 배열에서는 다시 등장할일이 없다는 의미이기도 하니깐, 지우는건 전혀 문제가 되지 않는다.
• swift 뿐만 아니라 dictionary와 set를 잘 써야 알고리즘 문제를 시간초과문제 없이 풀수 있는것 같다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    var ans = 0
    var topping = topping
    var toppingSet = Set<Int>()
    var dict = [Int:Int]()
    
    for (_,element) in topping.enumerated(){
        if let count = dict[element] {
            dict[element] = count + 1
        } else {
            dict[element] = 1
        }
    }
    
     for (_,element) in topping.enumerated(){
        toppingSet.insert(element)
        dict[element]! -= 1
        if dict[element]! == 0 {
            dict[element] =  nil
        }
        if toppingSet.count == dict.count {
            ans += 1
        }
     }
    
    return ans
}

프로그래머스 코딩테스트 [ 숫자 변환하기 ]

Github 링크

• 이 문제는 주어진 x,y,n 을 이용해서 x를 y로 만드는 문제다.
• x + n , x 2, x 3, 이 세가지 방법만을 이용해서 y를 만드는 것이다.
• 처음에는 dfs 풀어봤다. 재귀함수를 사용해서 모든 해를 구하고, 그 중에서 제일 cost가 적은 방법을 리턴하는 방법이다. 코드는 아래와 같다

import Foundation


func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    var ans = -1
    
    func cal (_ x:Int, _ y:Int, _ n:Int, _ count : Int){
        if x > y {
            return
        }
        if x == y {
            if ans == -1 {
                ans = count
            }else{
                ans = min(ans,count)
            }
            return
        }
        cal(x+n,y,n,count+1)
        cal(x*2,y,n,count+1)
        cal(x*3,y,n,count+1)
    }
    cal(x,y,n,0)
    return ans
}

• 솔직히 시간초과 날줄 알았다. 근데 뭔가 드디어 나도 DFS를 이해했구나 싶은 코드라서 소장용..

• 그래서 결국 문제를 어떻게 풀었냐면, 원래는 queue를 사용해서 BFS를 구현했지만, 이 또한 시간초과가 떠서, set를 이용하기로 했다.

• BFS를 생각하면 결국 트리 모양이라고 할 수 있는데, 시작점에서 leafNode 별로 한 번에 전개하고, 그리고 다시 leafnode 별로 한번에 전개 하는 방식이다.

• set 를 이용해서 x 부터 시작해서, x + n, x 2, x 3을 한번에 넣어주고, 다시 x + n, x 2, x 3 를 leafNode라고 생각하고 전개하는것이다. set를 쓰는것에 장점은, x + n == x * 2 이런 경우를 무시해줄수 있기 때문이다. 즉 연산을 한번 아낄수 있는것이다.

• 그리고 BFS이니깐 당연히 x + n, x 2, x 3 가 하나의 count로 계산할 수 있다.

import Foundation

func solution(_ x: Int, _ y: Int, _ n: Int) -> Int {
    var count = 0
    
    var set: Set<Int> = [x]
    
    while !set.isEmpty{
        if set.contains(y) {
            return count
        }
        var tempSet : Set <Int> = []
        for num in set {
            if num + n <= y {
                tempSet.insert(num + n)    
            }
            if num * 2 <= y {
                tempSet.insert(num * 2)    
            }
            if num * 3 <= y {
                tempSet.insert(num * 3)    
            }
        }
        set = tempSet
        count += 1
    }
    
    return -1
}