[swift - algorithm] swift로 알고리즘 접근 기본

알고리즘 핵심: https://ios-development.tistory.com/525

swift로 알고리즘 접근

• 코드의 간결화를 위해 강제 unwraping 사용
• string타입에서 특정 character접근 시 [Charactor] or [String] 타입으로 변환하여 효율적으로 접근
  • String타입에서 특정 character 접근 시 O(N)
  • Array타입은 random access O(1)
  • String의 for문에서 value값은 String.Element형
    :(for문 안에서 Int형으로 변경하고 싶은 경우, String으로 먼저 변형)
• swift는 Array, Set, Dictionary 세 가지 collection을 제공하므로 나머지 세 가지에 대해 어떻게 쓸것인지 미리 고민
  • Heap: 
  • Stack: 기본 배열 사용 (push는 append(), pop은 removeLast() 사용)
  • Queue: 기본 배열과 커서값을 활용해서 구현

키보드 입력

• 콘솔, 키보드 입력

let value = readLine()!

• 입력 + 특정 문자열로 파싱

// components로 형변환 할경우 import Foundation 추가
// split의 결과는 Substring으로 리턴 (단, 일반 String처럼 사용가능)

let nums1 = readLine()!.components(separatedBy: " ")
let nums2 = readLine()!.split(separator: " ").map { String($0) }

• cf) 줄바꿈되지 않고 출력하는 방법
  : 출력에서 print()문은 default가 print(값, terminator: "\n")인 상태이므로, print(값, terminator: "")로 수정해주어야 줄바꿈 방지
• 하나의 값 입력

let number = Int(readLine()!)!

• 2개의 값 입력

let numbers = readLine()!.split(separator: " ").map {Int($0)!}
let a = numbers[0]
let b = numbers[1]

• N개 만큼의 줄 입력

var lines = [Int]()
for i in 0..N {
  lines.insert(Int(readLine()!)!, at: 0)
}

배열

• 1차원 배열
  • 빈 값: let arr = [Int]()
  • 초기화된 배열: let arr = [Int](repeating: 0, count: 3)
• 2차원 배열
  • 빈 값: let arr = [[Int]]()
  • 초기화된 배열:(3x5배열 예시) let arr = [[Int]](repeating: [Int](repeating: 0, count: 5), count: 3)
• 정렬
  • 거꾸로 정렬: let reversedArr = arr.reverse() // reversed()가 아님을 주의
  • 오름차순: let arr = arr.sorted()
  • 내림차순: let arr = arr.sorted(by: >)
  • 커스텀: let sortedArr = arr.sorted(by: { $0.someKey < $1.someKey })
    • 단, 구조체를 사용할 경우 arr.sort()하면 컴파일 에러가 나므로 let res = sorted(by:)하여 사용
• 배열에서의 최댓값

let max = arr.max()!

• 배열 통째로 합치기: contentsOf

arr.append(contentsOf: anotherArr)

문자열

• 파싱
  • 간단한 파싱: split(separator: ) 사용
  • prefix: "12345".prefix(3) // "123"
  • suffix: "12345".suffix(3) // "345"
  • substring: let subStr = str[start...end]
• String을 순회활때 자료형이 String.Element이므로, 다른형으로 형변환 할 경우 String으로 먼저 변환 후 시도

• n번째 문자 index: let index = str.index(str.startIndex, offsetBy: n-1)
• 특정 문자의 index, 검색: "123".index(firstOf: "3")
• 특정 문자열 치환: str.replacingOccurences(of: "바꿀 문자열" with: "삽입될 문자열")
• 문자열 -> 아스키 코드 변환: Character("a").asciiValue!

let a = Character("a").asciiValue!
let b = Character("b").asciiValue!
print(b - a) // 1

• 소수점 아래 자릿수 제한하여 string으로 표현: String(format: "%.2f", 1.1234)
• 대문자 <-> 소문자
  • 소문자로: "HELLO".lowercased()
  • 대문자로: "hello".uppercased()

Higher order function (함수를 인수, 리턴할 수 있는 성질)

• map
  • string -> Int 매핑
    - let str = ["1", "2", "3"]
      let intArr = arr.map { Int($0)! }
