Jenikeju

문제 설명

내가 푼 풀이

첫번째 접근방법(완전탐색) (시간초과)

- 두개의 포인터를 이용해 각 포인터의 원소가 시소짝궁인경우 세주는 방식을 사용

- 모두 같은 원소인 100인경우 각 포인터가 n씩 움직여야하므로 O(N^2)이 걸려서 시간초과가 걸림..

두번째 접근방법(자료구조를 이용)

- 한개의 원소로 다른 원소들을 하나씩 찾는방식이였다면 이제는 한개원소로 모든 원소를 비교해보는 방식을 사용

원소 a가 2m에 있다면 원소b가 a의 시소짝궁이 되려면

1. a * 2 = b * 2 ------> b = a * 2 / 2  -> b = a

2. a * 2 = b * 3 ------> b = a * 2 / 3

3. a * 2 = b * 4  -----> b = a * 2 / 4

가 성립해야한다.

원소 a가 3m에 있다면 원소 b가 a의 시소짝궁이 되려면

1. a * 3 = b * 3 -------> a = b

2. a * 3 = b * 4 -------> b = a * 3 / 4

가 성립해야한다.

원소 a가 4m에 있다면 

원소 b는 원소 a의 두배면서 2m에 있는경우

위의 경우의수를 종합하자면

원소 a의 시소짝궁은 아래와 같다.

1. 같은원소

2. a의 두배 (a: 4m, b: 2m)

3. a의 2/3배 (a: 2m, b: 3m)

4. a의 3/4배 (a: 3m, b: 4m)

시소의 갯수를 구하기위해 딕셔너리를 이용해서 각각 무게의 수를 저장한다.

저장한 딕셔너리를 이용해 위의 경우의수와 맞는 모든 수를 찾고 출력한다.

코드로 구현하면 다음과 같다.

import Foundation

func solution(_ weights:[Int]) -> Int64 {
    var answer = 0
    var dict = [Double: Int]()
    // 딕셔너리에 저장
    // Swift는 나눗셈을 하면 소숫점을 모두 버리므로 정확한계산을 위해 무게는 Double형식으로 입력
    for i in weights {
        if dict[Double(i)] == nil {
            dict[Double(i)] = 1
        } else {
            dict[Double(i)]! += 1
        }
    }
    
    // 시소짝궁 찾기
    // a: 4, b:3 이라면 a와 b를 조합할 수 있는 경우의수: a x b = 12
    for i in dict {
        // 같은 무게
        if i.value > 1 {
            answer += (i.value * (i.value - 1)) / 2
        }
        // 2배의 무게
        if dict[i.key * 2] != nil {
            answer += (i.value * dict[i.key * 2]!)
        }
        // 2/3배의 무게
        if dict[i.key * 2 / 3] != nil {
            answer += (i.value * dict[i.key * 2 / 3]!)
        }
        // 3/4배의 무게
        if dict[i.key * 3 / 4] != nil {
            answer += (i.value * dict[i.key * 3 / 4]!)
        }
        
    }
    return Int64(answer)
}

문제 설명

내가 푼 풀이

- 이 문제는 완전탐색기법으로 풀었다.

1. 모든 층의 자리수는 + / - 두가지 경우의 수가 있다.

2. 일의자리부터 + / -를 하여 마지막자리수까지 + / - 를 해서 누른 버튼의 수중 최솟값을 구한다.

코드로 구현하면 다음과 같다.

import Foundation

func solution(_ storey:Int) -> Int {
    var current = storey
    var arr = Array(String(current).map{Int(String($0))!}.reversed())
    var answer = Int.max
    
    // DFS
    func dfs(arr: [Int], index: Int,count: Int) {
        // 모든 자리 탐색했다면 최솟값 구하기
        if index >= arr.count {
            answer = min(answer, count)
            return
        }
        var pulsNum = 10 - arr[index]
        var subs = arr
        var plus = arr
        
        // 현재자리에서 층수를 올리는 경우
        if index+1 < arr.count {
            plus[index+1] += 1
            dfs(arr: plus, index: index+1, count: count+pulsNum)
        } else if index == arr.count-1 && index < 10 {
            // 층수를 올려서 한자리수가 더 올라간경우 ex) 9층에서 10층
            plus.append(1)
            dfs(arr: plus, index: index+1, count: count+pulsNum)
        }
        // 현재자리에서 층수를 내리는 경우
        dfs(arr: subs, index: index+1, count: count+subs[index])

    }
    dfs(arr: arr, index: 0, count: 0)
    
    return answer
}

