# 필수
<details>
<summary>Two Sum</summary>

# 문제
- 매개변수로 숫자배열과 타겟을 받는다
- 더하면 target이 되는 숫자 2개를 배열에서 꺼내 인덱스를 리턴한다
- 답은 하나이며, 같은 숫자를 더하지 않는다

# 풀이

## O(N^2)

### 로직

1. for문을 돌려 배열에서 첫번째 숫자를 꺼낸다. 중복을 허용하지 않으므로 마지막에서 그 앞 숫자까지 돌린다
2. 이중 for문을 돌려 배열에서 두번째 숫자를 꺼낸다. 중복을 허용하지 않으므로 첫번째 숫자 바로 뒤의 숫자부터 반복문을 돌린다
3. 첫번째 숫자와 두번째 숫자의 합이 target일때까지 반복을 수행한다

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for i in 0..<nums.count - 1 {
        for j in i + 1..<nums.count {
            if nums[i] + nums[j] == target {
                return [i, j]
            }
        }
    }
    return []
}

### 개선이 필요한 사안

1. 배열에서 숫자를 꺼낼 때 딕셔너리를 이용하면 두번째 for문을 O(1)로 바꿔줄 수 있을 것 같다

## O(N)

### 로직

1. nums 배열을 딕셔너리로 바꿔준다. 이때 키값을 배열의 인덱스가 아닌 값으로 표현해야 두번째 숫자가 딕셔너리에 있는지 확인할 수 있으므로 key:값, value:인덱스로 한다.
2. 딕셔너리에 값을 넣기 전에 찾고자하는 두번째 숫자가 딕셔너리에 있는지 확인한다. 있다면 두번째 숫자와 리턴하며 반복을 종료한다

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var dic = [Int: Int]()
    for i in 0..<nums.count {
        if let j = dic[target - nums[i]] {
            return [i, j]
        } else {
            dic.updateValue(i, forKey: nums[i])
        }
    }
    return []
}

### 다른 문제에서 응용해볼만한 것들

1. 만약 인덱스를 리턴하는 게 아니라 숫자들을 리턴하는 거라면 굳이 인덱스를 저장할 필요가 없으니까 set를 활용해볼 수 있을 것 같다
</details>
<details>
<summary>Reverse Integer</summary>

# 문제

- Int32를 받는다
- 숫자를 뒤집어서 리턴한다
- 음수는 뒤집어도 음수다
- 앞에 0이 오면 제거한다
- 만약 뒤집었을 때 Int32의 범위를 벗어나면 0을 리턴한다

# 풀이

## 기존 방법

### 로직

1. 숫자를 String으로 변환한다
- 만약 음수이면 앞에 (-)를 제거한다
2. String을 .reversed() 메서드로 뒤집고 Int로 전환한다
3. 다음의 로직에 따라 뒤집힌 숫자를 리턴한다
- 만약 Int32의 범위를 벗어나지 않고
- 숫자가 음수였으면 (-) 부호를 붙인다
- 음수가 아니면 붙이지 않는다
- Int32의 벗어나면 0을 리턴한다

func reverse2(_ x: Int) -> Int {
    let str = x < 0 ? String(String(x).dropFirst()) : String(x)
    let result = Int(String(str.reversed()))!
    return result >= Int32.min && result <= Int32.max ? x < 0 ? -(result) : result : 0
}

</details>
<details>
<summary>Remove Duplicates From Sorted List</summary>

# 문제

- 정렬된 리스트를 받아 중복제거 후 리턴한다

# 풀이

### 로직

1. 리스트의 head를 받아온다
2. 현재 노드가 `nil`이 아닐 때까지 아래 로직을 반복한다
3. 현재 노드와 다음노드를 비교한다
1. 만약 같다면 다음 노드를 그 다음 노드로 지정한다 - 현재 노드는 변경되지 않고 그 다음 노드의 값과 동일한지 비교하게 된다
2. 다르다면 현재노드를 다음 노드로 변경한다

