백준 31458번 문제 풀이

문제

https://www.acmicpc.net/problem/31458

제출 코드

_ = readLine()
while let input = readLine() {
    let numberIndex = input.firstIndex(where: { $0.isNumber })!
    var number = Int(String(input[numberIndex]))!
    let factorialCount = input.distance(from: numberIndex, to: input.endIndex) - 1
    let logicalNotCount = input.distance(from: input.startIndex, to: numberIndex)
    if factorialCount > 0 {
        number = 1
    }
    print(logicalNotCount % 2 == 0 ? number : (number == 0 ? 1 : 0))
}

⏱️ 시간복잡도

• `firstIndex(where:)`
  • 문자열 처음부터 순회하며 조건에 만족하는 첫번째 문자를 찾기 때문에 O(L), L은 문자열 길이
• `distance(from:to:)`
  • 두 인덱스 사이의 거리를 계산하기 위해 문자열 내부 순회하고, factorialCount와 logicalNotCount 계산을 위해 총 두번 호출되었기 때문에 최악의 경우 각각 O(L), L은 문자열 길이
  • 두 인덱스 사이의 거리를 계산할 때 문자열 내부를 순회한다는 것은, Swift의 문자열은 각 문자의 메모리 크기가 일정하지 않아 두 인덱스 사이의 정확한 거리를 알기 위해서는 사이에 존재하는 모든 문자를 순회하면서 길이를 계산해야 한다는 뜻입니다!
• 결론 : input 한 줄 당 시간복잡도는 O(L)

📦 공간복잡도

• 입력 저장 공간
  • readLine()을 저장하는 input은 입력 저장공간으로 간주하고, 알고리즘이 추가적으로 사용하는 메모리만이 공간복잡도에 포함된다는 가정하에 계산합니다.
• 추가 변수 사용
  • 추가적으로 사용하는 메모리는 numberIndex, number, factorialCount, logicalNotCount 모두 상수 변수로 공간복잡도는 O(1)
• 결론 : input 한 줄 당 공간복잡도는 O(1)

회고

• String.Index를 통해 문자열 내 문자 접근 방식을 익히니까 알고리즘 문제를 풀 때 코드 표현력이 훨씬 향상됨!
• String.Index 간의 거리를 비교할 때 동작은 머릿속에 있지만 String 내장함수인 distance(from:to:)를 사용하는 것을 몰라서 결국 구글링을 통해 캐치함😅
• 숫자의 조건이 0 or 1이었기에 팩토리얼 연산에 대한 계산식이 필요없어서 문제를 처음 봤을 때의 체감난이도와 풀이중의 체감난이도 차이가 있었음