문제 설명

입출력 예

내가 푼 풀이

- 끊을 전선 하나를 제외한 그래프 구조로 만들고, dfs탐색을 했다.

- 탐색했을때, 방문한 수 count와 n-count의 차이 절댓값의 최솟값을 구했다.

1. 끊을 전선을 선택

2. 끊긴 전선을 제외한 전선들로 그래프 형성

3. DFS 혹은 BFS 탐색

4. 방문한 노드수: count 와 송전탑갯수 n사이에 |count - (n-count)|의 최솟값 출력

5. 모든 전선 다 끊어볼때까지 반복

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var answer = Int.max
    var arr = wires
    // 끊을 전선 모두 탐색
    for i in 0..<arr.count {
        var visited = [Int]()
        var needVisit = [Int]()
        var count = 0
        var node = [Int: [Int]]()
        
        // 끊을 전선을 제외한 나머지 전선으로 그래프 형성
        for j in 0..<arr.count {
            if i == j { continue}
            let start = arr[j][0]
            let arrive = arr[j][1]
            if node[start] == nil {
                node[start] = [arrive]
            } else {
                node[start]!.append(arrive)
            }
            if node[arrive] == nil {
                node[arrive] = [start]
            } else {
                node[arrive]!.append(start)
            }
        }
        
        // DFS
        needVisit = [node.first!.key]
        while !needVisit.isEmpty {
            var top = needVisit.removeLast()
            if !visited.contains(top) {
                count += 1
                visited.append(top)
                needVisit += node[top]!
            }
        }
        // | count - (n- count) |
        answer = min(answer, abs(count - (n-count)))
    }
    return answer
}

문제 설명

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    // 투포인터 start, end
    var start = 0
    var end = 0
    // k와 비교할 합계
    var sum = sequence[start]
    // [start, end]형식으로 저장할 배열과 해당 수열의 길이를 저장할 배열
    var result = [[Int]]()
    var length = [Int]()
    var min = Int.max
    var answer: [Int] = []
    
    // 투포인터 알고리즘 탐색
    while start <= end && end < sequence.count{     
        // 주어진 부분수열이 k와 동일하다면 추가해주고, start 인덱스를 옮기고, end도 가능하다면 옮김
        if sum == k {
            result.append([start, end])
            length.append(abs(start - end))
            sum -= sequence[start]
            start += 1
            
            if end+1 < sequence.count {
                end += 1
                sum += sequence[end]
            }
        } else if sum < k {
            // 합계가 k보다 작다면 end를 늘려 그만큼 합산
            // 만약 end가 주어진 수열의 끝번째자리인데 합계가 k보다 작다면 합계를 더 늘릴방법이 없으므로 탈출
            if end+1 < sequence.count {
                end += 1
                sum += sequence[end]
            } else {
                break
            }
        } else if sum > k {
            // 합계가 k보다 크다면 start를 올려 값을 낮춘다.
            sum -= sequence[start]
            start += 1
        }
    }
    
    // 주어진 여러가지 부분수열중 가장 길이가짧고 앞의 인덱스인 부분수열을 출력
    // 시작인덱스 start는 이미 오름차순으로 정렬되어있다(+1씩 증가하면서 답을 찾았기때문)
    for i in 0..<length.count {
        if min > length[i] {
            if length[i] == 0 {
                answer = [result[i][0],result[i][1]]
                break
            } else {
                answer = [result[i][0],result[i][1]]
                min = length[i]
            }
        }
    }
    return answer
}

문제 설명

내가 푼 풀이

- 이문제 이름도 그렇고 문제분류도 보면 우선순위큐를 사용하라고 하지만, Swift는 우선순위큐를 제공하지않는다..

- 그래서 더욱더 안만들고 배열로 풀었다.

- 원소를 입력받으면 오름차순으로 정렬하고, pop 메서드를 구현했다.

import Foundation

func solution(_ operations:[String]) -> [Int] {
    var arr = [Int]()
    
    for i in operations {
        let operation = i
        switch operation.prefix(1) {
            case "I": 
            let num = Int(operation.suffix(operation.count-2))
            arr = insert(arr: &arr, num: num!)
            print(arr)
            case "D":
            let str = operation.suffix(2)
            if str == " 1"{
                arr = popMax(arr)
            } else if str == "-1" {
                arr = popMin(&arr)
            }
            default: break
        }
    }
    if arr.isEmpty {
        return [0,0]
    } else {
        return [arr[0], arr[arr.count-1]]
    }
}

