[Algorithm] 수열과 구간 쿼리 2 (w/ Swift)

 

 

수열과 구간 쿼리 2

 

 

프로그래머스

 

 

---

 

w/ Swift

 

1. 문제 확인

• arr라는 정수 배열이 주어짐
• queries라는 2차원 배열이 주어짐 ([s, e, k] 형태)
• 각 쿼리에 대해 s ≤ i ≤ e인 범위에서 k보다 크면서 가장 작은 arr[i]를 찾아야 함
• 만약 그런 값이 없으면 -1을 반환

 

2. 제한사항 체크

• arr 길이는 1 이상 1,000 이하
• queries 길이는 1 이상 1,000 이하
• arr의 원소는 1 이상 1,000,000 이하
• queries의 [s, e, k]에서 s~e는 arr의 인덱스 범위 안에 있음
• k도 1 이상 1,000,000 이하

제한이 크진 않아서 그냥 쿼리 하나씩 돌면서 조건에 맞는 값 찾는 방식이면 충분할 것 같아!

 

 

func solution(_ arr: [Int], _ queries: [[Int]]) -> [Int] {
    var result = [Int]()
    
    for query in queries {
        let (s, e, k) = (query[0], query[1], query[2])
        var minValue: Int? = nil
        
        for i in s...e {
            if arr[i] > k {
                if let currentMin = minValue {
                    minValue = min(currentMin, arr[i])
                } else {
                    minValue = arr[i]
                }
            }
        }
        
        result.append(minValue ?? -1)
    }
    
    return result
}

 

 

3. 풀이 설명

1. 결과 저장할 result 배열을 만들고,
2. queries를 하나씩 확인하면서 [s, e, k] 값을 가져온 다음,
3. s부터 e까지 arr[i]를 보면서 k보다 크면 최소값(minValue)을 갱신
   • 만약 minValue가 아직 없으면(nil), 그냥 현재 값 저장
   • minValue가 있으면 기존 값과 비교해서 더 작은 값 저장
4. 만약 minValue가 여전히 nil이면 -1을 결과에 추가하고, 값이 있으면 그 값을 추가
5. 마지막으로 result를 반환

 

4. 예제 테스트

• [0,4,2] → 2보다 큰 값 중 최소값 3
• [0,3,2] → 2보다 큰 값 중 최소값 4
• [0,2,2] → 2보다 큰 값 없음 → -1

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

print(solution(arr, queries)) // [3, 4, -1]

 

 

 

 

최적화 생각해볼 점

 

사실 arr을 미리 정렬해두면 k보다 큰 최소값을 빠르게 찾을 수 있지만,
문제에서 범위가 계속 달라지기 때문에 정렬해도 별 의미 없어.
결론적으로, 쿼리 하나씩 돌면서 찾는 방식이 제일 나은 것 같아. (˶˃ ᵕ ˂˶)