https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

요약

92 → 100

풀이의 접근은 제대로 한 듯하다.

탐색의 범위가 헷갈렸는데, 나의 잘못과 문제의 잘못이 반반이라고 생각한다.

나의 잘못: 분명 배열을 둘로 나누라고 했으나, 포인터 == size - 1인 경우에는 나뉘지 않는다. 따라서 size - 2까지만 탐색하는 것이 맞다.

문제의 잘못: 포인터의 범위를 0 < P < N로 줬다. 둘로 나뉘지 않는 경우를 방지하기 위해 0을 제외했으면, N - 1까지 제외해야 하는 것 아닌가?

과실 비율은 나 : 문제 = 90 : 10

접근

// 배열을 두 부분으로 나누어서, 각각의 합을 구하고, 두 개의 합의 차이가 최소되는 경우를 구하시오.
// 배열을 한 번 탐색하면서, 현재 포인터 위치의 값을, 각각 합을 저장하는 변수에 빼고 더하고 계속 하다 보면 알 수 있겠다. O(n)
    // let size = A.count
    // var pointer = 1
    // var leftSum = A[0]
    // var rightSum = A[1:].reduce { $0 + $1 }
    // var minValue = leftSum
    // for i in 2..<size {
        // leftSum += A[i]
        // rightSum -= A[i]
        // if leftSum < minValue { minValue = leftSum }
    // }
    // return minValue
// 더 좋은 방법O(1)이 있을까?

나의 풀이

import Foundation
import Glibc

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

    var leftSum = A[0]
    var rightSum = A.reduce(0, { $0 + $1 }) - leftSum
    var minSum = abs(leftSum - rightSum)

    for i in 1..<size-1 { // 탐색 범위가 헷갈렸다. // 나눠야 하니까
        leftSum += A[i]
        rightSum -= A[i]
        let tmpSum = abs(leftSum - rightSum)
        if tmpSum < minSum { minSum = tmpSum }
    }

    return minSum
}

PermMissingElem coding task - Learn to Code - Codility

요약

80 → 100

처음에 문제 이해가 부족해서, 정답 제출 후 헤매다가 빠진 케이스를 찾아냈다.

그러나 이렇게 푸는 문제가 아니었다 ㅋㅋ

더 나은 풀이를 확인하면 아주 수학적으로 멋지게 해결하더라.

지금까지 코딜리티 문제들은 수학적으로 접근하는 것을 선호하는 듯하다.

마치 비문학을 읽고, 의사 코드를 적어서 제출하는 듯한 프로그래머스와는 다른 부분이다.

나의 풀이

import Foundation
import Glibc

// 문제가 헷갈리는데, [1..(N+1)] 범위의 정수형 원소가 담긴 배열에서, 사라진 하나의 원소를 찾는 것 같다. /
// 범위가 다소 애매하다. [1..(N+1)]이면 [1..<N+1]을 의미하는 것인가? 그러면 사라진 원소가 없을텐데...

// 일단 가정대로 풀이하자.
// let size = A.count
// var checkArr: Array(repeating: false, count: size + 1)
// checkArr[0] = true
// for i in 0..<A.count { 
    // checkArr[A[i]] == false {
        // checkArr[A[i]] = true
//    }
// }
// checkArr[i]가 false인 index 반환

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

    if size == 0 { return 1 }
    if size == 1 { return A[0] == 1 ? 2 : 1 }

    var checkArr = Array(repeating: false, count: size + 2)
    checkArr[0] = true // 1..<N+1의 범위이므로 0은 미리 true로 처리
    for i in 0..<A.count {
        if checkArr[A[i]] == false {
            checkArr[A[i]] = true
        }
    }

    if let idx = checkArr.firstIndex(where: { $0 == false }) {
        return idx
    } else {
        return 0
    }
}

더 나은 풀이

public func solution(_ A : inout [Int]) -> Int {
    var sum = 0
    
    let N = A.count
    let totalSum = (N + 1) * (N + 2) / 2  // N이 주어 졌을때 기대되는 전체 정수의 합을 구해줍니다. 보통 1~10까지의 합을 구하려면 (N+(N+1)) / 2로 계산할 수 있습니다.
    
    for element in A { // 현재 배열의 각 원소의 합을 구합니다.
        sum += element
    }
    
    return totalSum - sum  // 기대되는 원소의 합에서 실제 원소의 합을 빼면 비어있는 정수를 구할 수 있습니다.
}