func insert(arr: inout [Int], num: Int) -> [Int] {
    arr.append(num)
    arr.sort{$0 > $1}
    return arr
}

func popMax(_ arr: [Int]) -> [Int] {
    if arr.isEmpty {
        return []
    } else {
        var a = Array(arr.reversed())
    a.removeLast()
    return a.reversed()
    }
}

func popMin(_ arr: inout [Int]) -> [Int] {
    if arr.isEmpty {
        return []
    } else {
        arr.removeLast()
        return arr
    }
}

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.

입출력 예

내가 푼 풀이

- 딕셔너리를 이용해 입력받은 뒤 sorted 메서드를 이용해 정렬하여 출력하였다.

import Foundation

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var dict = [String: [[Int: Int]]]()
    var genre = [String: Int]()
    var result = [Int]()
    // 입력받기
    // ["장르명": [["고유번호": "플레이수"], ["고유번호": "플레이수"]]]
    for i in 0..<genres.count {
        if genre[genres[i]] == nil {
            genre[genres[i]] = plays[i]
            dict[genres[i]] = [[i: plays[i]]]
        } else {
            genre[genres[i]]! += plays[i]
            dict[genres[i]]!.append([i: plays[i]])
        }
    }
    var sortedGenre = genre.sorted{$0.value > $1.value}
    for i in 0..<sortedGenre.count {
        let g = sortedGenre[i].key
        var filteredGenre = dict.filter{$0.key == g}
        var sortedGenre = filteredGenre.values.flatMap{$0}.flatMap{$0}
        var sg = sortedGenre.sorted{
                                   if $0.value == $1.value {
                                       return $0.key < $1.key
                                   } else {
                                       return $0.value > $1.value
                                   }}
        for j in 0..<sg.count {
            if j == 2 { break }
            result.append(sg[j].key)
        }
    }
    return result
}

문제 설명

내가 푼 풀이

- while문 안에 여러 조건을 넣기에 너무 힘들어서 단계를 나눴다.

- 1단계 order를 모두 수행 ( 수행중 보조컨테이너의 마지막원소와 같다면 지우기 )

- 2단계 보조컨테이너에 남아있다면 털어내기

import Foundation

func solution(_ order:[Int]) -> Int {
    var result = 0
    var stack = [Int]()
    var idx = 0
    var i = 1
    
    while i < order.count + 1 {
        var check = order[idx]
        if i == check {
            result += 1
            idx += 1
            i += 1
        } else if !stack.isEmpty && stack.last! == check {
            idx += 1
            stack.popLast()!
            result += 1
        } else {
            stack.append(i)
            i += 1
        }
    }
    
    while !stack.isEmpty {
        if stack.popLast()! == order[idx] {
            result += 1
            idx += 1
        } else {
            break
        }
        
    }
    
    return result
}

문제 설명

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

내가 푼 풀이

- queue1 의 합 = queue2 의 합 이도록 만드는 최소의 큐 이동횟수를 구한다.

- 두 큐의 합을 비교했을때 큰 곳에서 pop, 작은곳에서 append 해서 최적의 해를 구한다.

- Swift는 큐를 직접 구현해야한다. 기능만 대충 흉내낼수 있게 코딩했다.

- 두 큐는 Array로 만들었고, arr 의 가장 앞의 원소를 pop 하는데 시간복잡도가 O(N)이다.

- removeFirst() 를 이용해서 빼면 무조건 시간초과가 뜨므로 따로 인덱스를 만들어 pop할 경우에 +1을 해서 현재 위치를 저장한다.

- q의 최대 이동횟수는 q1 에서 q2로 모두 이동하고, q2에서 q1으로 다시 모두 이동하는 횟수 q.count * 3 을 최대로 정했다.

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var q1 = queue1
    var q2 = queue2
    var q1Idx = 0
    var q2Idx = 0
    var sumQ1 = q1.reduce(0, +)
    var sumQ2 = q2.reduce(0, +)
    var result = 0

    for i in 0..<queue1.count * 3 {
        var num = 0
        if sumQ1 > sumQ2 {
            num = q1[q1Idx]
            q1[q1Idx] = 0
            q1Idx += 1
            sumQ1 -= num
            sumQ2 += num
            q2.append(num)
        } else if sumQ2 > sumQ1 {
            num = q2[q2Idx]
            q2[q2Idx] = 0
            q2Idx += 1
            sumQ2 -= num
            sumQ1 += num
            q1.append(num)
        } else {
            return result
        }
        result += 1
    }
    
    return -1
}