초니로그

문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제 설명

귤 크기를 의미하는 정수 배열이 주어짐

이 중 k개의 귤을 뽑아야 할 때, 크기의 종류 최솟값을 구해야 함

풀이법 구상

<틀린 풀이>

DFS를 활용하여 귤 크기 배열 내 부분 집합을 구하여 최솟값 갱신

-> n은 최대 100,000인데, dfs가 끝날 때마다 ch 배열을 전부 확인하게 되며 O(N^2)의 시간 복잡도를 가지게 됨

import Foundation

var answer = 100000
var ch:[Bool] = []

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    ch = Array(repeating: false, count: tangerine.count)
    dfs(0, tangerine, k)
    return answer
}

func dfs(_ v: Int, _ t:[Int], _ k: Int) {
    if(v == t.count) {
        var sizes = Set<Int>()
        var contain_cnt = 0
        for i in 0..<t.count {
            if(ch[i]) {
                contain_cnt += 1
                sizes.insert(t[i])
            }
        }
        if(!sizes.isEmpty && contain_cnt == k && answer > sizes.count) { 
            answer = sizes.count
        }
        
    } else {
        ch[v] = true
        dfs(v+1, t, k)
        ch[v] = false
        dfs(v+1, t, k)
    }
}

<정답 풀이>

딕셔너리를 통해 귤의 크기 별 개수를 정의

크기 별 개수를 기준으로 딕셔너리를 내림차순 정렬

딕셔너리를 돌며 개수와 종류 수를 누적합하며, 그 값이 k 이상이 될 경우 누적된 종류 수를 반환

(개수가 많은 것부터 탐색하므로 누적된 종류 수는 최소일 수밖에 없음)

코드 구현 (Swift)

import Foundation

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    var dict:[Int:Int] = [:]
    for t in tangerine {
        if(dict[t] == nil) { dict[t] = 1 }
        else { dict[t]! += 1 }
    }
    let s_dict = dict.sorted { $0.value > $1.value }
    
    var sum = 0
    var answer = 0
    for d in s_dict {
        sum += d.value
        answer += 1
        if(sum >= k) { return answer }
    }
    return answer
}

문제 URL

https://www.acmicpc.net/problem/2655

문제 설명 요약

• n개의 네모 모양 벽돌 정보가 주어짐
• 주어진 정보는 '밑면의 넓이'와 '높이' 그리고 '무게'
• 구해야 하는 것은 주어진 벽돌들 중 높이가 최대가 되도록 쌓을 때, 쓰인 벽돌의 개수와 각 벽돌의 순서
  (단, 순서를 출력할 때에는 제일 위에 쌓인 벽돌의 순서부터 출력해야함)
• 벽돌을 쌓을 때의 규칙은 아래와 같음
  
  1. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
  2. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
  3. 벽돌들의 높이는 같을 수도 있다.
  4. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
  5. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다

문제 풀이

• 벽돌을 쌓을 수 있을지 없을지를 결정하는 요소가 '밑면의 넓이'와 '무게'이므로, 우선 둘 중에 하나를 기준으로 배열을 정렬해둠
• 정렬 이후 Dynamic Programming(동적 계획법)을 활용하여, 쌓을 수 있는지 없는지에 대한 판단을 요소별로 쪼개어 수행

Swift를 활용한 풀이

import Foundation

let n = Int(readLine()!)! // 벽돌의 개수
var origin:[[Int]] = [] // 벽돌들의 정보

