Triangle coding task - Learn to Code - Codility

문제 분석

주어진 배열에서 삼각형을 구성하는 3개의 변의 길이가 하나라도 있으면 1, 없으면 0
 삼각형의 조건: 3개의 원소가 언제나 [2개의 합 > 1개]를 성립하는 것
 사실 큰 것끼리 더하면 당연히 성립한다.
 그러므로 3개의 원소를 정렬해서 [작은 값끼리의 합 > 큰 값]을 성립하는지만 확인하자.
 다만 원소에 음수가 있을 수 있다.
     원소에 음수가 있으면 조건이 절대 성립하지 않는다.
     작은 값이 음수일 텐데, 음수끼리의 덧셈은 값을 더 작아지게 만들기 때문에
     0의 경우도 같다.

배열 중에서 3개의 원소를 선택하는 방법을 고민해보자
 100,000 C 3은 너무 크다.
 배열을 오름차순으로 정렬해서, i, i+1, i+2를 계속 비교하는 것이 좋겠다.
     하나라도 조건을 만족하면 return 1, 없으면 return 0

의사 코드

let size = A.count
 let sortedA = A.sorted()
 for i in 0..<size - 2 // i + 2 == size - 1까지 가능하므로
 sortedA[i] + sortedA[i + 1] > sortedA[2] ? return 1
 중간에 return 못 하면, return 0

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    if size < 3 { return 0 }

    let sortedA = A.sorted()
    
    for i in 0..<size - 2 {
        if sortedA[i] + sortedA[i+1] > sortedA[i + 2] { return 1 }
    }

    return 0
}

회고

배열의 크기가 3보다 작은 경우를 놓쳐서, 최초 풀이 정확도가 87% 나왔다.

항상 문제의 조건을 기억하자.

더 좋은 습관은, 항상 테스트 코드를 작성할 때 다음을 고려하는 것이다.

• 값이 없는 케이스
• 값이 아주 작거나, 아주 큰 케이스
• 0, 양수, 음수가 포함되는 케이스

https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

문제 분석

원소 3개를 곱했을 때, 최대가 되는 결과값을 구하라
 N = 100,000이므로 O(N^3)은 불가능
 정렬을 해서 가장 큰 값 3개를 곱하는 것은 반례가 있다
     절댓값이 더 큰 음수 2개를 곱하고, 가장 큰 양수를 곱하는 상황이 있다
     음수를 원소로 사용하려면, 반드시 2개를 곱해야 한다.
     즉 음수를 원소로 사용하려면, 반드시 가장 작은 원소 2개만 가능하다.
         그보다 작은 것은 최댓값이 아니다.
     따라서 가장 큰 양수 3개의 조합과, 가장 작은 음수 2개 + 가장 큰 양수 1개의 조합이 전부.

의사 코드

let size = A.count
 let sortedA = A.sorted() // 오름차순 정렬
 let onlyPositive = sortedA[size - 1] * sortedA[size - 2] * sortedA[size - 3]
 let withNegative = sortedA[0] * sortedA[1] * sortedA[size - 1]
 둘 중에 큰 값을 return

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    let sortedA = A.sorted()
    let onlyPositive = sortedA[size - 1] * sortedA[size - 2] * sortedA[size - 3]
    let withNegative = sortedA[0] * sortedA[1] * sortedA[size - 1]

    return onlyPositive > withNegative ? onlyPositive : withNegative
}

추가된 내용

A -> [-8, -7, -6, -5, -4, -3, -2, -1]
onlyPositive -> -6
withNegative -> -56

최초 풀이 당시에는 모든 원소가 음수인 케이스를 고려하지 않았지만, 이 경우도 가능하다.

이 케이스에서는 절댓값이 작은 음수 3개를 선택하는 경우가, 가장 큰 값을 반환하기 때문.

변수명은 바꿀 필요가 있겠다. onlyBack / withFront 정도로.

MinAvgTwoSlice coding task - Learn to Code - Codility

문제 분석

N개의 정수로 이루어진 배열 A
슬라이스 -> A[P...Q] 범위를 잘라서 평균을 구하는 것을 말함
A를 슬라이스 해서 가장 최소값을 얻도록 하는, P를 return
O(N^2)으로 모든 경우의 수를 따지면 쉽지만, N = 100,000이므로 시간 초과
이것저것 해봤지만 방법이 쉽게 떠오르지 않음 ...

구글링

