Single Responsibility 객체는 하나의 기능만 수행해야 한다.

• View 는 UI 관련 설정만, 네트워크 매니저는 HTTP 요청/응답만 관여해야 한다.

Open-Closed 소프트웨어 엔티티는 확장에 열려있고 변경에 닫혀있어야 한다.

• <예시> 데이터 타입이 계속 추가되는 경우 추상 클래스를 작성하면 좋다.

Liskov substitution

프로그램의 정상 동작을 유지하면서 클래스 S 를 따르는 객체를 클래스 S 의 서브클래스 T 를 따르는 객체로 치환할 수 있어야 한다.

• 서브클래싱을 했을 때 상위 클래스의 동작과 엇나가면 안된다.

Interface segregation

사용하지 않는 UI 기능을 구현하지 않도록 주의하라

• <예시> UI 관련 프로토콜에 구현이 필요 없는 메소드가 포함되는 경우 프로토콜을 분리하는 것이 좋다.

Dependency inversion

추상화한 것이 디테일에 의존하지 않도록 작성해야 한다.

• 이것도 프로토콜 프로그래밍을 사용해야 하는 이유 중 하나이다.

ref: https://www.raywenderlich.com/21503974-solid-principles-for-ios-apps ref: https://medium.com/@nishant.kumbhare4/solid-principles-in-swift-73b505d3c63f

TableView 가 스크롤을 했을 때, 추가적인 동작을 위해 Delegate 에게 메시지를 전달하는 것이 그 예시이다.

TableView 가 행을 선택하기 전, Delegate 에게 선택이 가능한지 물어볼 수도 있다.

Delegate 는 프로토콜 기반으로 동작하는데, 이는 클래스 간의 디펜던시를 최소화 할 수 있고, 프로토콜을 선언하는 입장에서 꼭 구현해야 하는 / 구현하지 않아도 되는 메소드를 분리할 수 있다.

ref: https://useyourloaf.com/blog/delegation-or-notification/

Notification 은 메시지를 브로드캐스팅한다. 앞의 예시에서 Delegate 는 sender 와 상호작용이 가능하다고 했는데, Notification 의 receiver 는 sender 에게 어떤 동작을 하도록 작용할 수 없다.

NotificationCenter 가 방송국 역할을 한다고 할 수 있다. (addObserver 로 옵저버 등록, post 로 메시지 전송)

The concept of Delegate and Notification is devised in order to reduce couplings and dependencies (most of them are unnecessary.) between classes in application.

Delegate is, literally assigned to be delegated any actions to be done whenever sender sends certain messages.

For example, when scrolling table view, send a message to delegate to handle further actions.

Or before selecting a row, sender can ask its delegate whether to be allowed or not.

Delegate pattern is protocol based, it minimizes dependencies between classes, and separator must/optionally implemented methods easily.

In the meantime, Notification does broadcast messages. As in the previous example, Delegate can interact with its sender. But the receiver of Notification cannot force its sender to perform any action.

NotificationCenter plays a role as broadcast center, as receivers can add observers and senders post messages via NotificationCenter.

IP 주소가 주어지면, 이를 정수로 만든 다음 연속한 n개의 정수만을 커버하는 CIDR 의 최소 길이 배열을 찾으면 된다.

CIDR 이란, IP 주소 뒤에 비트 인덱스가 있어 이 비트 이후로는 어떤 숫자든 올 수 있기 때문에 여러 개의 IP 주소를 커버할 수 있다.

편의를 위해 아래 메소드를 생성했다.

func ipToNum(_ ip: String) -> Int {
    ip.split(separator: ".").compactMap { Int($0) }.reduce(into: 0) { r, c in
        r = r * 256 + c
    }
}

func bit(_ x: Int) -> Int {
    x & -x
}

func log(_ x: Int) -> Int {
    Int(log2(Double(x)))
}

func CIDR(_ num: Int, _ k: Int) -> String {
    [num/(256*256*256) % 256,
     num/(256*256) % 256
     num/256 % 256,
     um%256].map { "\($0)" }.joined(separator: ".") + "/\(k)"
}