func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    var curr = head
    while curr != nil {
        if curr?.val == curr?.next?.val {
            curr?.next = curr?.next?.next
        } else {
            curr = curr?.next
        }
    }
    return head
}

</details>

<br/><br/>
# 선택
<details>
<summary>Palindrome Number</summary>

# 문제

- 숫자를 받는다
- 만약 그 숫자를 뒤집어도 같다면 true, 아니면 false를 리턴한다
- 음수는 뒤집으면 부호가 뒤로가게 되므로 false이다
- 10을 뒤집으면 앞에 0이 제거되어 1이 되므로 false이다

# 풀이

### 로직

1. 숫자를 String으로 변환하여 뒤집은 것과 같은지 비교 후 결과값을 리턴한다

func isPalindrome(_ x: Int) -> Bool {
    String(x) == String(String(x).reversed())
}

</details>
<details>
<summary>Longest Common Prefix</summary>

# 문제

- 문자열 배열을 받는다
- 문자열들의 공통된 접두어를 반환한다
- 만약 없다면 “”을 반환한다

# 풀이

## 처음 풀이 - O(N^2)

### 로직

1. 첫번째 단어를 저장하고, 인덱스를 1로 지정한다
2. 배열에 있는 단어를 다 돌거나 접두어가 “”일 때까지 반복한다
3. 접두어가 현재 단어의 접두어가 될 때까지 접두어의 마지막 글자를 제거한다

func longestCommonPrefix3(_ strs: [String]) -> String {
    var prefix = strs[0]
    var i = 1
    
    while i < strs.count && !prefix.isEmpty {
        while !strs[i].hasPrefix(prefix) { prefix.removeLast() }
        i += 1
    }
    
    return prefix
}

### 개선방안

- 시간 복잡도를 줄일 수 없는지 생각해보았다
- 만약 배열의 가장 짧은 단어와 가장 긴 단어만 비교할 수 있다면 O(N)으로 줄여볼 수 있을 것 같았다

## 개선된 풀이 - O(N)

### 로직

1. 배열을 글자 수 순으로 정렬한다 (NlogN)
2. 첫번째 단어와 두번째 단어를 글자 단위로 반복한다
3. 첫번째 단어의 글자와 두번째 단어의 글자를 비교한다
1. 만약 같으면 리턴할 변수에 추가하고 다음 글자로 넘어간다
2. 같지 않으면 반복문을 벗어난다

func longestCommonPrefix4(_ strs: [String]) -> String {
  let sorted = strs.sorted()
    var result = ""
    
    for (charOfFirstWord, charOfLastWord) in zip(sorted.first!, sorted.last!) {
        if charOfFirstWord == charOfLastWord {
            result += String(charOfFirstWord)
        } else {
            break
        }
    }
    
    return result
}

</details>
<details>
<summary>Linked List Cycle</summary>

# 문제

- Linked List의 헤드를 받는다
- 원형이면 true, 아니면 false를 반환한다
- tail은 head를 가르킬 수도, list안에 있는 다른 노드를 가르킬 수 있다

# 풀이

### 로직

1. 노드를 두개 만들어서
1. 하나는 하나씩 다음으로 넘어가고
2. 다른 하나는 두칸씩 넘어가도록 하여
2. 따라잡히면 순회하는 것이므로 true를 반환하도록 하였다
3. 그리고 두개의 노드 중 하나라도 nil이면 순회하지 않는 것이기 때문에 두 노드 모두 nil이 아닐 때까지 위의 로직을 반복하도록 실행하였다
4. 반복문을 벗어나는 경우는 nil인 경우이므로 false를 반환한다

func hasCycle(_ head: ListNode?) -> Bool {
    var once = head
    var twice = head?.next
    
    while let movedOnce = once, let movedTwice = twice {
        if movedOnce === movedTwice { return true }
        once = once?.next
        twice = twice?.next?.next
    }
    
    return false
}

</details>