Optional Type

옵셔널 타입이란 값이 있을 수도 있고, 없을 수도 있는 타입을 말한다.

Swift에서는 값이 없음을 표시하기 위해 nil을 사용한다.

참조가 없음을 의미하는 다른 언어의 nil과는 사뭇 다르다.

var message: String = "My String"
message = nil // Error

Swift의 타입은 기본적으로 Non-Optional 타입이다. 즉, 반드시 값이 있어야 한다.

이러한 타입에 nil을 할당하면 컴파일 에러가 발생한다.

var myString1: String?
var myString2: Optional<String>

이것이 옵셔널 타입을 선언하는 방식이다.

위 두 변수는 이름만 다르고 같은 변수이다.

옵셔널 타입의 변수의 초깃값은 기본적으로 nil로 설정된다.

enum Optional<T> {
    case None
    case Some(T)
}

옵셔널 타입은 내부적으로 Enumertaion으로 정의한다.

우리가 어떤 변수를 옵셔널 타입을 선언할 때,

해당 변수에 nil을 할당했다면, None 값을 갖는 것이다.

해당 변수에 특정 값을 할당했다면, <T>에 대응하는 associated value를 갖게 되는 것이다.

Optional Type의 필요성

옵셔널은 런타임 오류를 방지하는 데에 그 목적이 있다.

옵셔널을 사용하면 컴파일 단계에서 변수 초기화 문제를 발견할 수 있다.

int i;
MyObject *m;

-(int)myMethodWithValue:(int)i {
    return i*2;
}

NSLog(@"Value: %d",[m myMethodWithValue:5]);

Objective-C에 이런 코드가 있다.

i와 m을 선언하고, 초기화는 하지 않는다고 가정하자.

이 코드를 실행하면 의도한 10(5 * 2)의 값이 아니라, 0의 값을 얻게 된다.

왜 why?

옵젝씨에서는 값을 초기화하지 않은 정수형 변수를 0으로 초기화하나 보다.

중요한 것은 에러조차 없이 이상하게 동작한다는 것이다.

이런 문제는 찾아내기 굉장히 어렵다.

var myString: String
print(myString) // ERROR: Variable 'myString' used before being initialized

같은 상황에서 Swift는 컴파일 에러를 띄워준다.

값이 필요하면 반드시 초기화를 하고,

값이 없을 수도 있는 경우에는 무조건 Optional 변수를 사용하라는 뜻이다. 참 따뜻하다.

Optional Unwrapping

옵셔널 타입의 변수를 사용하기 전에는 반드시 값이 있는지 없는지 검증해야 한다.

nil이 할당되어 있는 변수를 사용하려다가는 런타임 에러가 발생하면서 앱이 깨지고 만다. 와장창.

옵셔널 변수의 값을 얻어내는 것을 Optional Unwrapping이라고 한다.

두 가지 방법을 제시한다.

Forced unwrapping

// #1
var myString1: String?
myString1 = "test"
var test: String = myString1!
print(myString1) // test

// #2
var myString1: String?
myString1 = nil
var test: String = myString1! // Thread 1: Fatal error: Unexpectedly found nil while unwrapping an Optional value
print(test)

옵셔널 변수의 끝에 느낌표(!)를 붙이면, 안에 있는 값을 강제로 얻을 수 있다.

프로그래밍에서 강제란... 보통은 하면 안 되는 것이다.

Swift에서도 같다.

웬만한 경우에는 Force unwrapping을 사용하지 않을 것을 권장한다.

#1번의 경우에는 정상적으로 unwrapping이 된다.

#2번의 경우에는 컴파일러가 myString1에는 값이 있을 것이라고 굳게 믿고 코드를 실행한다.

아뿔싸. 값이 없다. 런타임 에러를 만나고 앱이 깨진다.

Optional Binding

// #1
if let constantName = optionalVariable {
    statements
}

// #2
if var variableName = optional {
    statements
}

보다 평화롭고 권장되는 방법이다.

등호를 기준으로 오른쪽에 있는 옵셔널 변수의 값을 확인한다.

nil이 아닌 값이라면, constantName 변수에 할당한다.

if statement 범위에서 constantName 변수를 자유롭게 사용할 수 있다.

세간의 인식과는 다르게 `if let` 뿐만 아니라 `if var`도 가능하다.

var myString3: String?
myString3 = "Space, the final frontier"

if let tempVar = myString3 {
    print(tempVar) // "Space, the final frontier"
} else {
    print("No value")
}