평균값의 성질을 이용하는 문제라고 한다
1. 두 수의 평균을 구하면, 작은 수 < 평균 < 큰 수
2. 두 그룹의 평균를 구하면, 작은 그룹의 평균 < 전체 평균 < 큰 그룹의 평균
3. 따라서 작은 그룹의 평균이 최솟값이라면, 그것을 포함한 모든 그룹의 평균보다 작다.
4. 작은 그룹은? 원소가 2개인 경우 / 3개인 경우만 따지면 된다. (4개는 2개 * 2로 나눌 수 있다.)

의사코드

minIdx: 정답으로 return할 최소 인덱스
minAvg: minIdx의 판단 기준이 되는 최소 평균값
minIdx를 0으로, minAvg와 최초 2개 원소의 평균값으로 초기화 한다.

for 문으로 2부터 A의 길이만큼 탐색한다
    3개의 평균을 구한다
        i-2, i-1, i의 평균을 구하고, 최소값인지 판단한다
        맞다면, minAvg, minIdx를 갱신한다.
    2개의 평균을 구한다
        i-1, i의 평균을 구하고, 최소값인지 판단한다
        맞다면, minAvg, minIdx를 갱신한다.
    순서는 중요하지 않다.
minIdx를 return한다.

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var minIdx = 0
    var minAvg = (Double(A[0]) + Double(A[1])) / 2

    for i in 2..<A.count {
        let tmpAvgInThree = (Double(A[i-2]) + Double(A[i-1]) + Double(A[i])) / 3
        if minAvg > tmpAvgInThree {
            minAvg = tmpAvgInThree
            minIdx = i - 2
        }

        let tmpAvgInTwo = (Double(A[i-1]) + Double(A[i])) / 2
        if minAvg > tmpAvgInTwo {
            minAvg = tmpAvgInTwo
            minIdx = i - 1
        }
    }

    return minIdx
}

참고

https://nukeguys.tistory.com/175

GenomicRangeQuery coding task - Learn to Code - Codility

문제 분석

A, C, G, T : 1, 2, 3, 4에 대응하는 염기서열
P, Q 배열은 각각 범위에 대한 정보 -> [Pn...Qn]의 범위
해당 범위 내의 염기서열에 대응하는 factor의 값 중 가장 작은 것을 return
O(N * M) == 5 * 10 ** 9이므로, 시간 초과

의사 코드 (오답)

A C G T와 factor 값을 대응시킨 딕셔너리 생성
answer: [Int] 변수에 정답 저장
M만큼 반복하며, 매 반복마다, 주어진 S에서 Pn...Qn 범위에 해당하는 Array를 생성
    최솟값을 저장할 변수 
    Array를 탐색하며, 각 원소에 대응하는 factor를 딕셔너리로 접근하고, 최솟값을 갱신
    혹은 Array 생성 단계에서, factor 값으로 정수형 배열을 생성하고 min()
    반복 종료되면 answer에 append
return answer

나의 풀이 (오답)

import Foundation
import Glibc

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    let nucleotidesDict = ["A" : 1, "C": 2, "G": 3, "T": 4]
    let arrSize = P.count
    var answer = [Int]()

    for i in 0..<arrSize {
        let start = S.index(S.startIndex, offsetBy: P[i])
        let end = S.index(S.startIndex, offsetBy: Q[i])
        let minValue = S[start...end]
            .compactMap { nucleotidesDict[String($0)] }
            .min()!        
        answer.append(minValue)
    }

    return answer
}

// O(N * M)

시간 초과가 날 것을 알면서도 기본적인 방식으로 풀이해봤다.

.compactMap()을 사용하면 forced-unwrap을 하지 않아도 된다는 점,

메서드를 이어서 사용할 경우, 메서드마다 라인을 나누면 가독성이 낫다는 점을 배웠다.

더 나은 풀이

// 개선된 풀이
// S에서 A, C, G, T가 등장하는 횟수를 세는 누적합 배열을 각각 만들어준다.
// Pn...Qn 범위에서, 누적합 배열의 Qn - Pn의 값이 0보다 크면, 해당 문자가 있는 것
    // A > C > G > T의 우선도로 먼저 등장하는 것의 factor를 ans에 append

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    var a = Array(repeating: 0, count: S.count + 1)
    var c = Array(repeating: 0, count: S.count + 1)
    var g = Array(repeating: 0, count: S.count + 1)
    var t = Array(repeating: 0, count: S.count + 1)
    var ans: [Int] = []
    
    for (idx, i) in S.enumerated() {
        a[idx + 1] = a[idx]
        c[idx + 1] = c[idx]
        g[idx + 1] = g[idx]
        t[idx + 1] = t[idx]
        
        switch i {
        case "A":
            a[idx + 1] += 1
        case "C":
            c[idx + 1] += 1
        case "G":
            g[idx + 1] += 1
        default:
            t[idx + 1] += 1
            
        }
    }
    
    for i in 0..<P.count {
        if a[Q[i] + 1] - a[P[i]] > 0 {
            ans.append(1)
        } else if c[Q[i] + 1] - c[P[i]] > 0 {
            ans.append(2)
        } else if g[Q[i] + 1] - g[P[i]] > 0 {
            ans.append(3)
        } else {
            ans.append(4)
        }
    }
    
    return ans
}

