3월 13일 TIL (투포인터)

프로그래머스 코딩테스트 [ 연속된 부분 수열의 합 ]

Gihub 링크

• 이 문제는 주어진 숫자 배열에서 제일 적은 연속된 부분 수열의 합이 k가 되는 인덱스를 찾는 문제이다.
• 시간제한이 없더라면 for 문 두개로 돌면 되곘지만, 배열의 최대 길이가 1,000,000이다. 즉 시간초과를 고려를 꼭 해야한다는 문제라는 것이다.
• 처음에는 for 문으로 돌려서 break만 잘하면 시간초과가 안되지 않을까 생각을 했는데, 결국 시간초과의 벽에 막히고 말았다.
• 인터넷을 찾아보니 투포인터 개념이 있었다.
• 단어 그대로 포인터를 두개를 사용하는것인데, 차이점은 지금까지의 합을 리셋하고 새로 계산하는것이 아니라, 합을 유지한 상태로 사용하는 것이다.
• 아래 다이어그램 처럼 두개의 포인터를 사용해서 pointer2만 증가 시키면서 지금까지의 합을 유지한다. 만약 pointer2가 움직이면서 sum이 k보다 커지면 pointer1이 가리키고 있는 element를 sum에서 빼버린다. 그리고 pointer1를 1 증가 시킨다. 이렇게 하면 pointer1이 바뀔때마다 pointer2를 새롭게 출발해서 sum을 찾을 필요가 없고, 이미 한번 찾은 sum을 통해 게속 이어 나갈 수 있다.

---

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var indexRecord : [[Int]] = []
    var point1 = 0
    var point2 = 0
    var sum = sequence[0]
    
    while(point1 < sequence.count && point2 < sequence.count){
        if sum == k {
            indexRecord.append([point1,point2])
        }
        
        if sum < k {
            point2 += 1
            if point2 == sequence.count{break}
            sum += sequence[point2]
        }else{
            sum -= sequence[point1]
            point1 += 1
        }
    }
    indexRecord = indexRecord.sorted(by: {
        if $0[1] - $0[0] >= $1[1] - $1[0]{
            return $0[0] < $1[0]
        } else{
            return $0[0] > $1[0]
        }
    })
    
    return indexRecord[0]
}

---

프로그래머스 코딩테스트 [ 두 큐 합 같게 만들기 ]

Gihub 링크

• 이 문제도 위 문제와 똑같이 투 포인터를 사용하는 문제다.
• 주어진 두 큐의 각자의 합이 같게끔 enqueue, dequeue를 사용횟수를 출력하는 문제다.
• 당연히 처음에는 역시나 큐를 만들어야하나 했지만, 그렇지 않아도 됐었다.
• 두개의 큐를 하나의 배열로 합치고, 포인터로 추적을 하면 된다는 것이다.
• 또 하나는 굳이 두개의 큐의 합을 각각 확인할 필요 없이, 하나의 큐가 만약 전체합의 50%가 된다면, 나머지 하나도 무조건 50%이니깐, 하나만 확인하면 된다.

• 위에 그래프 처럼 작동한다.

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var indexRecord : [[Int]] = []
    var point1 = 0
    var point2 = 0
    var sum = sequence[0]
    
    while(point1 < sequence.count && point2 < sequence.count){
        if sum == k {
            indexRecord.append([point1,point2])
        }
        
        if sum < k {
            point2 += 1
            if point2 == sequence.count{break}
            sum += sequence[point2]
        }else{
            sum -= sequence[point1]
            point1 += 1
        }
    }
    indexRecord = indexRecord.sorted(by: {
        if $0[1] - $0[0] >= $1[1] - $1[0]{
            return $0[0] < $1[0]
        } else{
            return $0[0] > $1[0]
        }
    })
    
    return indexRecord[0]
}