print(tempVar) // Compile Error: Cannot find 'tempVar' in scope

실전 예시를 보면 이렇다.

함수 내부에서 tempVar는 잘 사용할 수 있다.

함수를 벗어나서 사용하려고 하면, 컴파일 에러가 발생한다. 당연하다.

if let tmp1 = optional1, let tmp2 = optional2, let tmp3 = optional3 {
    print(tmp1)
    print(tmp2)
    ...
}

위와 같이 하나의 optional binding line에 여러 개의 옵셔널 변수를 unwrapping하는 것도 가능하다.

이때 하나의 변수라도 nil이면, 모든 unwrapping에 실패한다.

if let myOptional = myOptional {
    print(myOptional)
} else {
    print("myOptional was nil")
}

같은 이름의 변수에 unwrapping 결과물을 할당하는 것도 가능하다.

변수 이름 작명에 고심하는 개발자를 배려하는 따뜻한 조처이다.

Optional types with tuples

var tuple1: (one: String, two: Int)?
var tuple2: (one: String, two: Int?)

튜플을 통째로 옵셔널로 만들 수 있다.

튜플의 원소 하나만을 옵셔널로 만들 수도 있다.

Optional Chaining

var tireSize = car?.tires?.tireSize

프로퍼티, 메서드, subscript를 호출할 때, 그것의 return 값이 optional인 경우 위와 같이 사용할 수 있다.

chaining된 값 중에서 하나라도 nil이면, 전체 변수가 nil이 된다.

모든 값이 nil이 아니라면, 전체 변수는 optional unwrapping된 값을 얻는다.

  optionalA ?? defaultValue

병합 연산자라고들 하는 것 같다. 발음은 코얼레싱에 가깝다.

삼항 연산자(tenary operator)와 유사한 방식으로 동작한다.

좌항의 값이 nil이라면 defaultValue가 할당된다.

nil이 아니라면 optional unwrapping된 값이 할당된다.

varr defaultName = "Jon"
var optionalA: String?
var optionalB: String?
optionalB = "Buddy"

var nameA = optionalA ?? defaultName // "Jon"
var nameB = optionalB ?? defaultName // "Buddy"

어렵지 않다.

optionalA는 nil이니까 defaultName.

optionalB는 nil이 아니니까 "Buddy"

var nameC1 = optionalA ?? defaultName
var nameC2 = optionalA != nil ? optionalA! : defaultName

위 두 문장은 같은 코드이다.

coalescing operator를 적극 활용하자.

참고

<Mastering Swift 5.3>, Jon Hoffman, 6th Edition

Chapter 3: Learning about Variables, Constants, Strings, and Operators

8. Leader lesson - Learn to Code - Codility

문제 분석

 배열을 쪼개, 두 배열 모두 같은 leader를 갖게 하는 index를 모두 return

의사 코드

 leftCount = 0, rightCount = 배열의 길이, leftLeaderCount = 0, rightLeaderCount = 0
 1 .leader 구함
 2. 배열 탐색하면 leader를 만나면
     leftLeaderCount += 1
     rightLeaderCount -= 1
leftSize += 1
rightSize -= 1
leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2일 때, answer += 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    // leader 구한다.
    let sortedA = A.sorted()
    let candidate = sortedA[A.count / 2]
    var cnt = 0
    for elem in A {
        if candidate == elem {
            cnt += 1
        }
    }
    let leader = cnt > A.count / 2 ? candidate : -1 

    var leftSize = 0
    var leftLeaderCount = 0
    var rightSize = A.count
    var rightLeaderCount = cnt
    var answer = 0

    for elem in A {
        if elem == leader {
            leftLeaderCount += 1
            rightLeaderCount -= 1
        }

        leftSize += 1
        rightSize -= 1

        if leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2 {
            answer += 1
        }
    }

    return answer
}

Dominator coding task - Learn to Code - Codility

의사 코드

 1. leader 후보 찾기
     배열을 탐색하며, size == 0이라며면,
         해당 값을 value에 할당한다. size += 1
     size == 0이 아니라면,
         새로운 값이라면, size -= 1
         새로운 값이 아니라면, size += 1
    
     2. 후보 개수 세기
     candidate = -1
     if size > 0이라면,
         candidate = value
     배열에서 candidate와 같은 값의 index를 저장한다.
     return candidate의 개수 > 배열의 크기 / 2 이면 ? index 배열 : - 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var size = 0
    var value = 0

    for elem in A {
        if size == 0 {
            value = elem
            size += 1
        } else {
            if value != elem {
                size -= 1
            } else {
                size += 1
            }
        }
    }

    var candidate = -1
    var count = 0
    var idxArray = -1
    if size > 0 {
        candidate = value
    }

    for i in 0..<A.count {
        if A[i] == candidate {
            count += 1
            idxArray = i
        }
    }

    return count > (A.count / 2) ? idxArray : -1
}

