[Leet.3488] Streak Day 98-99 🔥

요즘 Challenge1을 시작하고 나서 계속 회의를 하고, 또 스스로 확신이 없으니까 계속 리서치를 하게 되더라. 그러다 보니 개인적인 시간이 거의 없어지는 느낌이다. 그러다보니 알고리즘 문제를 오랫동안 붙잡고 있으면 정작 중요한 SwiftUI가 밀리다보니.. 이게 알고리즘 문제가 조금 어려운 건 이틀에 걸쳐서 푸는걸로 한번 계획을 변경해보고자한다.

3488. Closest Equal Element Queries

---

문제 설명

• 원형 배열 nums와 query배열이 주어진다.
• query에서 원소하나씩 빼서 query[i] -> nums[query[i]] 를 실행하고
• nums내에서 nums[query[i]]에서 가장 가까운 원소까지의 거리를 구하라

---

문제 풀이

class Solution {
    func solveQueries(_ nums: [Int], _ queries: [Int]) -> [Int] {
        var answer = [Int]()
        for (idx, element) in queries.enumerated() {
            var move = 0
            let target = nums[element]

            var left = element - 1
            var right = element + 1
            var cnt = 1
            while left != element, right != element, left != right { // 한바꾸돌아서 마주치면안됨
                left -= move
                right = (right + move) % nums.count
                if left == -1 {
                    left = nums.count - 1
                }
                print("left : \(left), right : \(right) , move : \(move)")
                if nums[left] == target || nums[right] == target {
                    answer.append(cnt)
                    break
                }
                cnt += 1
                move = 1
            }
            if answer.count < idx + 1 {
                answer.append(-1)
            }
        }
        return answer
    }
}

print(Solution().solveQueries([1, 3, 1, 4, 1, 3, 2], [0, 3, 5]))

원하는 출력 : [2,-1,3]
내 코드 : [2,7,3]

그니까 못 찾았을 때에 대한 부분만 보완이 되면 될 것 같은데,
그래서 결국 cnt가 아직 while문에 걸리기전에 문제가 되는 것 같아서, cnt == nums.count 즉 한바퀴를 돌았을때에 대해서 -1을 append하도록 해줬으나, 시간초과가 발생했다..

⏲️ TIME LIMITED ⏲️

그래서 결국 이제 한바퀴 도는게 부담이라면! , 배열에서 미리 탐색을 좀 해주고 같은 원소 내에서 돌리는 것으로 수정하려했다.

class Solution {
    func solveQueries(_ nums: [Int], _ queries: [Int]) -> [Int] {
        var answer = [Int]()
        let LEN = nums.count
        for element in queries {
            let target = nums[element]
            var position = [Int]()

            nums.enumerated().map { index, value in
                if value == target {
                    position.append(index)
                }
            }
            if position.count == 1 {
                answer.append(-1)
                continue
            }
            var min_move = Int.max
            for item in position {
                if item == element { // 시작점과 같은건 패스!
                    continue
                }
                let direct = abs(item - element)
                let circular = min(direct, LEN - direct)
                min_move = min(min_move, circular)
            }
            answer.append(min_move)
        }
        return answer
    }
}

이렇게 야무지게 잘 개선했다고 생각했는데... 🤯🤯

또 시간초과 떠서 이거는 보내줘야겠다는 생각을 했다...

최종 제출 코드

마지막에 힌트까지보면서 BS로 풀어서 냈음에도 계속 612/614 614/614에서 걸리는거보니 엄청나게 빡빡하게 시간낭비가 전혀없어야했구나 + 빨리끝날 수 있게 특성 케이스 처리도 다 해줘야하는구나를 좀 알 수 있었다.
풀지못했으니 스킵..

타인의 코드

class Solution {
    func solveQueries(_ nums: [Int], _ queries: [Int]) -> [Int] {
        var positions = [Int: [Int]]()
        for (index, value) in nums.enumerated() {
            positions[value, default: []].append(index)
        }
        
        let LEN = nums.count
        var answer = [Int]()
        
        for queryIndex in queries {
            let target = nums[queryIndex]
            guard let indices = positions[target], indices.count > 1 else {
                answer.append(-1)
                continue
            }
            
            // 현재 쿼리 인덱스와 가장 가까운 인덱스 찾기
            var minMove = Int.max
            
            // 이진 탐색을 이용해 queryIndex의 위치 찾기
            var position = -1
            for i in 0 ..< indices.count {
                if indices[i] == queryIndex {
                    position = i
                    break
                }
            }
            
            // 이진 탐색으로 가장 가까운 왼쪽과 오른쪽 인덱스 찾기
            if position > 0 {
                // 왼쪽에 있는 가장 가까운 인덱스
                let leftIndex = indices[position - 1]
                let direct = abs(leftIndex - queryIndex)
                let circular = min(direct, LEN - direct)
                minMove = min(minMove, circular)
            }
            
            if position < indices.count - 1 {
                // 오른쪽에 있는 가장 가까운 인덱스
                let rightIndex = indices[position + 1]
                let direct = abs(rightIndex - queryIndex)
                let circular = min(direct, LEN - direct)
                minMove = min(minMove, circular)
            }
            
            // 원형 배열이므로 첫 번째와 마지막 인덱스 사이의 거리도 확인
            if position == 0, indices.count > 1 {
                let lastIndex = indices[indices.count - 1]
                let direct = abs(lastIndex - queryIndex)
                let circular = min(direct, LEN - direct)
                minMove = min(minMove, circular)
            }
            
            if position == indices.count - 1, indices.count > 1 {
                let firstIndex = indices[0]
                let direct = abs(firstIndex - queryIndex)
                let circular = min(direct, LEN - direct)
                minMove = min(minMove, circular)
            }
            
            answer.append(minMove)
        }
        
        return answer
    }
}

---

positions 딕셔너리에 각 숫자의 등장 인덱스 저장

var positions = [Int: [Int]]()
for (index, value) in nums.enumerated() {
    positions[value, default: []].append(index)
}

각 값이 나타난 인덱스들을 딕셔너리에 저장합니다.

• 예시: nums = [1, 2, 1, 3, 1]의 경우

positions = [
    1: [0, 2, 4],
    2: [1],
    3: [3]
]

---

값이 한 번만 등장하면 자기 자신밖에 없으므로 -1 추가

guard let indices = positions[target], indices.count > 1 else {
    answer.append(-1)
    continue
}

indices 배열에서 queryIndex의 위치 찾기

var position = -1
for i in 0 ..< indices.count {
    if indices[i] == queryIndex {
        position = i
        break
    }
}

• indices 배열에서 queryIndex의 위치를 찾고,

  첫 번째나 마지막 위치의 경우 원형 연결 고려하기

if position == 0, indices.count > 1 { ... }
if position == indices.count - 1, indices.count > 1 { ... }

• 첫 번째 위치/마지막 위치일대는 특별처리를 해줘야하는데, 뭔가 보편적으로 다 먹히게 수식을 자려다가 엄청 오래걸린것 같다..

---