// O(N + M)

풀이가 생각나지 않아 다른 블로그를 참고했다.

각 알파벳마다 누적합 배열을 만들고, S를 탐색하며 배열을 갱신한다.

이때 배열을 첫 번째 값을 0으로 설정하고, 배열의 길이를 S+1로 하는 것이 중요하다.

(Q[i] + 1) - (P[i])의 차이가 0보다 크면, 해당 염기서열에 대응하는 값을 ans에 추가한다. (이때 우선 순위는 A > C > G > T)

(Q[i] + 1) - (P[i])인 이유: 누적합 배열 길이가 S+1 이므로, 문자열 i == 누적합 배열 i +1

참고

https://borabong.tistory.com/37

https://woongsios.tistory.com/68

CountDiv coding task - Learn to Code - Codility

접근 방법

A...B 범위의 배열 안에서, K로 나누어 떨어지는 원소의 개수를 return
A...B의 범위가 최대 20억이므로, O(N)보다 효율적인 알고리즘이 필요함

의사 코드

정수론으로 접근하자면 B를 K로 나눈 값이 max / A를 K로 나눈 값이 min
    max - min에서 약간 조정하면 되지 않을까?
        A가 K로 나누어 떨어지는 경우: 값 - 1
        아닌 경우: 값

나의 풀이

import Foundation
import Glibc

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    
    let maxValue = B / K
    let minValue = A % K == 0 ? (A / K - 1) : (A / K)
    
    return maxValue - minValue
}

후기

범위에 B를 포함해야 하나? 싶어서 조금 시간이 걸렸다.
문제 자체는 medium 난도도 아니고, prefixSum 카테고리도 아닌 듯하다.

Swift에서 Int끼리 나눗셈을 하면 "내림" 처리가 된다.

https://school.programmers.co.kr/learn/courses/30/lessons/43162

접근 방법

[i][j] 값이 1인 연결 행렬을 받아서, 서로소 집합의 개수를 센다.
Union-Find로 풀이하면 될 듯
시간복잡도는 최악의 경우 Union과 Find 각각 O(N)에 준하는 수준이다.

의사 코드

크기가 n인, 루트 노드의 정보를 담는 배열 생성
find()를 정의. 시간복잡도를 위해 경로 압축한 형태로.
union()을 정의. 노드 번호가 빠른 것이 루트 노드로 갈 수 있도록 구현
computers를 탐색하여, i != j인 경우, union 연산을 실행
루트 노드의 정보를 Set으로 변환하여 네트워크가 몇 가지인지 return

나의 풀이 + chatGPT

import Foundation

func find(_ x: Int, _ rootArr: inout [Int]) -> Int {
    if rootArr[x] != x {
        rootArr[x] = find(rootArr[x], &rootArr)
    }
    return rootArr[x]
}

func union(_ x: Int, _ y: Int, _ rootArr: inout [Int]) {
    let rootX = find(x, &rootArr)
    let rootY = find(y, &rootArr)
    if rootX < rootY {
        rootArr[rootY] = rootX
    } else {
        rootArr[rootX] = rootY
    }
}

func solution(_ n: Int, _ computers: [[Int]]) -> Int {
    var rootArr = Array(0..<n)

    for i in 0..<n {
        for j in 0..<n {
            if i != j {
                union(i, j, &rootArr)
            }
        }
    }

    let uniqueNetworks = Set(rootArr.map { find($0, &rootArr) }) // 헷갈린 부분
    return uniqueNetworks.count
}

도움을 받은 부분은 uniqueNetworks 변수를 초기화 할 때, rootArr의 각 원소에 find() 함수를 적용하는 부분이다.

find() 함수에서 이미 경로 압축을 진행했기에, 다시 find()를 하는 과정이 필요 없을 것이라고 판단했다.

그러나 union() 연산을 적용하지 않는 원소가 있는 경우, 반드시 해당 원소들에 대해서도 find() 연산을 적용해야 한다.

참고

Union-Find 개념: https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

Union-Find 시간 복잡도: https://8iggy.tistory.com/157

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=swift

접근 방법

모든 경우의 수를 따지려면 DFS가 적합하겠다.
시간 복잡도는 O(2^N)이지만, 2 ** 20 ≈ 1,000,000이므로 가능하다.