StoneWall coding task - Learn to Code - Codility

문제 분석 (틀림)

문제 분석
막대 그래프를, 직사각형으로만 구성하기 위해 필요한 최소 개수는?
막대의 높이가 최대 10억이므로, 일반적인 탐색 문제는 아닌 듯하다.
왼쪽부터 현재 원소의 값(높이)를 기준으로, 연속으로 확장 가능한 너비를 측정한다.
현재 값보다 작은 값을 만나면 멈춘다. 직사각형을 1개를 구성한다.
    구성이 완료된 부분은, 각 원소에서 현재 값만큼 빼준다.
    직사각형 개수를 += 1
그런데 이렇게 하면, O(N^2)으로 시간 초과가 난다..

문제 분석 (구글링)

 스택에 저장된 높이와 현재 높이를 비교하면서 다음을 실행한다.
     1. 저장된 높이가 더 높은 경우: 현재 더 낮은 높이 블럭이 생길 것이므로, 이어지던 직사각형 생성 과정이 종료되었다. 이후 판단 과정에서 저장된 높이들이 필요 없어졌다. 현재보다 더 높은 블럭을 모두 스택에서 제거한다.
     2. 같은 경우: 아무 것도 하지 않는다. 블럭을 아끼는 것이다.
     3. 저장된 높이가 더 낮은 경우: 더 높은 새로운 블럭이 필요하다. 개수를 세고, 스택에 추가한다.

풀이 (구글링)

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var stack: [Int] = []
    var count = 0

    for element in H {
        while !stack.isEmpty && stack.last! > element {
            stack.removeLast()
        }

        if stack.isEmpty || stack.last! < element {
            count += 1
            stack.append(element)
        }
    }

    return count
}

회고

분명 Easy인데, 꽤나 어려운 문제였다.

인간의 직관과는 다른 컴퓨팅 사고가 필요한 문제에 여전히 고전한다.

이 문제는 3가지 케이스를 생각해내는 것이 핵심이다.

stack.top과 탐색 중인 element을 비교한다. 비교값은 3가지 케이스를 갖는다.

1. 같은 경우:
   1. 패스한다.
2. element가 더 작은 경우:
   1. stack의 더 높은 막대들은, element를 만들 수 없다.
   2. 동시에 1.의 케이스로 이어지던 직사각형의 생성 과정이 종료된다.
   3. 생성이 종료된 높은 막대들은 이후 판단 과정에 필요 없다. 모두 제거한다.
3. element가 더 큰 경우:
   1. 새로운 높은 막대가 필요하다.
   2. count를 증가시키고, stack에 element를 추가한다.

참고

https://rkdvnfma90.tistory.com/261

Nesting coding task - Learn to Code - Codility

의사 코드

 입력값이 "("인 경우:
     스택이 비어있으면 추가한다
     스택이 비어있지 않으면
         top이 ")"이면 return 0
         아니라면 추가한다.

 입력값이 ")"인 경우:
     스택이 비어있으면 return 0
     스택이 비어있지 않으면
         top이 "("이면 popLast()
         아니라면 return 0

 stack의 길이가 0이라면 return 1, 아니라면 return 0

풀이

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    var stack: [String] = []
    
    for currentB in S {
        if currentB == "(" {
            if stack.isEmpty {
                stack.append(String(currentB))
            } else {
                if stack.last! == ")" { return 0 }
                else { stack.append(String(currentB)) }
            }
        } else { // ")"
            if stack.isEmpty { 
                return 0
            } else {
                if stack.last! == "(" { _ = stack.popLast() }
                else { return 0 }
            }
        }
    }

    return stack.count == 0 ? 1 : 0
}

https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

문제 분석

 인접한 원소가 다른 방향을 갖고 있다면, 싸움이 붙는다.
 싸움: 큰 물고기가 작은 물고기를 먹어버린다.
 물고기는 한 방향으로 계속 이동한다.

