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

접근 방법

배열의 크기는 최대 10 ** 4 이므로, O(N^2)까지 괜찮겠다.
1. 각각의 패턴 대로 길이 10 ** 4의 배열을 미리 생성해놓고 비교하면 O(N)으로 가능.
    단, 메모리 공간이 3 * 0(N)만큼 추가적으로 소모
2. 각 패턴의 점화식을 만들어서 비교. O(N)
    메모리 공간의 낭비도 거의 없다.
    그러나 실제 코테에서는, 완탐으로도 O(N)의 풀이가 가능한데, 굳이 점화식을 만들 필요는 없겠다.

나의 풀이

import Foundation

func solution(_ answers:[Int]) -> [Int] {
    let size = answers.count
    let multipleValue = Int(pow(10.0, 3))
    var resultArr = [0, 0, 0]
    let studentOne = Array(repeating: [1, 2, 3, 4, 5, 1, 2, 3, 4, 5], count: multipleValue).flatMap { $0 }
    let studentTwo = Array(repeating: [2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5], count: multipleValue).flatMap { $0 }
    let studentThree = Array(repeating: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5], count: multipleValue).flatMap { $0 }
    
    for i in 0..<size {
        let currentAnswer = answers[i]
        
        if currentAnswer == studentOne[i] { resultArr[0] += 1 }
        if currentAnswer == studentTwo[i] { resultArr[1] += 1 }
        if currentAnswer == studentThree[i] { resultArr[2] += 1 }
    }
    
    let highestScore = resultArr.max()!

    return resultArr.indices.filter { resultArr[$0] == highestScore }.map { $0 + 1 }
}

배열을 repeating 할 때는, flatMap을 사용해서 2차원 배열을 1차원으로 변경해 주어야 한다.

filter 된 값의 index를 return 하고 싶다면, indices를 활용하자.

단, filter의 결과가 index로 반환된다는 것을 유의하자.

다른 사람 풀이

import Foundation

func solution(_ answers:[Int]) -> [Int] {
    let answer = (
        a: [1, 2, 3, 4, 5], // index % 5
        b: [2, 1, 2, 3, 2, 4, 2, 5], // index % 8
        c: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] // index % 10
    )
    var point = [1:0, 2:0, 3:0]

    for (i, v) in answers.enumerated() {
        if v == answer.a[i % 5] { point[1] = point[1]! + 1 }
        if v == answer.b[i % 8] { point[2] = point[2]! + 1 }
        if v == answer.c[i % 10] { point[3] = point[3]! + 1 }
    }

    return point.sorted{ $0.key < $1.key }.filter{ $0.value == point.values.max() }.map{ $0.key }
}

// <https://school.programmers.co.kr/learn/courses/30/lessons/42840/solution_groups?language=swift>

최초 패턴만 메모리에 저장하고, 나눗셈을 활용하는 접근 방식이 좋다.

점수를 저장하기 위한 자료구조로 딕셔너리를 사용한 것도 좋다.

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

문제 분석

n의 크기는 10 ** 4이므로, O(N^2)까지는 괜찮겠다.
2차원 배열을 탐색하며, 가로와 세로 길이를 각각의 배열에 저장한 뒤에, 각 배열의 max를 곱한 것을 return
가로 <-> 세로를 바꾸는 것이 가능하므로, 각 배열에 저장하기 전에, 비교를 통해 큰 값 / 작은 값으로 분류하는 것이 낫겠다.

의사 코드

sizes 배열을 forEach로 탐색한다.
    if $0 > $1인 경우에, 큰 값 배열에 $0을, 작은 값 배열에 $1을 추가한다, else 라면 반대로 한다.
큰 값 배열, 작은 값 배열에서 각각 .max() 값을 구해 곱한 값을 return 한다.

나의 풀이

import Foundation

func solution(_ sizes:[[Int]]) -> Int {
    
    var biggerArr = [Int]()
    var smallerArr = [Int]()
    var answer = 0
    // sizes 배열을 forEach로 탐색한다.
    sizes.forEach {
        // if $0 > $1인 경우에, 큰 값 배열에 $0을, 작은 값 배열에 $1을 추가한다,
        // else 라면 반대로 한다.
        biggerArr.append( $0[0] > $0[1] ? $0[0] : $0[1] )
        smallerArr.append( $0[0] > $0[1] ? $0[1] : $0[0] )
    }
    // 큰 값 배열, 작은 값 배열에서 각각 .max() 값을 구해 곱한 값을 return 한다.
    answer = biggerArr.max()! * smallerArr.max()!
    return answer
}

https://softeer.ai/practice/6289

회고

현대오토에버 코테를 준비하기 위해, 출제 플랫폼인 소프티어에서 맛 좀 봤다.
가장 놀라운 것은 Swift 채점을 지원하지 않는다 ...!
그래서 예전 기억을 더듬거리며 Python으로 풀었다.

- 소프티어의 특징은, 입력값을 직접 받아야 한다.
    - 코딜리티와 프로그래머스와는 다르다.
    - 따라서 Swift로 입력값 받는 연습을 해야겠다.
- 코드를 수동으로 저장해야 한다.
- 공식 문서가 제공된다.
- 에러 내용이 제공된다.
- 자동 완성을 지원한다.

문제 자체는 LV.3인데도 불구하고 쉬웠다.
그래프를 생성해서, 인접한 노드와 값을 비교하기만 하면 되는 문제였다.

접근

N, M
N: 각 회원이 들 수 있는 무게
M: 친분 관계