• filter
  • 조건에 맞는 값 리턴
• reduce
  • 배열 안에서 원소들의 사칙연산
    - let arr = [1, 2, 3, 4]
      let sumValue = arr.reduce(0, +)
      let multipleValue = arr.reduce(1, *)

for문

• 되도록 for문보다 map사용
• 리턴값이 필요없는 map을 사용하고 싶은 경우: forEach사용

let arr = [1, 2, 3, 4]

arr.forEach {
    print($0)
}

• value값 뿐만이 아닌 index가 필요한 경우: enumerate (단, for-in문을 지양하고 map이나 for-each로 접근할 것)

let arr = [1, 2, 3, 4]

for (index, value) in arr.enumerated() {
    print(index, value)
}

• 특정 index를 알고싶은 경우는 enumerate, filter, map 사용
  - enumerate할 경우, element, offset 사용가능

let arr = [3, 2, 12, 32]

let index = arr.enumerated()
    .filter { $0.element == 12 }
    .map { $0.offset }
    .first

 

• 원하는 수치만큼 증가 or 감속 반복문

// 6 포함 x
for i in stride(from: 0, to: 6, by: 2) {
    print(i)
}

// through는 6 포함
for i in stride(from: 0, through: 6, by: 2) {
    print(i)
}

Dictionary

• key값으로 value 접근: unwrapping 필요
  • dictionary[4]!
• for에서 값은: key, value (단 dictionary자료형은 순서는 존재 x)
• 값 추가 or 수정

var dic = [Int: Int]()
dic[4] = 1

• 값 삭제

dic[4] = nil

• key or value값을 기준으로 정렬

let sortedDic = dic.sorted(by: { $0.value < $1.value })

숫자

• 거듭제곱: pow(밑, 지수)

pow(2, 3) // 8

• 타입 범위

* Int     = Int64와 동일 (맥 64비트이므로 2^64-1)
* Int64   = 9223372036854775807   // 19자리
* Int32   = 2147483647  // 10자리
* Float   = 소수점 6자리까지 표현 가능
* Double  = 소수점 15자리까지 표현 가능

• 지수
  • 10진수 -> n진법: String(integer, radix: n)
  • n진법 -> 10진수: Int("11001"m radix: n)!
• 절대값: abs(-28)
• 올림 / 내림 / 반올림
  • ceil(6.3) // 7 (Double)
  • floor(6.3) // 6
  • round(6.3) // 6

전역 변수를 사용하지 못할 경우, inout

• 타입 앞에 inout 정의

func swap(_ a: inout Int, _ b: inout Int)

• 접근: `&` 사용

var a = 1
var b = 2

swap(&a, &b)

mutating 키워드 

• struct에서 프로퍼티의 값을 변경할 땐, 프로퍼티가 var로 설정되어 있어도 mutating 키워드가 없으면 에러

• mutating 키워드 적용

Set 사용법

• Set<Int>()로 선언하여 사용

var s = Set<Int>()
s.insert(0)
s.insert(1)
print(s) // [0, 1]

s.remove(0)
print(s) // [1]

for value in s {
    print(value) // 1
}

• Set배열

var s = [Set<Int>](repeating: Set<Int>(), count: 8)
s[0].insert(0)
s[0].insert(1)

print(s[0])

함수 외부에 전역변수 없이, 함수내부에서 전역변수처럼 사용하는 방법

• visit, answer와 같은 변수를 inout변수로 만들지 않는 방법: 함수 내부에 함수선언

func solution(_ numbers: [Int]) -> [Int] {
	var visit = [Bool](repeating: false, count: numbers.count)
    var answer = [Int]()
    
    func dfs(_ start: Int, _ cnt: Int) {
    }
    
    dfs()
    return answer
}

배열에 append보단 += 로 접근

var arr = [1, 2, 3]

// 배열에 4를 추가하고 싶은 경우
arr += [4] // good!
arr.append(4) // not good

* 문제 유형

- dfs, bfs, 백트래킹, 재귀, 순열과 조합: ios-development.tistory.com/423

- DP: https://kd-codebook.tistory.com/64