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끼리 나눗셈을 하면 "내림" 처리가 된다.

PassingCars coding task - Learn to Code - Codility

회고

문제 이해가 난데없이 어려웠다.
'passing cars' 라고 하면 '지나가는 차' 같지 않은가 ?
그렇지만 문제에서 의도했던 것은, '지나가다'가 아니라 '마주치다'의 의미로 해석하는 것이었다.
또 '마주치는' 자동차가 아니라, '마주칠 예정인' 자동차로 해석하는 것이 풀이에 이롭다.

문제를 이해하고 나니 어려운 문제는 아니었다.
배열의 정보를 받아서 '마주칠 예정인 인덱스의 조합'의 개수를 return 하면 된다.
다시 말해, 0 뒤에 나오는 모든 1은 마주칠 예정이다. 1에 관점에서 보아도 같다.

접근

<접근>
1. 이중 탐색
    배열을 앞에서부터 탐색한다.
    현재 인덱스의 방향(숫자)와 다른 방향으로 가는 원소의 개수를 count한다. O(N^2)

2. 누적합, 구간합
    cnt 변수를 만든다.
    기존 배열을 탐색하며, 값이 0인 인덱스와 마지막 인덱스 사이의 구간합을 cnt에 더한다.
    탐색이 완료되면, cnt를 return 한다.

3. 1의 관점에서 생각하기
    현재 인덱스의 값이 0이라면 cnt += 1
    현재 인덱스의 값이 1이라면 answer += cnt
    answer를 리턴한다.

나의 풀이 (2번 풀이)

// O(N)
import Foundation

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    var prefixSum = Array(repeating: 0, count: size)
    var answer = 0

    for i in 0..<size {
        if i == 0 { 
            prefixSum[i] = A[i]
            continue
        }
        prefixSum[i] = prefixSum[i-1] + A[i]
    }

    for i in 0..<size {
        if A[i] == 0 {
            answer += prefixSum[size - 1] - prefixSum[i]
        }
    }

    return answer <= 1000000000 ? answer : -1
}

나의 풀이 (3번 풀이)

// O(N)
import Foundation

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    var cnt = 0
    var answer = 0

    for i in 0..<size {
        let currentValue = A[i]
        
        switch currentValue {
            case 0:
                cnt += 1
            default: // 1
                answer += cnt
        }
    }

    return answer <= 1000000000 ? answer : -1
}

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

요약

O(N) or O(N * log(N))

88 → 100

쉬운 문제였다.

첫 번째 풀이에 중복 제거를 고려하지 못 했다.

정답 제출에 조금 더 신중해 보자.

접근

// 문제 분석
// 배열에 없는, 0보다 큰, 가장 작은 정수를 return 하라

// 접근
// 배열 A의 길이는 1...100,000. 따라서 O(N^2) 불가능
// 쉽게 생각나는 방법은 100,000 크기의 check 배열을 생성한 후에, O(N)
    // A를 탐색하며 True로 바꾸고 O(N)
    // 가장 먼저 등장하는 False의 index를 return 하는 것. filter의 시간복잡도? 정렬이 아니고 탐색이니까 O(N)일 듯하다.

// 두 번째 방법은 A 배열을 오름차순으로 정렬하고 O(NlogN)
// 배열을 탐색하며, 1부터 1씩 증가하는 변수와 비교하여, 현재 원소와 일치하지 않는 순간 return. O(N)

// 땡기는 두 번째 먼저 풀어보고, 안 되면 첫 번째로 풀자

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    // 두 번째 방법은 A 배열을 오름차순으로 정렬하고 O(NlogN)
    // 정렬하기 전에 중복 제거를 해주어야 함.
    let sortedA = Array(Set(A)).sorted() // 오름차순
    var counter = 0
    // 배열을 탐색하며, 1부터 1씩 증가하는 변수와 비교하여, 현재 원소와 일치하지 않는 순간 return. O(N)
    for elem in sortedA {
        if elem <= 0 { continue } // 음수는 빼고 count
        counter += 1
        if counter != elem {
            return counter 
        }
    }

    return counter + 1
}

MaxCounters coding task - Learn to Code - Codility

요약

88 → 100

효율성 문제로 조금 고민했던 문제이다.

최초 풀이에서는 max counter 연산 때, 새로운 배열을 만들어서 전달했는데,

Array() 생성의 시간복잡도는 O(N)이었다.

그도 그럴 것이, 배열의 길이만큼 메모리를 한 칸씩 이동하며 초기화 해주어야 하니까.

수정한 접근 방법에서, 변수를 따로 관리해야 하는 이유를 잠시 고민했다.

maxValue 값을 추적하는 시점과, 값을 갱신하는 시점이 달라야 하기 때문에, 2개의 변수(maxValue, maxTmp)를 사용해야 한다.

접근

최초 접근

// 문제 분석
// A 배열은 명령어를 원소를 갖는다. (원소의 개수는 M, 랜덤이다)
    // 해당 명령어는 N개의 카운터에 대한 명령어의 집합이다.
    // A 배열의 원소(명령어)는 1...N+1 범위에서 정해진다
    // 1) 1...N은 해당 인덱스에 += 1
    // 2) N+1은 전체 카운터를, 현재의 max 값으로
// 카운터에 모든 명령어를 적용하고, 카운터에의 최종 형태를 return 한다.

// 접근법 분석
// N과 M은 각각 100,000이다
// O(N * M)은 시간 초과가 날 듯
// 간단한 방법은 A 배열을 탐색하며, 카운터 배열을 수정하는 방법이다.
    // maxValue를 따로 관리하고, 2) 명령어를 수행할 때, 배열 전체를 교체하는 방법을 쓰면,

수정한 접근

// 연산을 다르게 접근하자
// increase: 현재 인덱스의 값을 maxValue로 갱신한 뒤에, += 1, maxTmp를 갱신
    // 해당 연산에서 maxTmp를 갱신해야, 시간의 낭비가 없음
// max counter: maxValue 값을 maxTmp로 갱신함
    // 변수를 따로 관리하는 이유.
    // 가장 큰 값에 대한 추적을 사실상 increase 연산에서 하고 있으므로, 
    // max counter 연산이 수행될 때에만 maxValue 값을 업데이트 하고 싶으면, 
    // 변수를 따로 관리해야 함.

최초 풀이

import Foundation
import Glibc

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var counter = Array(repeating: 0 , count: N)
    var maxValue = 0
    
    for operation in A {
        switch operation {
            case 1...N:
                counter[operation - 1] += 1
                let currentIdxValue = counter[operation - 1]
                if currentIdxValue > maxValue {
                    maxValue += 1
                }
            default: // N + 1
                counter = Array(repeating: maxValue, count: N)
        }
    }

    return counter
}

수정한 풀이

import Foundation
import Glibc

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var counter = Array(repeating: 0, count: N)
    var maxValue = 0, maxTmp = 0

    for operation in A {
        switch operation {
            case N + 1:
                maxValue = maxTmp
            default:
                counter[operation - 1] = max(maxValue, counter[operation - 1]) + 1
                maxTmp = max(counter[operation - 1], maxTmp)
        }
    }

    for (idx, elem) in counter.enumerated() {
        counter[idx] = max(elem, maxValue)
    }

    return counter
}