[Algorithm]Programmers_KAKAO_118667_두 큐 합 같게 만들기_Go

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/118667

풀기 전 생각

1. 큐를 둥글게 이어 붙이면 링(Ring) 형태가 된다.

2. 투포인터를 사용하여 타겟 넘버를 찾는다.

∵ 큐는 Pop과 Push를 이용해 연속된 데이터 처리만을 할 수 있기에 투포인터를 사용해도 된다 판단.

3. 시나리오를 분리하여 큐를 만드는데 필요한 수행 횟수 계산.

시나리오

1. 시작 포인터와 끝 포인터가 같은 큐에 있다.

    i) 끝 포인터가 큐의 마지막 인덱스 값이다.

    ii) 끝 포인터가 큐의 마지막 인덱스 값이 아니다.

2. 시작 포인터와 끝 포인터가 다른 큐에 있다.

 

사용 자료구조

tmpq  []int  -  링 형태를 직접 구현하기보다 1번 큐, 2번 큐, 1번 큐를 이어 붙여 링 형태로 사용.

코드

package main

import (
    "fmt"
    "math"
)

func main() {
    fmt.Println(solution([]int{1, 3}, []int{1, 5, 2, 2}))
}

var min = math.MaxInt
var qSize int

func solution(queue1 []int, queue2 []int) int {
    qSize = len(queue1)
    tmpq := append(queue1, queue2...)
    var total, target int
    for _, v := range tmpq {
        total += v
    }
    target = total / 2
    tmpq = append(tmpq, queue1...)
    findTarget(tmpq, target)
    if min == math.MaxInt {
        min = -1
    }
    return min
}

func findTarget(q []int, target int) {
    var start, end int
    val := q[start]
    for {
        if val == target {
            cal(start, end)
            end++
            if end == len(q) {
                return
            }

            val += q[end]
        } else if val > target {
            val -= q[start]
            start++
        } else {
            end++
            if end == len(q) {
                return
            }

            val += q[end]
        }

    }
}

func cal(start, end int) {
    startGroup, startGroupStartIndex := findGroup(start)
    endGroup, endGroupStartIndex := findGroup(end)
    if startGroup == endGroup {
        if end == qSize-1 || end == qSize*2-1 {
            if min > start-startGroupStartIndex {
                min = start - startGroupStartIndex
            }
        } else {
            switch startGroup {
            case 0:
                if min > qSize+(start-startGroupStartIndex)*2+end-start+1 {
                    min = qSize + (start-startGroupStartIndex)*2 + start - end + 1
                }
            case 1:
                if min > qSize+(start-startGroupStartIndex)*2+end-start+1 {
                    min = qSize + (start-startGroupStartIndex)*2 + start - end + 1
                }
            default:
                return
            }
        }
    } else {
        if startGroup == 0 && endGroup == 2 {
            return
        }
        if min > start-startGroupStartIndex+end-endGroupStartIndex+1 {
            min = start - startGroupStartIndex + end - endGroupStartIndex + 1
        }
    }
}

func findGroup(val int) (int, int) {
    if val < qSize {
        return 0, 0
    } else if val < qSize*2 {
        return 1, qSize
    } else {
        return 2, qSize * 2
    }
}