20230329 TIL

어제 올린 TIL과 포스팅에 몇몇 분들이 응원의 댓글을 달아줘서 너무 힘이 되었습니다 !!!

감사해용 .. 🥲 안그래도 요즘 사람도 잘 안만나고, 이런저런 걱정에 조금 힘들었는데 

덕분에 오늘도 열시미 공부 하구.. 티스토리를 쓰러 왔습니다 >< ! 

 

 

1. 알고리즘 풀이 - 두 큐 합 같게 만들기

 

- 처음에 문제를 보고, removeFirst 쓰면 무조건 시간초과 나겠구나 싶어서 포인터를 활용했습니다.

- 그런데 이렇게 풀었음에도 불구하고.. 11번이랑 28번에서 시간초과가 나네요.... 😀

    var sum1 = queue1.reduce(0,+)
    var sum2 = queue2.reduce(0,+)

    let sum = sum1 + sum2

    let target = sum / 2

    var queue1 = queue1
    var queue2 = queue2

    var moveCount = 0

    var pointer1 = 0
    var pointer2 = 0
    
    if sum % 2 != 0 {
        return -1
    }

    while sum1 != target {

        let popNum1 = queue1[pointer1]
        let popNum2 = queue2[pointer2]

        if sum1 < sum2 {
            queue1.append(popNum2)
            pointer2 += 1
            sum1 += popNum2
            sum2 -= popNum2
        } else {
            queue2.append(popNum1)
            pointer1 += 1
            sum1 -= popNum1
            sum2 += popNum1
        }

        if pointer1 >= queue1.count || pointer2 >= queue2.count {
            return -1
        }
        
        moveCount += 1
    }

    return moveCount

 

- 결국, 풀이를 찾아보니 전부다 2개의 큐를 합쳐서 하나의 배열로 만든다음, 거기서 투 포인터를 돌리더라구요 !

- 참고해서 아래와 같이 개선해줬습니다 ! 

    
    var sum1 = queue1.reduce(0,+)
    var sum2 = queue2.reduce(0,+)

    let sum = sum1 + sum2

    let target = sum / 2

    var queue = queue1 + queue2

    var moveCount = 0

    var pointer1 = 0
    var pointer2 = queue1.count
    
    if sum % 2 != 0 {
        return -1
    }

    while sum1 != target {
        
        if pointer2 >= queue.count || pointer1 >= pointer2 {
            return -1
        }

        let popNum1 = queue[pointer1]
        let popNum2 = queue[pointer2]

        if sum1 < sum2 {
            pointer2 += 1
            sum1 += popNum2
            sum2 -= popNum2
        } else {
            pointer1 += 1
            sum1 -= popNum1
            sum2 += popNum1
        }
        
        moveCount += 1
    }

    return moveCount

- 놓쳤던 부분은 큐 2개를 이어 붙이게 되면, 앞에서 빼주고 뒤로 붙여주는 식의 이동을 구현해 낼 수 있다는 점 !

- 그리고 어차피 하나의 큐를 모두 확인할 때까지 합이 안맞으면 -1을 return 하면 되기 때문에

queue의 요소들을 따로 건드릴 필요없이 구현해야 시간초과가 안난다는 사실... 

 

 

 

2. 알고리즘 풀이 - 보석쇼핑

두 큐 합 같게 만들기와 동일한 유형으로,

알고리즘 스터디 지정 문제였습니다. 

 

핵심 : 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며,

만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

 

-> 구간을 찾는 문제이니 투 포인터나 슬라이딩 윈도우를 이용하면 될 것이라고 생각했고,

크기가 고정되어있지 않으니 투포인터를 사용해서 풀어야겠다 생각을 해써요.

 

그런데 위의 문제의 경우 sum으로 더하고 빼주면 되지만,

보석 쇼핑의 경우 String값이기 때문에 어떻게 관리를 해죠야 할지 고민했습니다.

 

처음에는 매번 start와 end를 update하면서 Set(gems[start...end]) 를 계산해서 포함되어있는지 확인했습니다.

근데 두큐합같 풀때와 마찬가지로 while 문 내부에서 저렇게 매번 Set을 만들어낸다면,

