프로그래머스 - 두 큐 합 같게 만들기

아래 문제는 프로그래머스에서 제공하는 두 큐 합 같게 만들기의 문제입니다🧑🏻‍💻

문제 제시

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

문제 풀이

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
  var totalQueue = queue1 + queue2
  var queue1Sum = queue1.reduce(0) { $0 + $1 }
  var middleSum = totalQueue.reduce(0) { $0 + $1 } / 2
  var leftOffset: Int = 0
  var rightOffset: Int = queue1.count
  var count: Int = 0
  
  if !(middleSum is Int) {
    return -1
  }
  
  while (leftOffset <= rightOffset && rightOffset < totalQueue.count) {
    if queue1Sum == middleSum {
      return count
    }
    if queue1Sum > middleSum {
      queue1Sum -= totalQueue[leftOffset]
      leftOffset += 1
    } else {
      queue1Sum += totalQueue[rightOffset]
      rightOffset += 1
    }
    count += 1
  }
  
  return -1
}

사용 개념

- reduce
- 타입 체크
- 반복 및 조건문

문제 후기

해당 문제는 2022 카카오 테크 인턴쉽 기출 문제로 난이도가 2정도 되는 어렵다고는 할 수 없지만 성능을 고려해야하는 문제였다.
각 두 큐의 길이는 항상 같으며 첫번째 인덱스의 값을 교환하며 계속 비교해나가면 되는줄 알았다.우선 두 큐의 합의 2로 나눈 값이 소수로 떨어지면 절대 같아질 수 없음으로 타입 체크를 해준다.그 다음 while 반복문을 통해 두 큐에서 큰 큐를 매번 파악하고 그 큐의 첫번째 값을 넘겨주며 계속 비교 판단해주었다.while 조건의 경우 처음에는 한 큐의 길이에 2배 되는 정도를 돌았을때는 모든 교환이 이루어졌다고 판단했고 그 수치를 조건으로 잡았다.그리고 popFirst를 아래와 같이 Array extension으로 구현하여주어 First 인덱스를 구하고 한 큐에서는 빼고 다른 큐에서는 더해줬다.

extension Array {
  mutating func popFirst() -> Element? {
    return self[self.indices].popFirst()
  }
}

array에는 popLast만 있고 popFirst가 없기에 해당 구현을 해주었다.
popFirst는 collection에 있기에 indices 인스턴스 프로퍼티를 가져와서 구현을 시켰다.
그런데 실행 결과에서 타임 아웃이 났다.
즉, popFirst하는 동작이 첫번째 요소를 빼오고 다시 모든 요소를 배치해야하니 시간 복잡도가 O(n)이 들 수 밖에 없었다.
그렇기에 이 시간을 줄이고자 위 코드 구현과 같이 두 큐를 합치고 left, right offset 기준점을 두었다.
left는 0번째부터 right는 2번째 큐의 시작점부터 기준점이 잡히도록 했다.
그리고 leftOffset이 rightOffset을 넘어간다면 모든 교환은 이뤄진거라 판단했고 rightOffset도 합쳐진 큐의 카운트를 넘어가면 모든 교환이 끝나 비교해볼 수 있는건 다해봤다는 조건을 두었다.
그 내부에서는 첫번째 큐의 합이 중간값보다 크면 값을 빼야하니 totalQueue에서의 leftOffset에 위치한 수를 구해 빼주고 leftOffset은 1 증가시키며 이동 시킨다.
반대로 중간값보다 적으면 값을 더해야하니 totalQueue에서의 rightOffset에 위치한 수를 구해 더해주고 rightOffest은 1 증가시키며 마찬가지로 이동 시킨다.
이렇게 한 사이클을 돌때 count는 1씩 증가시키고 처음 비교할때 중간값과 큐의 합이 같으면 최소 횟수를 구한것이니 return시킨다.
while문에서 빠져나왔을경우에는 만족시키는 값이 없기에 -1을 리턴시키며 해결할 수 있었다.

[참고 자료]

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

프로그래머스