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] 이렇게 입력 받는 형태를 기억하자.

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
}

Swift에서 class와 struct의 공통점은 '데이터를 캡슐화'하고, '사용자 정의 데이터 타입을 생성'하는 것이다.

그러나 메모리 관리 측면에서 중요한 차이점이 있다.

1. Value Type과 Reference Type

Struct (Value Type):

• struct는 Swift에서 값 타입(value type)이다.
• 값 타입은 변수에 할당되거나 함수에 전달될 때 그 값이 복사된다.
• 각각의 인스턴스는 고유한 데이터 복사본을 가지며, 다른 인스턴스와 독립적이다.
• 메모리에서는 스택(stack) 영역에 저장되는 경우가 많다. 스택은 컴파일 시간에 크기가 결정되는 변수들을 저장하며, 메모리 할당 및 해제가 빠르다.

Class (Reference Type):

• class는 참조 타입(reference type)이다.
• 참조 타입은 변수에 할당되거나 함수에 전달될 때 실제 데이터가 아닌 메모리 주소(즉, 참조)가 전달된다.
• 이러한 방식은 여러 변수가 메모리상의 동일한 데이터 인스턴스를 공유할 수 있게 한다.
• 클래스 인스턴스는 힙(heap) 영역에 저장된다. 힙은 런타임에 크기가 결정되는 변수들을 저장하며, 스택에 비해 메모리 관리가 더 복잡하고 느릴 수 있다.

2. 메모리 관리: Stack vs Heap

Struct의 메모리 관리

• 구조체 인스턴스는 스택에 할당되어 빠르고 자동으로 메모리가 관리된다.
• 스택은 LIFO(Last In, First Out) 방식으로 작동한다.
  • 변수가 범위(scope)를 벗어나면 자동으로 메모리에서 제거된다.
  • 스택 기반 메모리 할당은 작은 데이터 구조에 적합하다.

Class의 메모리 관리

• 클래스 인스턴스는 힙에 저장되어 더 유연하지만, 복잡하고 비용이 많이 드는 메모리 관리가 필요하다.
• Swift에서는 ARC(Automatic Reference Counting)를 사용하여 클래스 인스턴스의 메모리를 관리한다.
  • 객체에 대한 참조가 더 이상 없을 때 시스템이 자동으로 메모리를 해제하는 방식

3. 성능 측면

Struct:

• 값 타입의 복사는 대체로 간단한 데이터에 대해서는 매우 빠르지만, 크기가 큰 구조체의 경우 비용이 많이 들 수 있다.
• 따라서 작은 데이터 구조에 적합하다.

Class:

• 참조 타입은 메모리 주소만 전달되므로, 일반적으로 크기에 관계없이 복사 비용이 적다.
• 그러나 참조 카운팅으로 인한 오버헤드가 있으며, 힙 할당/해제로 인해 성능 저하가 발생할 수 있다.

4. 크기 결정: Compile-time vs Runtime

Struct (Compile-time):

• struct는 컴파일 시간에 크기가 결정된다.
• 이는 struct가 값 타입이며, 그 값이 복사될 때 전체 내용이 메모리에 복사되기 때문이다.
• 컴파일 시간에 struct의 크기를 결정하면, 스택 메모리에 효율적으로 할당하고 관리할 수 있다.

Class (Runtime):

• class는 런타임에 크기가 결정된다.
• 클래스 인스턴스는 힙에 저장되며, 인스턴스의 크기는 런타임에 객체가 생성될 때 결정된다.
• 이는 클래스 인스턴스의 크기가 동적으로 변할 수 있고, 상속, 다형성 등으로 인해 컴파일 시점에서 정확한 크기를 결정하기 어렵기 때문이다.

5. 메모리 {할당 ~ 접근 ~ 해제} 과정

Struct (Value Type) - 스택 할당

1. 메모리 할당:
   • 구조체(Struct) 인스턴스가 생성될 때, 그 크기와 구조는 이미 컴파일 시점에 결정된다.
   • 실행 시점에 해당 구조체 변수가 범위(scope)에 들어오면, 스택 메모리에 공간이 할당된다.
   • 스택 메모리는 함수 호출과 함께 관리되며, 각 함수 호출에 대한 로컬 변수들이 순차적으로 스택에 쌓인다.
2. 메모리 접근:
   • 스택에 저장된 변수는 빠르게 접근 가능하다.
   • 스택은 LIFO(Last In, First Out) 구조를 가지기 때문에 최근에 할당된 변수가 가장 먼저 접근된다.