ipToNum : ip 주소를 정수로 변환 bit : least significant bit 의 크기 log : Log2 값 CIDR : 정수와 비트 인덱스에 해당하는 CIDR 문자열로 변환

풀이는 그리디 알고리즘을 사용하면 된다. LSB 만큼 더했을 때 n 이 남아있는 경우 CIDR 에 해당한다.

func ipToCIDR(_ ip: String, _ n: Int) -> [String] {
    var num = ipToNum(ip), n = n, res = [String]()

    while n > 0 {
        var b = bit(num) > 0 ? bit(num) : Int(pow(2.0, Double(log(n))))
        while b > n {
            b = b / 2
        }
        res.append(CIDR(num, 32 - log(b)))
        num += b
        n -= b
    }

    return res
}

0.0.0.0 이 주어진 경우 bit(0) = 0 이기 때문에 무한 루프를 돌게 되고, 이를 위해 Int(log2(num)) 만큼 강제 전진 해주는 과정이 필요하다.

worker - bike 쌍을 만들면서 맨하탄 거리 합의 최소를 찾아야 한다.

n, m < 10 인 제한이라 그냥 노가다로 때려 박았다.

var dic = [String: Int]()

func key(_ w: [[Int]], _ b: [[Int]]) -> String {
    w.description + b.description
}

func d(_ w: [Int], _ b: [Int]) -> Int {
    abs(w[0] - b[0]) + abs(w[1] - b[1])
}

func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
    if bikes.isEmpty || workers.isEmpty {
        return 0
    }

    if let v = dic[key(workers, bikes)] {
        return v
    }

    let n = workers.count
    let m = bikes.count
    let res = (0..<m).map { i -> Int in
        let w = Array(workers[1..<n])
        let b = Array(bikes[0..<i]) + Array(bikes[(i+1)..<m])
        return assignBikes(w, b) + d(workers[0], bikes[i])
    }.min()!

    dic[key(workers, bikes)] = res

    return res
}

dp 문제로 Memoization 을 사용했다.

이거 예전에 풀어본 적 있는 문제인데...

길이 n 인 String 이 도합 k 의 value 를 가지면서 사전순으로 가장 앞에 나와야 한다.

그리디 하게 풀고 뒤집으면 된다.

func getSmallestString(_ n: Int, _ k: Int) -> String {
    var res = [Character]()
    var k = k

    for i in 0..<n {
        var r = k - (n - 1 - i) // 이거 가지고 만들어야 된다.
        if r > 26 {
            res += ["z"]
            k -= 26
        } else {
            res += [Character(UnicodeScalar(97 + r - 1)!)]
            k -= r
        }
    }

    return String(Array(res.reversed()))
}

906. Super Palindromes

[left, right] 사이에 N 과 N*N 이 모두 팰린드롬인 수의 갯수를 구하는 문제인 듯 하다.

right < 1e18 이므로 가능한 N < 1e9 이다.

1e9 개의 팰린드롬을 미리 만들어 놓고 제곱수도 팰린드롬인지 확인하기로 한다.

자릿수가 n 이하인 팰린드롬 만드는 시간 복잡도는 양쪽에 숫자를 갖다 붙이는 방법으로 하면 O(10^(n/2)) 이다.

이 때 만들어진 팰린드롬 개수도 동일하고, 자릿수가 n 이하인 숫자가 팰린드롬인지 확인하는 시간 복잡도는 O(n) 이므로 시간은 충분하다.

func superpalindromesInRange(_ left: String, _ right: String) -> Int {
    var p = (1...9).map { "\($0)" }
    var res = 0

    for i in 1..<Int(1e4) {
        let s = "\(i)", r = String(s.reversed())
        for j in (0..<10).map { "\($0)" } + [""] {
            p.append(s + j + r)
        }
    }

    for n in p.map { Int($0)! * Int($0)! } {
        if Int(left)! <= n, Int(right)! >= n {
            var s = "\(n)", r = String(s.reversed())
            res += s == r ? 1 : 0
        }
    }

    return res
}

1751. Maximum Number of Events That Can Be Attended II

예제를 먼저 살펴보았다.

k 개의 이벤트를 고를 수 있고, 이벤트는 겹치면 안 되는 모양이다. 이벤트의 cost 가 가장 큰 조합을 찾는 문제인 듯 하다.