// 벽돌 정보 입력 받기
for _ in 0..<n {
    origin.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
// 벽돌의 밑면의 넓이를 기준으로 내림차순 정렬
var sorted_list = origin.sorted { $0[0] > $1[0] }

var dy:[Int] = [] // 높이합 최대 기록 배열
var hist:[Int:[Int]] = [:] // 각 항목 별 쌓을 수 있는 벽돌의 무게 정보 - [s:[w1, w2, ...]]

// 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)에 대한 정보는 기본적으로 저장 (비교 대상이 없기 때문)
dy.append(sorted_list[0][1])
hist[sorted_list[0][0]] = [sorted_list[0][2]]

// 최대값에 관한 정보는 모두 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)의 값으로 초기화
// (0과 빈 배열로 초기화해두면, 0번째 값을 고려하는 경우가 없어지기 때문)
var max_h_sum = dy[0] // 높이 합의 최대값
var max_h_list:[Int] = hist[sorted_list[0][0]]! // 높이 합이 최대인 경우의 높이값 요소 배열

// 2번째 벽돌 정보부터 살펴보면서, 이전 벽돌 중 자신이 위에 쌓일 수 있을지를 판단
for i in 1..<n {
    var max_h = 0
    var temp:[Int] = []
    for j in (0..<i).reversed() {
        // 이전 벽돌 중 자신보다 무게가 무거운 벽돌이면서, 높이의 합이 최대치인 경우의 정보를 임시 저장
        if (sorted_list[i][2] < sorted_list[j][2] && dy[j] > max_h) {
            max_h = dy[j]
            temp = hist[sorted_list[j][0]]!
        }
    }
    // 바로 위 for문에 의해 결정된 '높이의 합이 최대이면서, 무게가 자기자신보다 무거운 벽돌'의 정보를 기반으로 dy와 hist 초기화
    temp.append(sorted_list[i][2])
    hist[sorted_list[i][0]] = temp
    dy.append(max_h + sorted_list[i][1])

    // dy와 hist의 정보가 추가될 때마다, 각 높이의 합과 그것을 이루는 높이 요소값 배열을 갱신
    if (max_h_sum < dy[i]) {
        max_h_sum = dy[i]
        max_h_list = hist[sorted_list[i][0]]!
    }
}

// 결정된 최대 높이값의 요소 배열을 뒤집고 출력
// (무게를 기준으로 내림차순 된 배열에서 값을 찾았기때문)
max_h_list = max_h_list.reversed()
print(max_h_list.count)
for w in max_h_list {
    for i in 0..<origin.count {
        if(origin[i][2] == w) { print(i+1) }
    }
}

문제 링크 - https://www.acmicpc.net/problem/15649

문제 설명

n, m이 주어지면 1이상 n이하의 수 중 m개를 선택해 구성한 순열 출력

n >= m이며, n과 m 모두 1이상 8이하의 정수

풀이법 구상

파이썬을 사용하면 itertools 내 permutations 메소드를 써서 바로 풀이가 가능하지만 스위프트는 그런거 없음 왜..왜...

처음에는 1부터 n까지의 정수가 담긴 배열을 돌면서 하나씩 추가하고 배열에서 삭제해나가는 로직으로 생각했는데, 이러면 m중 반복문을 돌아야함 (그래도 시간복잡도가 O(N^m)이라 시간초과는 안 나겠지만 구현하기 까다로울 것 같아서 일단 포기)

1이상 n이하 정수 중에서 m개를 뽑는 방법은 DFS/BFS를 사용할 수 있는데

n이 4이고, m이 2인 경우를 생각해보면 1부터 4사이의 정수 중에 2개를 선택해야함

선택된 수를 담을 배열은 아래와 같은 경우의 수들을 가질 수 있음

[ ] -> [1] -> [1,2]

[ ] -> [1] -> [1,3]

[ ] -> [1] -> [1,4]

[ ] -> [2] -> [1,2]

[ ] -> [2] -> [2,3]

[ ] -> [2] -> [2,4]

...

[ ] -> [4] -> [3,4]

위 경우들은 트리로 시각화 할 수 있고, 각 노드들을 탐색하면서 노드를 구성하는 정수배열의 크기가 m인 경우만 중복없이 출력시키면 됨

는 그나마 익숙한 BFS로 구현했더니 시간초과

/// 시간초과난 코드

import Foundation

func solution(_ n: Int, _ m: Int) -> Void {
    var results: [[Int]] = []
    for i in 1...n { results.append([i]) }

    // 수열 생성
    for _ in 0..<m {
        for arr in results {
            var temp: [[Int]] = []
            for i in 1...n {
                if arr.contains(i) { continue }
                var temp_arr = arr
                temp_arr.append(i)
                temp.append(temp_arr)
            }
            
            for t in temp {
                if !results.contains(t) { results.append(t) }
            }
        }
    }

    // 사전 순으로 정렬
    var sorted_results: [[Int]] = []
    for arr in results { if (arr.count == m) { sorted_results.append(arr) } }
    
    sorted_results = sorted_results.sorted(by: { $0[0] < $1[0] })

    // 정답 출력
    for arr in sorted_results {
        var str = ""
        for a in arr { str += "\(a) " }
        print(str)
    }
}

let input = readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)

구글링했더니 대부분 백트래킹으로 풀었음

백트래킹은 DFS와 비슷하지만 DFS는 종료 조건만 가지고 무지성 재귀함수를 사용하고, 백트래킹은 답이 있을 것 같은 경우에만 탐색하는 것이 차이점임

백트래킹에서 쓰이는 '유망함', '유망하지않음', '가지치기'의 용어도 정답 존재 가능성과 연관된 것임

- 유망함 : 정답을 찾을 수 있는 가능성 O

- 유망하지않음 : 정답을 찾을 가능성 X

- 가지치기 : 유망하지 않은 경우를 제외하는 것

(아무튼 다시 이 문제로 돌아와서) BFS 풀이는 배열의 수가 0개 -> 1개 -> 2개 -> ... -> m개인 순서로 노드들을 탐색하기 때문에, 배열의 길이가 0개부터 m-1개인 탐색할 필요가 없는 경우까지 고려하게 됨