N명의 회원을 탐색하며, (인접 리스트로 구현한다, 방향이 없는 무향 그래프가 되어야 한다)
연결된 모든 회원과 비교
비교 결과, 자기 자신이 가장 높으면 ans += 1

인접 리스트와 인접 행렬 중에서, 인접 리스트를 선택한 이유는 아래와 같다.

노드 최대 개수(N): 10 ** 5
간선 최대 개수(E): 10 ** 5
인접 행렬: 공간 복잡도 O(N^2) / 노드 하나당 시간 복잡도 O(N); 항상 O(N)
인접 리스트: 공간 복잡도 O(E) / 노드 하나당 시간 복잡도 O(E); 모든 노드가 O(E)인 경우는 드물다.

나의 풀이

import sys

n, m = map(int, input().split())
recordArr = list(map(int, input().split()))
adjancyList = [[] for _ in range(n+1)] # 아래에 입력될 노드 번호가 1~5이므로, indexError를 방지하기 위해 n+1
ans = 0

# 연결 리스트 생성
for i in range(m):
    a, b = map(int, input().split())
    # 방향이 없으므로 양쪽 모두 연결
    adjancyList[a].append(b)
    adjancyList[b].append(a)

# 모든 회원 탐색하며 비교
for i in range(1, n+1):
    isBiggest = True
    for adjElem in adjancyList[i]:
        if recordArr[adjElem - 1] >= recordArr[i - 1]: # Biggest 해야 하니까 같은 기록이 있는 경우도 안 된다
            isBiggest = False
            break
    
    if isBiggest:
        ans += 1

print(ans)

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
}

PermCheck coding task - Learn to Code - Codility

요약

56 → 100

1. Array → Set은 쉽게 가능하다. Set(Array<>)
2. .max(), .min(), .count는 각각 메서드, 메서드, 프로퍼티라는 것을 기억하자.
3. 최대 1,000,000,000 크기의 배열을 O(n)으로 탐색하는 것은, 시간 초과가 발생하지 않았음을 기억하자.

접근

// permutation이 성립하는 경우 1, 그렇지 않은 경우 0 return
// A 배열의 길이는 1,000,000,000이다. O(N)이 가능할까 ?
// 쉬운 접근은 Set을 활용하는 것이다.
// 배열을 탐색하며 Set에 추가하고, Set.count == N을 출력하면 된다.

// 또 다른 힌트는 permutation의 정의가, 1...N의 범위가 한 번씩만 등장한다는 것이다.
// 따라서 A의 크기가 N과 다른 경우 return 0이다.
// else N과 같다면, Set(A)의 크기까지 N과 같은 경우 return 1이다.

// 다행히 Array를 Set으로 쉽게 바꿀 수 있다. Set(Array)

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let setA = Set(A)
    let maxValueOfA = A.max()
    let sizeOfA = A.count
    let sizeOfSetA = setA.count

    guard sizeOfA == maxValueOfA else { return 0 }
    guard sizeOfSetA == maxValueOfA else { return 0 }

    return 1
}

FrogRiverOne coding task - Learn to Code - Codility

요약

1. 문제를 꼼꼼히 읽자. 조건을 달성할 수 없는 경우 return -1 하라는 부분을 놓쳤다.
2. 예외 처리가 항상 아쉽다. 빈출 예외는 항상 고려하자 (0, 1, -1, 조건을 달성할 수 없는 경우, 극단값, …)

더 나은 풀이를 보고 …

1. Set을 활용하는 게 훨씬 간편하다.
2. 예외 처리를 할 때는 guard 문을 적극 활용하자.

접근

// 쉽게 느껴진다
// 배열을 탐색하며, 1...N에 해당하는 값이 최소 한 번씩 등장하는, 최소 시간을 구하는 것이다.
// 1. 무식하게 처음부터 탐색한다. O(N). 배열의 크기가 100,000 이하 이므로 가능하다.
    // cnt. checkArr 배열을 방문할 때마다 += 1
    // 1...N의 합을 구한다. totSum. 새로운 숫자를 탐색할 때마다 totSum에서 뺀다.
    // 1...N에 대응하는 checkArr를 생성한다. 방문할 때마다 totSum에서 제거하고, true로 바꾼다.
    // totSum == 0 && checkArr 배열이 모두 true인 경우 count를 return한다.

나의 풀이

import Foundation
import Glibc

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    let size = A.count
    if size < X { return -1 }
    var cnt = 0
    var totSum = X * (X + 1) / 2
    var checkArr = Array(repeating: false, count: X + 1)
    checkArr[0] = true // 1...size 범위만 사용하기 위함

    for i in 0..<size {
        cnt += 1
        
        if checkArr[A[i]] == false {
            checkArr[A[i]] = true
            totSum -= A[i]
        }

        if totSum == 0 && checkArr.filter({ $0 == false }).count == 0 {
            return cnt - 1
        }
    }

    return -1
}

더 나은 풀이

import Foundation

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    guard !A.isEmpty else { return -1 } //비어있는 배열은 존재할 수 없다.
    guard A.count >= X else { return -1 } //A의 개수가 X보다 작다면 절대 건너지 못한다.

    var leaves: Set = []
    var result = -1
    for (i, num) in A.enumerated() {
        leaves.insert(num)
        if leaves.count == X {
            result = i //index가 초임
            break
        }
    }

    return result
}

// <https://jeong9216.tistory.com/435#%EC%A0%84%EC%B2%B4-%EC%BD%94%EB%93%9C>