시간 복잡도가 최악의 경우 O(N^2) 이 되어버립니다. ( GPT가 알려줌 ! 똑똑잉 )

 

그래서 포인터를 옮기면서 새롭게 추가되거나 제거되는 보석을 담을 별도의 자료형이 필요하다고 생각했습니다.

GPT의 힌트를 참고해서, Dictionary를 만들어줬습니다. 

그리고 보석의 종류가 부족하면 right를 늘려주고, 충분하면 left를 늘려주는 과정을 반복합니다.

이 과정에서 Dictionary에 보석의 종류를 저장해주면 됩니다 !

매번 Set을 만들지 않고 딕셔너리 값을 조회만 해서 확인할 수 있습니다.

 

요즘엔 바로 다른 사람의 풀이의 전체를 보는 것이 아니라, GPT를 활용해서 

저의 답안에서 틀린 점을 알려달라고 한다음에 그걸 바탕으로 고쳐보는 식으로 하고 있어요 !

 

func solution(_ gems:[String]) -> [Int] {
    let gemSet = Set(gems)
    var gemDict = [String: Int]()
    var left = 0
    var right = 0
    var minLength = gems.count
    var result: [Int] = [left+1, gems.count]
    
    while true {
        if gemDict.count == gemSet.count {
            // 현재 구간이 모든 보석을 포함하는 경우
            if right - left < minLength {
                minLength = right - left
                result = [left+1, right]
            }
            
            if let count = gemDict[gems[left]] {
                if count == 1 {
                    gemDict.removeValue(forKey: gems[left])
                } else {
                    gemDict[gems[left]] = count - 1
                }
            }
            left += 1
        } else if right == gems.count {
            break
        } else {
            // 현재 구간이 모든 보석을 포함하지 않는 경우
            if let count = gemDict[gems[right]] {
                gemDict[gems[right]] = count + 1
            } else {
                gemDict[gems[right]] = 1
            }
            right += 1
        }
    }
    
    return result
}

이렇게 했더니, 통과했습니다 ! 하지만, 코드를 더 깔끔하게 고칠 수 있을 것 가타요.

다음에 다시 풀어봐야겠어요 ! 

 

알고리즘 공부를 열심히 하고 있긴한데 생각보다 하루에 많은 문제를 풀진 못하네요.. ㅜㅜ

새롭게 알게되는 것도 너무 많고. 미리미리 안한걸 많이 후회중이에여.. 쩝.. 

하지만 과거의 잘못은 빨리 청산하고 ㅋㅋ 이제서라도 열심히 풀어서 다행이라고 생각하기로.. 

Lv3은 아직 혼자 힘으로 풀기 어렵네요 😅

 

 

 

 

3. SwiftUI 튜토리얼 

https://suvera.tistory.com/56

SwiftUI) SwiftUI Essentials

https://suvera.tistory.com/57

SwiftUI) SwiftUI Essentials - 2

유진언니랑 같이 스유 튜토리얼 하루 한 챕터씩 4일안에 뽀개기 ! ㅋㅋ 

오늘 챕터1 까지 했습니다요. 정리하면서 하니까 죄금 귀찮긴 한데 더 이해가 잘되네용.

그리고 역시 뭔가 할땐 다른 사람들이랑 같이 하는걸 더 좋아하는 것 같아요..

요즘엔 거의 스터디 구걸중.. 제발 나랑 스터디 해줘 .. 이런 느낌.. ? 

 

SOPT 할때는 정말 스터디할 기회가 너무 많았는데, 요즘엔 마음에 맞는 스터디원 구하기가 

하늘의 별따기인듯 합니다.. 그래도 스알뿌 사람들이 있어서 다행이에요.. 😆

SOPT 사람들 만큼 열정적인 사람들로 스터디를 구성하기가 정말 힘든 것 같네요.. !!

그래서 이번 비활로 스터디 한번 참여해볼까했는데 거의 다 활동기수 제한이더라구요 ㅋㅋㅋ

직접 열기에는 또 부담스럽기도 하고.. 내일까지니 한번 고민해봐야게써요.. 

 

 

늦었지만, 다들 오늘 하루 고생하셨습니다 😎