Jenikeju

내가 푼 풀이

- 이문제의 구현방법은 어렵지않지만, 예외처리를 굉장히 엄격하게 해야한다.

접근방법:

1. 주어진 배열을 받아서 해당 노래의 음을 재생시간에 맞춰서 늘리거나 줄여줌(문제조건3번)

2. 조절된 음을 m의크기만큼 부분문자열로 만듬

3. 예외처리에 따라서 m과 동일한 문자열이 있는지 확인

4. 같은음이 다른 재생시간에서도 발견된다면, 음악길이가 긴것먼저, 음악길이도 같다면 먼저 재생된것으로 출력한다.

예외처리가 너무 빡셌다.. 특히 Swift는 문자열에대해 아주 가혹해서 더 어려웠던것같다.

확실히 카카오 문제는 구현도 어렵게 예외처리도 어렵게,,

*** 여러가지 예외들)

1. 음뒤에 #이 붙어있는것은 다른음으로 취급한다. #문자열 처리가 잘 되어있어야한다.

2. 노래의길이는 재생시간만큼 반복재생하거나 줄여야한다.

3. 부분문자열이 중간에 있을때, m과 동일한지 비교할 수 있어야한다.

코드로 구현하면 다음과 같다.(매우김)

import Foundation

func solution(_ m:String, _ musicinfos:[String]) -> String {
    var answer = ["0", "(None)"]
    var index = 0
    var musics = [[String]]()
    var mCount = m.count
    
    // 주어진 음악정보를 음악길이만큼 늘리거나 줄여서 따로 저장한다.
    while index < musicinfos.count {

        var infos = musicinfos[index].split(separator: ",")
        // 재생시간 계산
        let start = infos[0].split(separator: ":").joined(separator: "")
        let end = infos[1].split(separator: ":").joined(separator: "")
        let startNum = Int(start.prefix(2))! * 60 + Int(start.suffix(2))!
        let endNum = Int(end.prefix(2))! * 60 + Int(end.suffix(2))!
        let total = (endNum - startNum)
        
        // 음악이름, 음악의 음정
        let name = infos[2]
        var music = infos[3].map{String($0)}
        var converted = [String]()
        var musicIndex = 0
        
        // 음정 문자열을 배열로 변환
        while musicIndex < music.count {
            var str = music[musicIndex]
            if str == "#" {
                musicIndex += 1
                continue 
            }
            if musicIndex == music.count-1 {
                converted.append(str)
                musicIndex += 1 
                continue
            }
            if music[musicIndex+1] == "#" {
                str = str + "\(music[musicIndex+1])"
                converted.append(str)
            } else {
                converted.append(str)
            }
            musicIndex += 1
        }
        
        // 변환한 배열을 통해 재생시간만큼 줄이거나 늘린다.
        let a = converted.joined(separator: "")
        var musicString = ""
        var sin = 0
        for i in 0..<total {
            musicString += converted[sin]
            sin += 1
            if sin == converted.count {
                sin = 0
            }
        }
        // 음악길이로 조절한 음악을 따로저장
        musics.append([String(musicString.count),String(musicString),String(name)])
        index += 1
    }
    
    // 같은 음악인지 판단
    for i in musics {
        let length = i[0]
        var str = i[1]
        let name = i[2]
        
        var sine = 0
        var strs = [String]()
        
        // m의 길이만큼 부분문자열 배열 생성
        while true {
            if sine + mCount > Int(length)! { break }
            sine += 1
            strs.append(String(str.prefix(mCount)))
            str.remove(at: str.startIndex)
        }
        """
        같은 문자열인지 확인
        1. i == strs.count-1
        뒷자리가 #이 아닌문자열이 들어온다면 뒤에 #이 이어지는지 확인해야한다. 
        하지만 뒤에 오는 문자가 없다면 같은문자로 판단
        2. (i+1 < strs.count && strs[i+1].suffix(1) != "#") 
        뒷자리가 더 올수있는상황에서 그다음 부분문자열의 마지막문자가 #이 아니라면, 그 뒤로 #이 올 수 없다는 뜻
        그래서 같은문자로 판단 (#이 안오는 일반 음정이다.)
        (부분 문자열 순서는 ex.ABCD의 2길이 문자열 이라면 AB, BC, CD 이므로 BC 뒤에 오는문자는 CD의 마지막문자 D)
        """
        for i in 0..<strs.count {
            if strs[i] == m {
                if i == strs.count-1 || (i+1 < strs.count && strs[i+1].suffix(1) != "#"){
                    if Int(answer[0])! < Int(length)! {
                        answer = [String(length), String(name)]
                    }
                }
            }
        }
    }
    return answer[1]
}

내가 푼 풀이

첫번째 접근법: 당연히 완전탐색

1. 각 배열마다 최대공약수를 구한다.

2. 구한 최대공약수를 상대 배열에 전체적으로 나누어본다.

3. 나누어지지 않는 숫자중 최댓값 출력

4. 없다면 0

-> 시간초과

주어진 원소의 최댓값이 1억이라서 이방법으로 한다면 최대공약수를 구하는 반복문만 최대 1억번 돌리게된다..

두번째 접근법: 유클리드 호제법

시간을 단축하기위해 단순반복방법이 아닌 유클리드호제법으로 최대공약수를 구하는 시간을 줄인다.

1. 배열마다 유클리드호제법으로 최대공약수를 구한다. 반복은 배열의 갯수만큼(최대 50만번)

2. 구한 최대공약수로 상대배열을 나눠본다.

3. 나눠지면 0으로 초기화, 안나누어지면 그대로

4. 두개의 최대공약수중 최댓값 출력(둘다 나누어졌다면 0이되고, 한쪽만 나누어진다면 그 값이 최대가됨)

-> 성공

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

import Foundation

// 유클리드를 이용한 gcd 재귀호출
func gcd(_ num1: Int,_ num2: Int) -> Int {
    if num2 == 0 {
        return num1
    } else {
        return gcd(num2, num1 % num2)
    }
}
func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    var fA = arrayA[0]
    var fB = arrayB[0]
    
    //A의 최대공약수
    for i in arrayA {
        fA = gcd(fA,i)
    }
    //B의 최대공약수
    for i in arrayB {
        fB = gcd(fB,i)
    }
    // A의 최대공약수로 B를 나눠봄, 나눠지면 0
    for i in arrayB {
        if i % fA == 0 {
            fA = 0
            break
        }
    }
    // B의 최대공약수로 A를 나눠봄, 나눠지면 0
    for i in arrayA {
        if i % fB == 0 {
            fB = 0
            break
        }
    }

    return max(fA, fB)
}

문제 설명

제한사항

• 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
}