// <https://jusung.github.io/Codility-Lesson3(Time-Complexity)-PermMissingElem/>

FrogJmp coding task - Learn to Code - Codility

요약

쉬운 문제였다.

ceil() 함수를 사용하면 더 깔끔하게 풀이가 가능하다.

나눗셈 연산을 하기 위해서는 변수의 타입을 모두 Double로 변환해야 함을 기억하자.

나의 풀이

// easy peasy lemon squeezy
// X 위치에서 D만큼씩 이동할 수 있다
// Y 이상이 되는 최소 이동 횟수를 구하라

// 직관적으로 떠오르는 풀이
// X와 Y 사이의 거리를 구함. Dist = Y - X
    // 예외처리: if Dist == 0: return 0
// 거리를 D로 나누고, 나머지가 있으면 += 1

import Foundation
import Glibc

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
    let dist = Y - X
    if dist == 0 { return 0 }
    var div = dist / D
    let mod = dist % D
    if mod > 0 { div += 1}
    return div
}

더 나은 풀이

public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
        let doubleX = Double(X)
        let doubleY = Double(Y)
        let doubleD = Double(D)

        return Int(ceil((doubleY - doubleX) / doubleD)) // 소수점은 ceil함수로 무조건 올림해줍니다.
    }

// <https://jusung.github.io/Codility-Lesson3(Time-Complexity)-FrogJmp/>

https://app.codility.com/programmers/lessons/2-arrays/

요약

간단한 문제임에도 문제 접근에 시간이 꽤 걸렸다. (15분)

unpaired value는 1개만 나온다고 착각했지만, 홀수개였다. 문제를 잘 읽자.

XOR에 대하여

더 나은 풀이에 대한 내용이다.

XOR 연산자는 다음과 같은 특성이 있다.

같은 수를 XOR 연산하면 없어진다. 순서는 상관 없다.

3 == 0011

5 == 0101

1 == 0001

• 3^5^5 == 0011 (3)
• 3^5^5^3 == 0000
• 3^3 == 0000
• 3^3^5 == 0101 (5)
• 3^1^3^1^3^1^3^1^5 == 0101 (5)

검색한 것

• dictionary 내에 key 여부를 파악하는 법
  • Swift의 기본 기능으로 없으면 nil을 반환한다
• dictionary의 첫 번째 원소의 key를 반환하는 법
  • .first! / .last! (딕셔너리는 기본적으로 옵셔널을 반환하므로, forced-unwrapping)
  • .key / .value

나의 풀이

// A 배열의 길이는 1 ~ 1,000,000 이하 
    // -> Empty 배열에 대한 처리는 따로 하지 않아도 좋다
    // NlogN까지만 괜찮다
// 원소는 1 ~ 1,000,000,000

// 한 번만 나오는 원소를 출력하면 되지 않는가?
// 배열을 전부 탐색하면서 원소를 cnt 한다.
    // 딕셔너리에 해당 키가 없으면, 키를 생성하고 cnt = 1
    // 키가 있으면, cnt += 1
// 탐색을 종료하면, 딕셔너리를 값을 기준으로 정렬하여, 최소 값의 키를 반환한다.

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var countDict: [Int: Int] = [:]
    A.forEach {
        if countDict[$0] != nil {
            countDict[$0]! += 1
        } else {
            countDict[$0] = 1
        }
    }

    let sortedCountDict = countDict.filter { $0.1 % 2 != 0 }
    
    return sortedCountDict.first!.key
}

더 나은 풀이

public func solution(_ A : inout [Int]) -> Int {
    return A.reduce(0){ $0^$1 }
}

// 어이 없는 풀이 ㅋㅋ

https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

요약

87점 → 100점.

N == 0인 경우를 체크하지 않았다. 이런 건 기본이기도 하고, 기본 테케에서 보여주지 않으니까 잘 챙기자.

