Jenikeju

문제 설명

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
  • [대실 시작 시각, 대실 종료 시각] 형태입니다. 
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
  • 예약 시각이 자정을 넘어가는 경우는 없습니다.
  • 시작 시각은 항상 종료 시각보다 빠릅니다. 

내가 푼 풀이

어디선가 많이 본 익숙한 문제다.

1. 시작시간을 기준으로 오름차순 정렬한다.

2. 시작시간이 가장 빠른 예약부터 방에 넣는다.

3. 시작시간이 동일한경우, 종료시간이 빠른 예약부터 넣는다.

4. 방 중에 종료시간+10분과 다음예약이 같거나 크다면 해당방에 다음예약을 넣는다.

주의: 종료시간뒤 10분의 청소시간이 주어지므로 종료시간 + 10분 해야하지만, 50...59분 종료시간엔 시 단위가 바뀐다.

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

import Foundation

func solution(_ book_time:[[String]]) -> Int {
    var reservation = [[Int]]()
    var rooms = [[Int]]()
    var answer = 0
    var index = 0
    // 시작시간과 종료시간을 숫자로 변환
    for i in 0..<book_time.count {
        var res = book_time[i]
        var start = res[0].split(separator: ":").joined(separator: "")
        var end = res[1].split(separator: ":").joined(separator: "")
        reservation.append([Int(start)!, Int(end)!])
    }
    
    // 예약배열을 시작시간 기준 오름차순으로 정렬
    // 시작시간이 같다면 종료시간이 빠른 순으로 정렬
    var sorted = reservation.sorted{ 
        if $0[0] == $1[0] {
        return $0[1] < $1[1]
    } else {
        return $0[0] < $1[0]
    }}
    // index: 정렬된 예약배열 인덱스
    // answer: 정답출력 변수
    while index < sorted.count {
        // 이용중인 방이 없다면 바로 넣는다.
        if rooms.isEmpty {
            rooms.append(sorted[index])
            index += 1
            answer += 1
            continue
        }
        // 다음예약자의 시작시간과 종료시간
        var resStart = sorted[index][0]
        var resEnd = sorted[index][1]
        var find = false
        // 이용중인 방이 있다면 종료시간들을 검사한다.
        for i in 0..<rooms.count {
            var end = rooms[i][1]
            end += 10
            var str = String(end)
            // 종료후 청소시간이 60~69 사이라면 시단위가 올라가야한다.
            if Int(str.suffix(2))! >= 60 {
                end += 100
                end -= 60
            }
            // 종료시간과 다음예약의 시작시간이 동일하거나 작다면 이 방으로 다음예약을 넣는다.
            if end <= resStart {
                rooms[i] = [resStart, resEnd]
                find = true
                break
            } 
        }
        // 교체가능한 방이 없다면 추가
        if !find {
            rooms.append([resStart,resEnd])
            answer += 1
        }
        index += 1
    }
    return answer
}

문제 설명

내가 푼 풀이

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

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

- 모두 같은 원소인 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
}

***
* *
***

N=3일때 [1, 1] 을 제외한 8군데를 그린다.

이는 x % 3 = 1, y % 3 = 1 이 된다는것이다.

N=9일때 위 세칸을 보자

공백인 위치는 [1, 1], [1, 4], [1,7] 이 된다.

첫번째  [1, 1]: x % 3 = 1, y % 3 = 1

두번째 [1, 4]: x %3 = 1, y % 3 = 1

세번째 [1, 7]: x %3 = 1, y % 3 = 1 가 된다.

문제는 N = 9일때의 중간 공백이다.

중간공백의 좌표는 [3, 3], [3, 4] [3, 5] 등 9개가 있지만, 3 % 3 = 0이 된다.

그래서 위의 규칙과 같이 만들어 재귀호출을 하기 위해 왼쪽값을 3보다 작은값으로 만든다.

-> 3 / 3 % 3 = 1형식으로 만든다.

또한 N이 9를 넘어간다면  9 /3 = 3 이되고, 3%3은 0이 되므로 위의 규칙과 맞지않는다.

따라서 나눗셈의 오른쪽값은 왼쪽값보다 크거나 같아야 3보다 작은값으로 나뉘어 3으로 나눠도 0이되지않는다.

-> 재귀호출할때마다 N으로 나누어 0이나오면 N을 3으로 나누어 재귀호출한다.

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

import Foundation

// 입력받기
var N = Int(readLine()!)!
var out = ""

// 그리기함수
// a / b 일때 b가 a보다 크면 0이다.
// 그래서 b를 3으로 나누고 다시 재귀호출
func draw(x: Int, y: Int, num: Int) {
    if x / num % 3 == 1 && y / num % 3 == 1 {
        out += " "
    } else {
        if num / 3 == 0 {
            out += "*"
        } else {
            draw(x: x, y: y, num: num/3)
        }
    }
}

for i in 0..<N {
    for j in 0..<N {
        draw(x: i, y: j, num: N)
    }
    out += "\n"
}
print(out)