코딩테스트 잔기술

코딩테스트 문제 풀 때 자주 쓸 수 있는 잔기술들

입력 받기

공백으로 나누어진 숫자 받기

let inputs = readLine()!.split(separator: " ").map { return Int($0)! }

2차원 배열 받기 (nxm)

var arr = Array(repeating: [Int](), count: n)

for i in 0..<m {
    arr[i].append(contentsOf: readLine()!.split(separator: " ").map { return Int($0)! })
}

아스키코드 변환

Unicode → Int (UInt32)

UnicodeScalar("문자(하나)")?.value

Int → Unicode

UnicodeScalar(숫자)

String

let str = "adcde"
for i in str.utf16 {
	print(i)
}

2차원 배열 회전

90도

func rotateAMatrixBy90Degree(_ matrix: [[Int]]) -> [[Int]] {
    let n = matrix.count
    let m = matrix[0].count
    var result = Array(repeating: Array(repeating: 0, count: n), count: m)
    
    for i in 0..<n {
        for j in 0..<m {
            result[j][n-i-1] = matrix[i][j]
        }
    }
    return result
}

시간복잡도 가늠하기

N이 100만이라고 할 때 $O(NlogN)$은 몇 번정도의 연산을 하는 걸까?
100만 X $log$ 100만 이고, 소프트웨어 공학에서 $log$ 함수의 밑은 2이다.
그렇다면 $log$ 100만은 ?

2의 10승은 1024니까 대략 1000이라고 생각하자
그렇다면 2의 20승은 1000x1000 = 1000000
즉, 100만이다.
2의 30은 100만x1000이니까 10억 정도

따라서 $log$ 100만은 대략 20이라고 생각할 수 있고, 100만 x 20 = 200만이므로
데이터 N의 개수 100만일 때, 시간복잡도 $O(NlogN)$의 알고리즘에서는 약 200만 번의 연산이 이루어 진다고 생각할 수 있다!

파이썬 기준 1초에 약 2000만 번의 연산을 수행할 수 있으므로 1초짜리 문제에서는 안정적이다고 할 수 있다.

소수점 다루기

소수점 6자리까지 표현하기

String(format: "%.6f", 숫자)

배열 custom sort하기

points.sort(by: sortPoints(this:that:))

func sortPoints(this: Point, that: Point) -> Bool {
    if this.x == that.x {
        return this.y > that.y
    }
    else {
        return this.x > that.y
    }
}

or

let sortedArr = lines.sorted(by: {$0.length > $1.length})

참고

https://zeddios.tistory.com/340
https://book.naver.com/bookdb/book_detail.nhn?bid=16439154