방향이 두 가지(+, -)가 있는 그래프를 탐색한다고 생각하면 쉽다.
dfs 함수가 재귀적으로 + / - 의 경우를 각각 호출하고,
깊이가 numbers와 같아지면, target과 비교하여 cnt하는 방식으로 풀어보자.

의사 코드

func dfs(depth:int, sum:Int) -> Int
     depth == numbers.size && sum == target인 경우 cnt += 1
     depth + 1이 범위(numbers.size) // 벗어나면 return
     // 두 가지 방향 재귀적으로 탐색
     dfs(depth + 1, sum + numbers[depth + 1])
     dfs(depth + 1, sum - numbers[depth + 1])

 func solution()
 dfs(-1, 0) 호출
 return cnt

나의 풀이

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {

    func dfs(_ depth: Int, _ sum: Int) {
        if depth == numbers.count - 1 && sum == target {
            cnt += 1
            return // 재귀 탐색 종료
        }

        // depth + 1이 범위(numbers.count)보다 작으면 진행, 벗어나면 return
        guard depth + 1 < numbers.count else { return }

        // 두 가지 방향 재귀적으로 탐색
        dfs(depth + 1, sum + numbers[depth + 1])
        dfs(depth + 1, sum - numbers[depth + 1])
    }
    
    var cnt = 0
    dfs(-1, 0) // 첫 번째 인덱스부터 방향이 갈리므로

    return cnt
}

의사 코드에서는 함수를 분리했지만, cnt 변수를 관리하는 것이 까다로워서 중첩으로 풀이.

특별한 점은 없고, Swift의 경우에는 index가 벗어나는 것을 guard로 관리하면 깔끔하다.

더 나은 풀이

import Foundation

func dfs(_ depth: Int, _ sum: Int, _ numbers: [Int], _ target: Int) -> Int {
    if depth == numbers.count - 1 {
        return sum == target ? 1 : 0
    }
    // 다음 깊이로 재귀 호출하고, 각 경우의 수를 더함
    return dfs(depth + 1, sum + numbers[depth + 1], numbers, target) +
           dfs(depth + 1, sum - numbers[depth + 1], numbers, target)
}

func solution(_ numbers: [Int], _ target: Int) -> Int {
    return dfs(-1, 0, numbers, target)
}

이 풀이가 압도적으로 깔끔하고, 관리하기도 좋다.

SOLID의 단일 책임 원칙(SRP)을 잘 지키고 있다.

또한 다른 함수의 변수에 접근하려면, 현재 함수의 매개변수로 넘겨줘야 한다는 것을 기억하자.

주목할 부분은 경우의 수를 세는 cnt 변수를 따로 관리하고 있지 않다는 점이다.

위 코드에서는 재귀 함수가 두 가지 경우의 반환값의 합을 return 하고 있다.

이렇게 하면 별도 변수 없이도 stack에 반환값을 관리할 수 있다.

이것을 반드시 기억하자.

2559번: 수열

문제 분석

크기가 N인 배열을 받아서, K의 간격으로 구간합을 구하고,
 구간합 결과의 리스트 중에서 가장 큰 값을 return 하는 문제
 N의 크기가 100,000 이므로, O(N^2)의 접근은 불가하다.
 1. 가장 단순한 방법
     배열을 탐색하며, K 간격의 구간합을 모두 구해서 최대값을 return
     K는 1..<N이므로, K가 N인 경우에 O(N^2)이 되므로 불가하다.
 2. 슬라이딩 윈도우 식으로
     최초 구간합을 구하고, 한 칸식 우측으로 밀어가면서, head를 빼고, tail을 더하는 방식
     무난한 O(N)으로 가능해 보인다.

의사 코드

n, k에 입력을 받는다.
degreesArr 배열에 입력을 받는다.
window: Int, 구간합, 최초 K개의 합으로 초기화 한다.
maxValue: Int, return할 최대값, window로 초기화 한다.
for i in 0..<n - k 의 범위를 탐색한다.
    maxValue = maxValue > tmpWindow ? maxValue : tmpWindow
maxValue를 return 한다.

나의 풀이

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0], k = input[1]
let degreesArr = readLine()!.split(separator: " ").map { Int($0)! }

var window = degreesArr[0..<k].reduce(0) { $0 + $1 }
var maxValue = window

for i in 0..<n - k {
    window = window - degreesArr[i] + degreesArr[i + k]
    maxValue = maxValue > window ? maxValue : window
}

print(maxValue)

회고

백준에서 입력 받는 법을 연습해봤다.

let n = input[0], k = input[1] 이렇게 입력 받는 형태를 기억하자.