의사 코드

 순방향으로 탐색
 while stack이 비어있지 않고, 현재 원소가 올라가고, stack에 있는 원소가 내려가고 있을 때 판단
     if stack.last!.0 < currentElement.0
         stack.popLast()
     else 
				 flag = true // 현재 원소가 잡아먹힘 -> 더 할 게 없음.
		     break
if flag == false // 현재 원소 잡아먹히지 않음 -> stack에 추가
	append

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int {
    var survivedStack: [(Int, Int)] = []

    for i in 0..<A.count {
        let currentElement = (A[i], B[i])
        var isEaten = false

        while !survivedStack.isEmpty && survivedStack.last!.1 == 1 && currentElement.1 == 0 {
            if survivedStack.last!.0 < currentElement.0 {
                _ = survivedStack.popLast()
            } else {
                isEaten = true
                break
            }
        }

        if !isEaten {
            survivedStack.append(currentElement)
        }
    }

    return survivedStack.count
}

Brackets coding task - Learn to Code - Codility

문제 분석 (오답)

문자열 S가 'properly nested' 문자열인지 판단하는 문제
 'properly nested'이란?
     1. "": 빈 문자열
     2. "(X)", "[X]", "{X}": 괄호로 둘러싸인 배열
     3. "XX": nested strings이 나열된 배열
 문자열 S는 (, ), [, ], {, } 으로만 구성된다.

 Stack으로 푸는 문제
 Stack을 구현하지 않아도 된다.

의사 코드 (오답)

3가지의 괄호를 담당하는 변수를 하나씩 선언한다.
 문자열을 탐색한다.
     열린 괄호를 만나면, 해당하는 변수에 += 1
     닫힌 괄호를 만다면, 해당하는 변수에 -= 1
     변수가 0 보다 작아지면, 즉시 return 0
 탐색이 종료되고, 3개의 변수가 모두 0이면 return 1 아니면 return 0

나의 풀이 (오답)

import Foundation
 import Glibc

 public func solution(_ S : inout String) -> Int {
     let size = S.count
     if size == 0 { return 1 }
     if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

     var bracket = 0
     var squareBracket = 0
     var curlyBracket = 0

     for i in 0..<size {
         let idx = S.index(S.startIndex, offsetBy: i)
         let currentBracket = S[idx]

         switch currentBracket {
             case "(":
                 bracket += 1
             case ")":
                 bracket -= 1
                 if bracket < 0 { return 0 }
             case "[":
                 squareBracket += 1
             case "]":
                 squareBracket -= 1
                 if squareBracket < 0 { return 0 }
             case "{":
                 curlyBracket += 1
             default: // "}"
                 curlyBracket -= 1
                 if curlyBracket < 0 { return 0 }
         }
     }

     return bracket == 0 && squareBracket == 0 && curlyBracket == 0 ? 1 : 0
 }

문제 분석 2 (오답)

Stack으로 구현해야 한다 ..
카운트만 해서는 다음과 같은 테스트 케이스를 통과할 수 없다. "([)()]"

의사 코드 2 (오답)

문자열을 담을 스택을 선언한다. var bracketStack = [String]()
 열린 괄호가 들어오면, 스택에 push() 한다.
 닫힌 괄호가 들어오면, 스택에서 pop() 한 값과 짝을 이루는지 검증한다.
     짝이 아니면 즉시 return 0
     짝이 맞으면 그대로 pop()
 탐색이 끝났을 때, 배열이 비어있으면 1 아니면 0

나의 풀이 2 (오답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

    var bracketStack = [String]()

    for i in 0..<size {
        let idx = S.index(S.startIndex, offsetBy: i) // 여기가 문제
        let currentBracket = String(S[idx])

        switch currentBracket {
            case ")":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "(" { return 0 }
            case "]":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "[" { return 0 }
            case "}":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "{" { return 0 }
            default:
                bracketStack.append(currentBracket)
        }
    }

    return bracketStack.count == 0 ? 1 : 0
}

// 시간 복잡도가 무려 O(3 ** N)...
// String의 subscript는 O(N)이다. RandomAccessCollection이 아니므로.
// 그렇다 하더라도 O(N ** 2) 아닌가? 찾아봤지만 답을 얻기 어렵다.

수정된 풀이 (정답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

    var bracketStack = [String]()

    for currentBracket in S {
				let currentBracket = String(currentBracket) // 이 부분 개선

        switch currentBracket {
            case ")":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "(" { return 0 }
            case "]":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "[" { return 0 }
            case "}":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "{" { return 0 }
            default:
                bracketStack.append(currentBracket)
        }
    }

    return bracketStack.count == 0 ? 1 : 0
}

