Jenikeju

문제 설명

내가 푼 풀이

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

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)

내가 푼 풀이

- 처음엔 그리디기법으로 입력받는수 100, 01 에따라 다음에 올 수 있는 수들만 넣었더니 틀렸다.

- 그리디로 하니까 반례들이 너무많았고 정확히 답을 구할 수 없었다.

- 다른사람의 풀이를 참고해봤는데, 다양하게 풀이 방법이 있었다..

- 이 문제는 완전탐색 dfs를 이용했지만 조건을맞춰서 탐색하였다.

맨처음에 올수있는 문자는 100혹은 01이다.

100이 온다면 0, 1이 올 수 있다

01이 온다면 다시 100이 오거나, 01이 올 수 있다.

100다음에 0이 온다면 0또는 1이 올수있다 이는 위의 100이 왔을때의 조건과 같다.

100다음에 1이 온다면 1 또는 01 또는 100이 올 수 있다.

이렇게 각각 문자간의 관계가 형성되는데, 관계만 따지고 다음에 올 수 있는 모든 경우의 수를 탐색한다면 시간초과가 날 것이다.

조건을 더 추가해서, 앞의 문자를 미리 받고 해당문자와 이전문자의 관계있는문자가 동일하다면 탐색하는 방향으로 지었다.

예) 100101

1. 첫번째 올 수 있는 문자: [100, 01] , 앞의 문자 스캔: 100 , 10

100이 동일하므로 100 배치 -> 100

2. 100다음에 올 수 있는문자: [0,1] , 앞의 문자 스캔 1

1이 동일하므로 1 배치 -> 1001

3. 1다음에 올 수 있는문자: [1, 01, 100] , 앞의 문자 스캔 [0, 01, 01x]

01이 동일하므로 01 배치 -> 100101 결과 YES

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

import Foundation

// 문자 해당 범위를 출력하기위해 별도의 메서드 생성
// 문자를 받는중 주어진 문자열을 초과한다면 임의의 문자(여기선 2)를 더 붙여준다.
extension String {
    func getRangeString(start: Int, end: Int, max: Int) -> String {
        var result = ""
        for i in start...end {
            if i >= max {
                result += "2"
            } else {
                result += "\(self[self.index(startIndex, offsetBy: i)])"
            }
        }
        return result
    }
}

// 테스트케이스 수
let T = Int(readLine()!)!
var result = String()

// dfs
func dfs(str: String, targetStr: String, count: Int, compare: String) {
    var target = targetStr
    // 찾는도중에 이미 찾았거나, 찾는범위가 주어진 문자열을 넘어버린경우 종료
    if result == "YES" || count > target.count {
        return
    }
    // 배치한 문자가 주어진 문자열과 동일하다면 YES
    // 하지만 마지막문자가 100으로 끝난다면 주어진 규칙과 맞지않는다.
    if str == target && compare != "100" {
        result = "YES"
        return
    }
    
    // 이전 문자와의 관계에 따라서 다음에 올 문자를 찾는다.
    // 맨 처음시작할때나 이전문자가 01 일때 올수있는문자 100, 01
    if compare == "" {
        var s1 = ""
        var s2 = ""
        
        //뒤의문자를 탐색
        if count+2 <= target.count {
            s1 = target.getRangeString(start: count, end: count+2, max: target.count)
        }
        if count+1 < target.count {
            s2 = target.getRangeString(start: count, end: count+1, max: target.count)
        }
        
        //앞의문자와 그다음 올수있는문자가 동일하다면 추가
        if s1 == "100" {
            dfs(str: str + "100", targetStr: target, count: count+3, compare: "100")
        }
        if s2 == "01" {
            dfs(str: str + "01", targetStr: target, count: count+2, compare: "")
        }
    } else if compare == "100" {
        // 이전문자가 100일때, 올수있는문자 0,1
        var s = ""
        
        //뒤의문자 탐색
        if count+1 <= target.count {
            s = target.getRangeString(start: count, end: count, max: target.count)
        }
        
        //뒤의문자와 그다음 올수있는문자가 동일하다면 추가
        if s == "1" {
            dfs(str: str + "1", targetStr: target, count: count+1, compare: "1")
        }
        if s == "0" {
            dfs(str: str + "0", targetStr: target, count: count+1, compare: "100")
        }
    } else if compare == "1" {
        // 이전문자가 1일때, 올수있는문자 100, 01, 1
        var s1 = ""
        var s2 = ""
        var s3 = ""
        
        //뒤의 문자 탐색
        if count <= target.count {
            s1 = target.getRangeString(start: count, end: count, max: target.count)
        }
        if count + 1 <= target.count {
            s2 = target.getRangeString(start: count, end: count+1, max: target.count)
        }
        if count + 2 <= target.count {
            s3 = target.getRangeString(start: count, end: count+2, max: target.count)
        }
        
        //뒤의문자와 그다음 올수있는문자가 동일하다면 추가
        if s1 == "1" {
            dfs(str: str + "1", targetStr: target, count: count+1, compare: "1")
        }
        if s2 == "01" {
            dfs(str: str + "01", targetStr: target, count: count+2, compare: "")
        }
        if s3 == "100" {
            dfs(str: str + "100", targetStr: target, count: count+3, compare: "100")
        }
    }
    
}
for i in 0..<T {
    result = "NO"
    var target = readLine()!
    dfs(str: "", targetStr: target, count: 0, compare: "")
    print(result)
}