3. 메모리 해제:
   • 변수의 범위(scope)를 벗어나면, 해당 변수에 할당된 메모리는 자동으로 해제된다.
   • 예를 들어, 함수가 종료되면 그 함수의 로컬 변수들이 스택에서 제거된다.
   • 이 과정은 빠르고 효율적이며, 개발자가 직접 관리할 필요가 없다.

Class (Reference Type) - 힙 할당

1. 메모리 할당:
   • 클래스(Class) 인스턴스가 생성될 때, 그 크기가 런타임에 결정되고 힙에 메모리가 할당된다.
   • 힙은 동적 메모리 할당을 위한 공간으로, 실행 시간에 크기가 결정되는 데이터를 저장한다.
   • 클래스 인스턴스에 대한 참조(주소)는 스택이나 다른 클래스의 일부로 저장될 수 있지만, 실제 데이터는 힙에 위치한다.
2. 메모리 접근:
   • 힙에 저장된 객체는 주소를 통해 접근된다.
   • 이 주소는 변수가 스택에 저장되거나 다른 객체에 포함될 수 있다.
   • 힙 메모리 접근은 스택에 비해 상대적으로 느릴 수 있다.
3. 메모리 해제:
   • Swift에서는 ARC(Automatic Reference Counting)를 사용하여 클래스 인스턴스의 메모리를 관리한다.
   • 인스턴스에 대한 모든 참조가 사라지면, 즉 참조 카운트가 0이 되면 ARC는 자동으로 해당 인스턴스의 메모리를 해제한다.
   • 메모리 누수를 방지하기 위해 강한 순환 참조(strong reference cycles)를 피하는 것이 중요하다.
   • 힙에서의 메모리 할당과 해제는 스택에 비해 비용이 많이 들고 복잡할 수 있다.

6. ARC(Automatic Reference Counting)에 대한 추가 설명과 예시

class Person {
    let name: String

    init(name: String) {
        self.name = name
        print("\(name) is being initialized")
    }

    deinit {
        print("\(name) is being deinitialized")
    }
}

var reference1: Person?
var reference2: Person?
var reference3: Person?

reference1 = Person(name: "John") // "John is being initialized"
// 여기서 John에 대한 참조 카운트는 1.

reference2 = reference1 // John에 대한 참조 카운트가 2가 된다.
reference3 = reference1 // John에 대한 참조 카운트가 3이 다.

reference1 = nil // John에 대한 참조 카운트가 2로 감소한다.
reference2 = nil // John에 대한 참조 카운트가 1로 감소한다.
reference3 = nil // "John is being deinitialized"
// 모든 참조가 제거되었으므로 John에 대한 인스턴스가 메모리에서 해제된다.

ARC는 강한 순환 참조(strong reference cycles)를 방지하기 위해,

강한(strong), 약한(weak) 또는 미소유(unowned) 참조에 대한 개념을 이해하는 것이 중요하다.

이러한 메커니즘을 통해 메모리 누수를 방지할 수 있다.

7. ARC의 참조 유형

1. Strong 참조

class Person {
    let name: String
    init(name: String) { self.name = name }
}

var person1: Person? = Person(name: "Alice")
var person2 = person1 // Strong 참조
// 이 시점에서 'Alice'에 대한 참조 카운트는 2이다.

• 기본 참조 방식:
  • Swift에서는 변수가 클래스의 인스턴스를 참조할 때 기본적으로 strong 참조를 사용한다.
  • 이는 참조하는 인스턴스가 메모리에 유지되어야 함을 의미.
• 작동 원리:
  • strong 참조가 있는 동안, ARC는 해당 인스턴스를 메모리에서 해제하지 않는다.
  • 인스턴스에 대한 strong 참조가 하나라도 있으면, 해당 인스턴스는 메모리에 유지된다.
• 메모리 누수 위험:
  • strong 참조는 순환 참조(두 객체가 서로를 strong으로 참조)를 생성할 수 있으며, 이는 메모리 누수로 이어질 수 있다.

2. Weak 참조

class Apartment {
    let unit: String
    weak var tenant: Person?

    init(unit: String) { self.unit = unit }
}

var john: Person? = Person(name: "John")
var unit4A: Apartment? = Apartment(unit: "4A")
unit4A?.tenant = john
// 'John'에 대한 참조는 weak이므로 참조 카운트는 증가하지 않는다.

// 여기서 Apartment 클래스의 tenant 속성은 weak 참조이다. 
// john이 unit4A.tenant에 할당되어도, 'John' 인스턴스의 참조 카운트는 증가하지 않는다.
// unit4A.tenant에 <- john을 할당 == unit4A.tenant가 -> john을 참조함