그리고 모든 결과 배열을 다 포함하고 마지막에 탐색하면서 길이가 m인 배열을 사전순으로 출력하기 위해 따로 정렬도 해줘야 함

근데 백트래킹 풀이는 가장 적은 숫자부터 구성된 배열 중, 길이가 m인 경우에만 출력하게 하면 되니까 불필요한 경우의 고려와 정렬 코드가 삭제될 수 있음

그럼 백트래킹을 쓰려면 뭐가 유망한 거고, 뭐가 유망하지 않은 건지를 알아야 하는데 n = 4, m = 2인 경우를 예시로 보면, 

결과배열이 [1]인 경우에는 1부터 4까지 중 1을 제외하고 추가해야함

이런 생각들로 아래처럼 구현하고 제출했더니 성공,,

코드 구현 (스위프트 사용)

import Foundation

func solution(_ n: Int, _ m: Int) -> Void {
    let temp:[Int] = []
    dfs(arr: temp, m: m, n: n)
}

func dfs(arr: [Int], m: Int, n: Int) -> Void {
    if (arr.count == m) {
        var str = ""
        for a in arr { str += "\(a) " }
        print(str)
        return
    }

    var temp = arr
    for p in 1...n {
        if !temp.contains(p) {
            temp.append(p)  // 1부터 n 사이의 배열에 없는 숫자 중 젤 작은 거 추가
            dfs(arr: temp, m: m, n: n)   // 위에서 숫자 새로 추가한 배열로 다시 검사
            temp.remove(at: temp.count-1)   // 위에서 검사 끝나고 오면 가장 최근에 추가했던거 삭제(그 자리에 다른 새로운거 넣어보려고)
        }
    }
}

let input = readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)

DFS/BFS로 풀 수 있을 것 같아도 시간 복잡도 한 번 더 고려해보고, 뭔가 될 것 같아서 풀었는데 시간초과나면 백트래킹 풀이도 고려해보자

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

주어진 정수 배열을 적절히 더하거나 뺀 값이 주어진 타겟 넘버와 같은 경우의 수를 출력

풀이법 구상

처음에는 이중 반복문을 돌면서 각 숫자를 음수로 바꾼 후의 총 합이 타겟과 같은지 판별하는 로직으로 구현했다가 실패

-> +4-1+2-1 과 같이 음수 사이에 양수가 존재하는 경우는 고려할 수 없음

각 숫자가 양수이거나 음수인 경우만 고려하면 되고 그러면 2^N의 시간 복잡도가 발생하는데, N의 최대값은 20으로 약 1,050,000이 됨

각 숫자가 양수이거나 음수가 되는 경우를 모두 고려하려면 각 숫자에 +,-를 붙인 노드로 이루어진 트리로 시각화할 수 있음

각 노드를 탐색하며 더한 합계값을 타겟 넘버와 비교하면 결과값 도출 가능

탐색에는 BFS/DFS를 모두 사용할 수 있으나 제출 코드는 BFS사용

코드 구현 (스위프트 사용)

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var result = 0
    var sum_arr = [0]   // 반복문 시작을 위해 0 하나 추가
    
    for n in numbers {
        var temp: [Int] = []
        for s in sum_arr {
            temp.append(s+n)
            temp.append(s-n)
        }
        sum_arr = temp
    }
    
    for s in sum_arr { result += (s == target) ? 1 : 0 }
    
    return result
}

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/120875

문제 설명

x,y 좌표값으로 구성된 점 4개의 정보가 2차원 정수형 배열로 주어짐

4개의 점들이 조합되어 만들 수 있는 직선 중 서로가 평행한 경우가 있다면 결과값으로 1을, 아니라면 0을 반환해야함

풀이법 구상

점의 정보는 4개로 고정된 만큼만 주어짐

직선의 x,y 좌표간 차이값의 절대값이 같으면 평행한 것으로 간주하고 풀었다가 틀림 -> 방향 고려 안됨

방향을 포함하는 기울기값(y차이 / x차이)이 같으면 평행

주어진 점 4개로 서로 다른 직선을 구성할 수 있는 경우의 수를 아래와 같음

(0번째 점, 1번째 점)

(0번째 점, 2번째 점)

(0번째 점, 3번째 점)

(1번째 점, 2번째 점)

(1번째 점, 3번째 점)

(2번째 점, 3번째 점)

서로 다른 직선 6가지 경우의 각 기울기 값을 구하여 반복문을 돌며 같은 값이 존재하는지 판단 -> 틀림(12번 케이스부터 실패)

위와 같은 로직으로 기울기들을 판별할 경우 불가능한 경우까지 비교하게됨