검색한 것

• 함수의 파라미터 변수에 inout:
  • copy-in-copy-out. 파라미터 변수를 변경할 수 있게 된다.
  • 원리는 변경이 필요할 때, 초기값을 복사해서 복사된 값을 변경한다. return할 때 복사된 값을 return한다.
  • 함수를 호출할 때는 add(&a: 3, b: 4) 이런 식으로 한다.
• reverse(), reversed():
  • reverse() → void / O(N)
  • reversed() → ReversedCollection<Self> / O(1)

나의 풀이

// 배열의 길이가 101이므로 O(n)으로 가능하다.
// 역순으로 된 큐라고 생각하면 쉽다.
    // 6 7 9 8 3 뒤집기
    // 7 9 8 3 6 dequeue -> enqueue
    // 9 8 3 6 7 dequeue -> enqueue
    // 8 3 6 7 9 dequeue -> enqueue
    // 9 7 6 3 8 뒤집기

// 최적화를 위해서는 N을 K로 나눈 나머지 만큼만 움직이면 된다.

import Foundation
import Glibc

public func solution(_ A : inout [Int], _ K : Int) -> [Int] {
    if A.isEmpty {
        return []
    }

    let move = K % A.count
    
    A.reverse()
    for _ in 0..<move {
        let front = A.removeFirst()
        A.append(front)
    }
    A.reverse()

    return A
}

더 나은 풀이

public func solution(_ A : inout [Int], _ K : Int) -> [Int] {
    if A.count == K || K == 0 || A.count == 0 { return A }
    let rotation = K % A.count
    let range = 0...(A.count - 1 - rotation)
    let firstPick = A[range]
    A.removeSubrange(range)
    return A + firstPick
}

// https://muizidn.medium.com/codility-cylicrotation-swift-2008877b2a71

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

요약

여전히 컴퓨팅 사고가 부족하다고 느낀다.

나의 풀이는 전형적으로 문자열을 만들어서 하나씩 더듬어 가며 탐색하는 풀이. 심지어 틀렸다.

GPT는 이진수를 만들지 않고 나눗셈으로 찾아가는 풀이.

반성하자.

이진수, 3진수, 8진수, 16진수 <-> 10진수의 변환은 자연스럽게 가능해야 한다.

나의 풀이 (오답)

import Foundation
import Glibc

// N이 21억이면 2진수인 문자열로 바꿔서 O(n)하면 터지나 ?
// 정수형을 이진수 형태 문자열로 변환
// 투포인터를 활용하면 될 듯 (i, j)
// i로 문자열을 탐색하면서 1을 찾음
// 1을 만나면 j = i + 1. while 문으로 다음 1을 만날 때까지 0을 count
// 1을 만나면 count된 0의 개수가, 최대값인지 확인 후 최대값이면 갱신, i = j + 1에 할당, 그리고 break
// 문자열을 끝까지 탐색하면 종료

public func solution(_ N : Int) -> Int {
let binaryStr = String(N, radix: 2)
let binaryStrSize = binaryStr.count
let firstIdx = binaryStr.startIndex
var i = 0
var maxCnt = 0

while i < binaryStrSize {
    if binaryStr[binaryStr.index(firstIdx, offsetBy: i)] == "1" {
        var j = i + 1
        var cnt = 0
        while j < binaryStrSize && i < j{
            if binaryStr[binaryStr.index(firstIdx, offsetBy: j)] == "0" {
                cnt += 1
                j += 1
            } else {
                maxCnt = cnt > maxCnt ? cnt : maxCnt
                i = j + 1
                break
            }
        }
        // 이 부분을 추가해야 무한 반복을 막을 수 있다
        if j == binaryStrSize {
            i = j
        }
    } else {
        i += 1
    }
}

return maxCnt

더 나은 풀이

public func solution(_ N : Int) -> Int {
    var n = N
    var distance = -1
    var maxDistance = 0
    while n > 0 {
        if n % 2 == 1 {
            maxDistance = max(maxDistance, distance)
            distance = 0
        } else if distance != -1 {
            distance += 1
        }
        n /= 2
    }
    return maxDistance
}