• 옵셔널 참조:
  • weak 참조는 옵셔널 형태로 선언된다.
  • 즉, 참조된 인스턴스가 메모리에서 해제될 수 있으며, 그 경우 참조는 자동으로 nil이 된다.
• 주 사용 시나리오:
  • 순환 참조를 피하기 위해, 두 객체 간의 관계에서 한 쪽이 다른 쪽보다 "덜 중요할" 때 사용된다.
  • 예를 들어, delegate 패턴에서는 delegate를 weak으로 선언하는 것이 일반적이다.
• 참조 카운트 영향:
  • weak 참조는 참조 카운트를 증가시키지 않는다.
  • 따라서, weak 참조만이 남아있는 객체는 ARC에 의해 메모리에서 해제될 수 있다.

3. Unowned 참조

class CreditCard {
    let number: UInt64
    unowned let customer: Person

    init(number: UInt64, customer: Person) {
        self.number = number
        self.customer = customer
    }
}

var bob: Person? = Person(name: "Bob")
var card: CreditCard? = CreditCard(number: 1234567890123456, customer: bob!)
// 'bob' 인스턴스는 CreditCard에 의해 unowned 참조된다.

// 이 경우 CreditCard 클래스는 customer 속성을 unowned로 참조한다. 
// 'bob' 인스턴스는 CreditCard가 존재하는 한 메모리에 유지되지만, CreditCard 인스턴스는 'bob'이 메모리에서 해제되더라도 그 상태를 변경하지 않는다. 
// 'bob'이 메모리에서 해제된 후에 card의 customer에 접근하려고 하면 런타임 오류가 발생할 수 있다.

• Non-Optional 참조:
  • unowned 참조는 non-optional 타입.
  • 참조된 인스턴스가 항상 존재한다고 가정한다.
  • unowned 참조는 참조된 인스턴스가 해제된 후에도 nil로 바뀌지 않는다.
• 사용 상황:
  • unowned 참조는 두 객체가 서로에 대해 동등한 생명주기를 가지고 있거나,
    참조하는 객체가 참조된 객체보다 더 긴 생명주기를 가질 때 사용된다.
  • 순환 참조를 피하는 데 사용될 수 있으나, 참조된 객체가 해제된 후에는 사용할 수 없다.
• 위험성:
  • unowned 참조를 사용할 때는 주의가 필요하다.
  • 참조된 객체가 해제된 후에 unowned 참조를 접근하면 런타임 오류가 발생할 수 있다.

+ 24.02.04

컬렉션 타입(Array, Dictionary, Set)의 조금은 다른 점

대량의 데이터를 관리하는 경우, 값 타입은 매번 전체 값을 메모리에 저장해야 하는 문제가 있다. 느려진다.

특히 이런 문제를 마주할 가능성이 높은 컬렉션 타입은 값 타입이지만, 내부적으로 참조 타입을 사용한다.

즉, 메모리 관리를 위해 Stack과 Heap을 모두 사용한다.

1. 메모리 할당

• 스택에서의 할당
  • 컬렉션 타입의 인스턴스가 생성될 때, 인스턴스의 메타 데이터는 스택에 할당된다.
  • 메타 데이터에는 컬렉션의 크기, 용량 등의 정보가 포함된다.
  • 기존 규칙에 따라, 스코프를 기준으로 즉시 할당된다.
• 힙에서의 할당
  • 실제 데이터(예: 배열의 요소)는 힙에 할당된 참조 타입을 통해 관리된다.
  • 즉, 컬렉션에 데이터가 추가, 수정, 삭제되는 경우 힙에 할당된다.
  • ARC를 통해서도 관리된다.

2. 데이터 수정

• Copy-On-Write(COW)
  • 컬렉션의 복사본이 수정되려 할 때, Swift는 해당 컬렉션이 다른 인스턴스와 내부 데이터를 공유하고 있는지 확인한다.
  • 공유되고 있다면, 수정 작업 수행 전에, 내부 데이터의 실제 복사본을 생성한다. (힙에 새로운 데이터 할당)
  • 불필요한 데이터 복사를 방지한다.
  • 이때, ARC로 새로운 할당을 추적한다.
  • Class의 그것과 같다.

3. 메모리 해제

• 스택에서의 해제
  • 컬렉션 타입의 인스턴스가 스코프를 벗어나면, 스택에 저장된 메타 데이터는 자동으로 해제된다.
  • 빠르다. ARC 필요없다.
• 힙에서의 해제
  • 컬렉션 타입의 인스턴스에 연결된, 실제 데이터는 ARC에 의해 관리된다.
  • 인스턴스에 대한 모든 참조가 사라지면(RC == 0), ARC는 힙에서 해당 데이터를 해제한다.

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
}