DP 문제처럼 생겼다.

시작 날짜로 정렬해준 후 f(i, j) 를 i 번째 이후로 최대 j 개의 이벤트를 골랐을 때 최대값이라 하자.

f(i, j) = max (i 번째 이벤트를 고른 경우), (고르지 않은 경우)

라고 할 수 있다.

func maxValue(_ events: [[Int]], _ k: Int) -> Int {
    let events = events.sorted { $0[0] < $1[0] }
    let arr = Array(repeating: -1, count: k + 1)
    var dp = Array(repeating: arr, count: events.count)

    func f(_ i: Int, _ j: Int) -> Int {
        if i >= events.count || j < 1 {
            return 0
        }

        if dp[i][j] != -1 {
            return dp[i][j]
        }

        let e = events[i]

        // let k = events.firstIndex { $0[0] > e[1] } ?? Int.max
        var k = i + 1
        while k < events.count, events[i][1] >= events[k][0] {
            k += 1
        }

        dp[i][j] = max( f(i+1, j), f(k, j-1) + e[2] )

        return dp[i][j]
    }

    return f(0, k)
}

메모이제이션이 없거나 firstIndex 를 사용하면 시간 제한에 걸린다...

1281. Subtract the Product and Sum of Digits of an Integer

설명이 한 줄이라 읽어보았다. 어떤 정수의 자릿수 전체의 곱과 합의 차를 구하는 문제이다.

예제도 단순했다.

func subtractProductAndSum(_ n: Int) -> Int {
    let arr = Array("\(n)").compactMap { Int("\($0)") }
    return arr.reduce(1, *) - arr.reduce(0, +)
}

타입 변환은 귀찮다.. 파이썬이 그립다....

1528. Shuffle String

예제를 확인해 보았다.

보아하니 캐릭터의 실제 인덱스가 주어지고, 그에 맞게 정렬된 문자열을 반환하는 문제인 듯 하다.

O(n) 메모리 가지고는 쉽게 풀 수 있지만... 이 문제의 의도는 인메모리 정렬이니까... 한번 스캔하면서 제자리가 아닌 애들은 제자리를 찾을 때까지 스왑을 해주면 된다.

func restoreString(_ s: String, _ indices: [Int]) -> String {
    var s = Array(s), indices = indices

    for i in 0..<s.count {
        var j = indices[i]

        while i != j {
            s.swapAt(i, j)
            indices.swapAt(i, j)
            j = indices[i]
        }
    }

    return String(s)
}

877. Stone Game

예제 부터 확인했다.

앨리스와 밥이 숫자를 하나씩 뽑는 문제인가 보다. 그리고 숫자의 합이 더 큰 사람이 이긴다. 최적의 플레이를 했을 때 앨리스가 이길 수 있는 지를 알아내면 된다.

그리디 알고리즘이 아닐까? 특히 첫 번째 무브에서 앨리스가 최대값을 뽑지 않으면 무조건 밥이 가져갈 것 같은데..

이렇게 생각하다 보니 답을 그냥 true 로 제출해봤다.

2088. Count Fertile Pyramids in a Land

Description 은 읽기 귀찮아서 예시 입력을 먼저 보았다.

피라미드와 인버스 피라미드 형태가 몇 개 있는지 세어 주는 문제인 듯 하다.

DP 문제가 아닐까? 행이 하나씩 추가되면 이전 결과값에 답을 더해가기 때문이다.

f(n) = f(n-1) + (새로 만든 피라미드) + (이어 붙인 피라미드)

• 새로 만든 피라미드는 단순히 ㅗ 모양임을 확인하면 된다.
• 이어 붙인 피라미드는 밑변의 길이를 메모하고 있어야 해서, g 라는 배열 하나를 더 추가한다.
• 인버스 피라미드는 grid 를 뒤집으면 되기 때문에 피라미드 문제만 풀면 된다.

그리드의 크기 제한을 확인했다.

1 <= m, n <= 1000
1 <= m * n <= 1e5

O(n^2) 인거 같으니 계속 하기로 한다...