ex. (0번째 점, 1번째 점)으로 이루어진 직선과 (0번째 점, 2번째 점)으로 이루어진 직선 간의 기울기를 비교

즉 주어진 점 4개로 '서로 다른 2개의 직선'을 구성하여 비교하기 위한 경우는 아래와 같음

(0번째 점, 1번째 점) VS (2번째 점, 3번째 점)

(0번째 점, 2번째 점) VS (1번째 점, 3번째 점)

(0번째 점, 3번째 점) VS (1번째 점, 2번째 점)

코드 구현 (스위프트 사용)

func solution(_ dots:[[Int]]) -> Int {
    if (getInc(dots[0], dots[1]) == getInc(dots[2], dots[3])) {
        return 1
    } else if  (getInc(dots[0], dots[2]) == getInc(dots[1], dots[3])) {
        return 1
    } else if  (getInc(dots[0], dots[3]) == getInc(dots[1], dots[2])) {
        return 1
    } else {
        return 0
    }
}

func getInc(_ m:[Int], _ n: [Int]) -> Double {
    let diffX = max(m[0], n[0]) - min(m[0], n[0])
    let diffY = max(m[1], n[1]) - min(m[1], n[1])
    let inc = ((n[0]-m[0])*(n[1]-m[1]) < 0) ? -1.0 : 1.0
    return inc*(Double(diffY)/Double(diffX))
}

문제 링크 - https://www.acmicpc.net/problem/2012

문제 설명

n명에게 각각 예상 등수값을 입력받고, 그 값들을 토대로 불만족 지수가 최소로 나오도록 구성하여 불만족 지수의 최소값을 출력

불만족 지수란 예상 등수가 1등이고, 실제 순위 구성 후 등수가 3등인 경우 (|1-3|)으로 2의 값이 됨

(n의 범위는 1이상 500,000이하)

풀이법 구상

예상 순위보다 실제 순위가 높든 낮든 무관하게 그 차이값만큼이 불만족 수치가 됨

최대한 예상 순위가 실제 순위가 되도록 해야하므로 정렬 후 각 예상 순위값을 돌며 실제 순위와의 차이값을 구해야함

정렬 + 반복문이 필요함

-> 스위프트 기본 정렬 메소드의 시간복잡도 - O(n log n)

-> 반복문 시간 복잡도 - O(N)

-> 동시에 일어나지 않고 정렬 후 반복문 돌게됨

코드 구현 (스위프트 사용)

import Foundation

func solution(_ arr: [Int]) -> Void {
    var sum = 0
    let temp = arr.sorted()
    for i in 1...arr.count { sum += abs(i - temp[i-1]) }
    print(sum)
}

var arr: [Int] = []
let cnt = Int(readLine()!)!
for _ in 0..<cnt { arr.append(Int(readLine()!)!) }

solution(arr)

문제 링크 - https://www.acmicpc.net/problem/2751

문제 설명

랜덤한 숫자 n개가 입력되면 해당 숫자들을 오름차순으로 정렬하여 한 줄에 하나씩 출력

- 입력되는 숫자의 개수는 1개 이상 1,000,000개 이하

- 들어오는 숫자는 절대값이 1,000,000이하인 정수

풀이법 구상

스위프트에 있는 sort 메소드 사용하기

-> 기본 정렬 메소드의 시간 복잡도는 O(n log n) 이므로 시간 제한에 문제되지않음

코드 구현 (스위프트 사용)

import Foundation

func solution(_ arr: [Int]) -> Void {
    let result = arr.sorted()
    for n in result { print(n) }
}

var arr: [Int] = []
let cnt = Int(readLine()!)!
for _ in 0..<cnt { arr.append(Int(readLine()!)!) }

solution(arr)

문제 링크 - https://www.acmicpc.net/problem/2581

문제 설명

주어진 두 수 m, n을 포함하여 그 사이에 존재하는 소수의 합계값과 그 소수들 중 최소값을 출력 (소수가 없는 경우 -1 출력)

풀이법 구상

m이상 n이하를 범위로 하는 반복문을 돌면서 각 수가 소수인지 판별

코드 구현 (스위프트 사용)

import Foundation

func solution(_ m:Int, _ n:Int) -> Void {
    var sum = 0
    var min = -1

    for p in m...n {
        if isDecimal(p) {
            sum += p
            if (min == -1 || min > p) { min = p }
        }
    }
    if (sum == 0) { print(-1) }
    else {
        print(sum)
        print(min)
    }

}

func isDecimal(_ n:Int) -> Bool {
    if (n == 1) { return false }
    for i in 2..<n { if (n%i == 0) { return false } }
    return true
}

let m = Int(readLine()!)!  
let n = Int(readLine()!)!  

solution(m,n)