Taehyeon-Kim/SwiftAlgorithm

Tip

Closed this issue · 5 comments

Taehyeon-Kim commented

입력 시간

let nums = readLine()!.split(separator: " ").compactMap { Int(String($0)) }
let nums = readLine()!.split(separator: " ").compactMap { Int($0) }
let nums = readLine()!.components(separatedBy: " ").compactMap { Int($0) }
  • split이 components보다 빠르고, SubString을 String타입으로 캐스팅하고 Int타입으로 캐스팅하는 것이 더 빠르다.
Taehyeon-Kim commented

구현

  • 반복문부터 시작된다. 기준점을 정해놓고 좌우를 체크하거나, 상하좌우를 체크하거나 하는 경우가 많다.
  • 1차원 배열의 경우는 좌우 체크, 2차원 배열의 경우는 상하좌우 체크가 되겠지.

범위에 주의

  • ex. boj 11967 불켜기
  • (0..<n) 범위를 (1...n)로 생각해야 할 때, 실수로 범위를 잘라서 계산하는 경우가 있었음
  • 아예 처음부터 zero-indexed로 계산하거나, 주의를 해야 함.
Taehyeon-Kim commented

문자열

func compare(_ lhs: [Character], _ rhs: [Character]) -> Bool {
    guard lhs.count == rhs.count else { return false }

    for (lhsChar, rhsChar) in zip(lhs, rhs) {
        guard rhsChar == "*" || lhsChar == rhsChar else { return false }
    }
    return true
}
  • 문자열 자체를 비교할 때 zip을 유용하게 사용할 수 있음(위와 같은 느낌)
Taehyeon-Kim commented

경우의 수

  • 도구로써 순열과 조합을 사용하는 일이 정말 많다. 전체 원소의 수가 많지 않은 상황에서 여러가지 케이스를 살펴보아야 한다면 순열과 조합을 적절하게 이용해보도록 하자. (단순 케이스 산출이라면 반복문만 이용해도 괜찮을 것 같다.)
  • 다른 언어에서는 기본으로 제공되는 STL이 있지만 Swift는 없기 때문에 반드시 원활하게 쓸 수 있도록 암기가 필수다.
Taehyeon-Kim commented

for문

for i in 0..<n {
    for j in coins[i]...k {
        if j < coins[i] { break }
        if dp[j] + dp[j - coins[i]] >= Int(pow(2.0, 31.0)) {
            dp[j] = 0
        } else{
            dp[j] += dp[j - coins[i]]
        }
    }
}
  • 런타임 에러 발생
for i in 0..<n {
    for j in stride(from: coins[i], through: k, by: 1) {
        if dp[j] + dp[j - coins[i]] >= Int(pow(2.0, 31.0)) {
            dp[j] = 0
        } else{
            dp[j] += dp[j - coins[i]]
        }
    }
}
  • stride는 알아서 반복문 종료
Taehyeon-Kim commented

sort(), sorted()

  • 오늘 문제 풀다가 희한한 상황을 맞이했다.
  • 숫자 카드 2
  • 위의 문제는 연속된 숫자의 개수를 체크하는 것을 이분탐색으로 구현해서 접근한 문제였다.
  • 이분탐색에는 딱히 문제가 없는데 시간초과가 계속 발생해서 sorting하는 코드를 원본 sort()에서 sorted() 하고 값을 복사하는 식으로 바꿨더니 문제가 통과하는 이상한 상황이 발생했다.
  • 공식문서 찾아보면 두 메소드 모두 O(n log n)의 시간복잡도를 가진다고는 하는데 원인을 잘 모르겠다. 일단은 sorted()를 이용하기로 하자.