func countPyramids(_ grid: [[Int]]) -> Int {
    var n = grid.count
    var m = grid[0].count

    func count(_ grid: [[Int]]) -> Int {

        var f = Array(repeating: 0, count: n)
        var g = Array(repeating: 0, count: m) // 현재 밑변의 길이가 2*g[k] - 1 인 피라미드의 중심이 여기에 있다.

        for i in 1..<n {
            f[i] = f[i-1]

            // Existing pyramid

            for j in 0..<m {
                if g[j] != 0 {
                    if j-g[j] >= 0,
                       j+g[j] < m,
                       Array(grid[i][(j-g[j])...(j+g[j])]) == Array(repeating: 1, count: 2*g[j] + 1) {
                        f[i] += 1
                        g[j] += 1
                    } else {
                        g[j] = 0
                    }
                }
            }

            // New pyramid

            for j in 1..<(m-1) {
                if grid[i][(j-1)...(j+1)] == [1, 1, 1], grid[i-1][j] == 1 {
                    f[i] += 1
                    g[j] = max(g[j], 2)
                }
            }
        }

        return f[n-1]
    }

    print(count(grid), count(grid.reversed()))
    return count(grid) + count(grid.reversed())
}

예제를 통과하지 못했다. 피라미드가 만들어지지 않는 조건을 추가했다.

guard n > 1, m > 2 else {
    return 0
}

그래도 통과가 안 된다. Existing pyramid 를 계산할 때 높이 4 짜리 피라미드가 높이 3짜리 피라미드를 동시에 포함하고 있음을 고려하지 못했다.

아래처럼 수정한다.

// Existing pyramid

for j in 0..<m {
    while g[j] >= 2 {
        if j-g[j] >= 0,
           j+g[j] < m,
           Array(grid[i][(j-g[j])...(j+g[j])]) == Array(repeating: 1, count: 2*g[j] + 1) {
            f[i] += g[j]-1
            g[j] += 1
            break
        } else {
            g[j] -= 1
        }
    }
}

1527. Patients With a Condition

이런.. SQL 문제가 뽑혔다. 다시 돌렸다.

223. Rectangle Area

그림과 예시를 먼저 봤다.

직사각형 2개를 주고 면적의 총 합을 구하는 문제였다.

겹치는 부분을 한 번 빼주면 될 거 같은데, 겹치는 좌표를 어떻게 구한담?

생각해보니 겹치는 좌표의 x, y 는 주어진 x, y 중 하나를 꼭 따라가게 되어있다.

코드 작성을 시작해 보았다. 우선 풀이를 쉽게 해주는 좌표 스트럭트와 좌표 2개로 면적을 리턴하는 메소드를 생성했다.

struct P {
    var x: Int
    var y: Int

    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }
}

func area(_ p: P, _ q: P) -> Int {
    (q.x - p.x) * (q.y - p.y)
}

잘 동작 하려나? p == q 인 경우에 0.. 머리 속으로 대충 돌려보니 맞는거 같다.

생각해보니 겹치는 좌표가 생기려면 변이 서로 겹쳐야 된다.

var overlapped = 0
if max(ax1, bx1) < min(ax2, bx2), max(ay1, by1) < min(ay2, by2) {
    overlapped = area(P(max(ax1, bx1), max(ay1, by1)), P(min(ax2, bx2), min(ay2, by2)))
}

그런데 area 함수에서 예외처리하면 if statement 를 없앨 수 있을 것 같다.

답:

class Solution {
    func computeArea(_ ax1: Int, _ ay1: Int, _ ax2: Int, _ ay2: Int, _ bx1: Int, _ by1: Int, _ bx2: Int, _ by2: Int) -> Int {
        struct P {
            var x: Int
            var y: Int
            init(_ x: Int, _ y: Int) {
                self.x = x
                self.y = y
            }
        }

        func area(_ p: P, _ q: P) -> Int {
            max(q.x - p.x, 0) * max(q.y - p.y, 0)
        }

        return
            area(P(ax1, ay1), P(ax2, ay2)) + 
            area(P(bx1, by1), P(bx2, by2)) - 
            area(P(max(ax1, bx1), max(ay1, by1)), P(min(ax2, bx2), min(ay2, by2)))
    }
}