// O(N)
// removerLast() -> Element
// popLast() -> Element?

더 나은 풀이 (정답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 }

    let bracketMap = [")": "(", "]" : "[", "}" : "{"]
    var bracketStack = [String]()

    for bracket in S {
        if let matchingBracket = bracketMap[String(bracket)] {
            if bracketStack.isEmpty || matchingBracket != bracketStack.last {
                return 0
            }
            bracketStack.removeLast()
        } else {
            bracketStack.append(String(bracket))
        }
    }

    return bracketStack.isEmpty ? 1 : 0
}

// 딕셔너리와 함께 하면 쉽다.
// switch를 활용하지 않아도 된다.

회고

가장 기본적인 문제인데 꽤 고생했다.

Swift의 문자열 인덱싱은 쉬이 익숙해지지 않는다.

Swift에서 subscript(_ :)는 기본적으로 O(1)을 보장하지만, String은 다르다.

String은 Character의 Collection이다.

C++, Java의 char는 고정된 크기를 갖지만, Swift의 Character는 1개 이상의 Unicode Scalar로 이루어져 있다. 크기가 가변적이다.

따라서 String은 RandomAccessCollection 프로토콜을 따르지 않는다. (BidirectionalCollection 채택)

따라서 순차 접근해야 한다.

그렇기에, index(_ : offsetBy:)로 접근해야 하고, O(N)의 시간복잡도를 갖는다.

길이를 구하는 .count 연산도 String은 O(N). RandomAccessCollection은 O(1).

String의 원소에 대한 임의 접근이 반드시 필요하다면?

String을 Character의 Array로 바꾸고 작업을 한 뒤, 마지막에 String으로 바꾸는 것이 좋다.

String.index를 순회하는 것보다, Character의 Array가 훨씬 효율적이다.

let str = "Hello, World!"
let arr = Array(str)

print(arr) 
// ["H", "e", "l", "l", "o", ",", " ", "W", "o", "r", "l", "d", "!"]

참고

https://jcsoohwancho.github.io/2019-11-19-Swift-String-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9C%BC%EB%A1%9C-%EC%93%B0%EA%B8%B0/

https://stackoverflow.com/questions/38800662/big-o-of-accessing-a-string-with-an-index-in-swift-3-0

NumberOfDiscIntersections coding task - Learn to Code - Codility

문제 분석

겹치는 원의 개수를 구한다
 겹치기만 하면 되니까, x축만 고려하자
 겹친다의 정의: i번째 원의 max 값 >= i+1번째 원의 min 값
 O(N^2)하면 쉽게 풀리지만, N = 100,000이므로 불가능

구글링

 시작점과 끝점의 배열을 각각 구한다
 각각 오름차순으로 정렬한다
 시작점 배열을 기준으로 탐색하며, 활성화된 원의 개수를 하나씩 추가한다
     다음 순서 원을 탐색할 때,
     현재 원의 시작점 < 이전까지 가장 큰 원의 끝점인지 확인한다.
         아니라면 조건을 성립할 때까지 탐색하며 활성화된 원을 제거한다.
     기존 활성화된 원의 개수를 정답에 더한다.
     정답이 조건을 넘어서면 -1을 반환한다.

참고한 풀이

import Foundation
import Glibc

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

    for i in 0..<size {
        starts.append(i - A[i])
        ends.append(i + A[i])
    }

    starts.sort()
    ends.sort()

    var intersections = 0
    var activeDiscs = 0
    var endIdx = 0

    for start in starts {
        while endIdx < size && ends[endIdx] < start { // 겹치지 않는 상황
            activeDiscs -= 1
            endIdx += 1
        }
        intersections += activeDiscs // 지금까지 활성화된 디스크 수를 더하고
        activeDiscs += 1 // 디스크 수 + 1

        if intersections > 10_000_000 {
            return -1
        }
    }

    return intersections
}

회고

꽤 어려웠다. 코딜리티 문제는 난도가 들쭉날쭉하다.

시작점과 끝점 만을 고려한다는 것에는 접근을 했다.

그러나 정렬을 해도 된다는 생각을 하지 못 했다.

순서쌍을 구하는 것이 아니라, 카운트만 하면 되니까 정렬을 해서 따져도 문제가 없다.

점화식 만드는 훈련을 지속하자.

참고

https://study-ihl.tistory.com/175