https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=python3
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.
다음은 두 큐를 나타내는 예시입니다.
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.
queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.
제한사항
1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
1 ≤ queue1의 원소, queue2의 원소 ≤ 109
주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.
아이디어를 떠올리는데 시간이 상당히 오래 걸렸다. 전체 합을 구할 필요 없이 한쪽 큐의 합이 전체 합의 절반이 되면 된다. 전체 합이 홀수라면 항상 -1을 반환한다 등... 파편적인 아이디어는 떠올랐지만 문제를 해결 할 수 있을 정도가 아니었다.
검색을 활용해서 각 큐의 원소들을 실제로 다른 큐로 이동시킬 필요 없이 두 큐를 연결해서 부분합이 15가 되는 경우를 찾으면 된다는 것을 알아냈다. 두 큐간의 원소의 이동이 첫번째칸에서 제거되고 마지막칸에 추가된다는 것을 활용한 것이었다.
def solution(queue1, queue2):
total_sum = sum(queue1) + sum(queue2)
if total_sum % 2 != 0:
return -1
가장 먼저 두 큐의 원소의 합으로 총 합계를 구했다. 목표 큐의 합계가 총 합계의 절반이기 때문이고 하술할 예외처리를 위한 것이다.
총합계가 홀수일 경우 조건을 만족하는것이 불가능하기 때문에 즉시 -1을 반환한다.
answer = 0
target_sum = total_sum // 2
combined_queue = queue1 + queue2
len_queue = len(queue1)
right = len_queue - 1
current_sum = sum(queue1)
다음으로 사용할 변수들을 선언한다.
answer: 작업횟수를 기록한다.
target_sum: 목표 숫자, 현재 큐의 합계가 총 합계의 절반이 되는 지점을 찾아내기 위함이다.
combined_queue: 두 큐를 결합한 큐, 큐의 입력과 출력이 각각 맨뒤와 맨 앞에서만 일어나기 때문에 두 큐를 연결해서 슬라이싱하는 방법으로 현재 큐의 합계를 구할 수 있다.
len_queue: 시작 큐의 길이를 나타낸다.
right: 현재 큐의 범위를 나타낸다. combined_queue에서 현재 큐의 범위(combined_queue[0:3] = queue1)을 슬라이싱하기 위해 queue1의 길이에서 1을 뺀 값을 지정한다.
current_sum: 현재 큐의 합계를 나타낸다. 매 반복마다 sum(combined_queue[0:right]))를 사용한다면 연산량이 너무 많이 늘어나기 때문에 합계는 다른 변수에 따로 저장을 한다.
while right < len(combined_queue) - 1 :
if current_sum == target_sum:
return answer
elif current_sum < target_sum:
right += 1
if right < len(combined_queue):
current_sum += combined_queue[right]
answer += 1
elif current_sum > target_sum:
right -= 1
current_sum -= combined_queue[0]
combined_queue.append(combined_queue[0])
combined_queue.pop(0)
answer += 1
return -1
그리고 반복문을 이용하여 combined_queue를 슬라이싱한다. right의 값이 combined_queue의 길이가 될 경우, 모든 경우를 순회해도 목표값을 달성할 수 없기때문에 반복문을 종료하고 -1값을 반환한다.
current_sum == target_sum인 경우 목표값을 달성했으므로 반복문의 실행을 종료하고 지금까지의 작업횟수인 answer를 반환한다.
current_sum < target_sum인 경우 현재 값이 목표값보다 작기때문에 right를 증가시켜서 현재 큐의 범위를 넓힌다. 동시에 현재 큐의 합계인 current_sum의 값도 넓힌 범위만큼 업데이트하고 작업횟수를 증가시킨다.
current_sum > target_sum인 경우 현재 값이 목표값보다 크기때문에 right를 감소시켜서 현재 큐의 범위를 좁힌다. 동시에 combined_queue에서 가장 앞에 있는 값을 combined_queue의 가장 뒤로 이동시킨다. (나중에 다시 더해질 수도 있으므로) 그리고 작업횟수를 증가시킨다.
이상의 과정을 반복해서 목표값에 도달했을 경우 작업횟수를, 도달하지 못했을경우 -1을 반환하도록 작성을했다.
def solution(queue1, queue2):
total_sum = sum(queue1) + sum(queue2)
if total_sum % 2 != 0:
return -1
answer = 0
target_sum = total_sum // 2
combined_queue = queue1 + queue2
right = len(queue1) - 1
current_sum = sum(queue1)
while right < len(combined_queue) - 1 :
if current_sum == target_sum:
return answer
elif current_sum < target_sum:
right += 1
if right < len(combined_queue):
current_sum += combined_queue[right]
answer += 1
elif current_sum > target_sum:
right -= 1
current_sum -= combined_queue[0]
combined_queue.append(combined_queue[0])
combined_queue.pop(0)
answer += 1
return -1
결과는 시간초과였다. 어떻게 보면 당연했다. 리스트의 값을 반복적으로 업데이트하는 것이 연산량을 상당히 소모하기 때문이다. 때문에 지난번과 마찬가지로 자료형을 deque로 수정해주었다.
from collections import deque
def solution(queue1, queue2):
total_sum = sum(queue1) + sum(queue2)
if total_sum % 2 != 0:
return -1
answer = 0
target_sum = total_sum // 2
combined_queue = deque(queue1 + queue2)
right = len(queue1) - 1
current_sum = sum(queue1)
while right < len(combined_queue) - 1 :
if current_sum == target_sum:
return answer
elif current_sum < target_sum:
right += 1
if right < len(combined_queue):
current_sum += combined_queue[right]
answer += 1
elif current_sum > target_sum:
right -= 1
current_sum -= combined_queue[0]
combined_queue.append(combined_queue[0])
combined_queue.popleft()
answer += 1
return -1
하지만 시간초과가 다시 한번 발생했다. 이전보다는 확실히 빨라졌지만 아직 더 개선할 필요가 있었다.
문제가 되는 부분은 당연히 이 부분일 것이다.
elif current_sum > target_sum:
right -= 1
current_sum -= combined_queue[0]
combined_queue.append(combined_queue[0])
combined_queue.popleft()
answer += 1
반복을 실행할때마다 현재 큐의 값을 뒤로 옮기고 새로 추가하는 과정을 반복하고 있기 때문이다. 문제를 해결하기 위해서 현재 큐의 범위를 0:right로 한정하지 않고 시작 큐의 범위도 설정해서 left:right로 바꿔주기로 했다. 그렇게 한다면 combined_queue의 값을 직접적으로 조작할 필요가 사라질것이다.
answer = 0
target_sum = total_sum // 2
combined_queue = queue1 + queue2 + queue1
len_queue = len(queue1)
left = 0
right = len_queue - 1
current_sum = sum(queue1)
left를 추가하기 위해서 변수를 수정했다. 달라진 부분만 설명하면 다음과 같다.
combined_queue: 큐의 맨 앞의 값을 맨 뒤로 옮기는 과정을 생략하기 위해서 queue1 전체를 뒤에 덧붙였다.
while right < len_queue * 2 - 1 :
if current_sum == target_sum:
return answer
elif current_sum < target_sum:
right += 1
if right < len_queue * 2:
current_sum += combined_queue[right]
answer += 1
elif current_sum > target_sum:
current_sum -= combined_queue[left]
left += 1
answer += 1
바뀐 변수에 따라서 반복문의 조건도 수정해주었다. combined_queue의 길이가 더 길어졌기때문에 반복문의 종료조건을 len(queue)의 두배가 될때로 변경해주었고 current_sum > target_sum일때는 left의 값을 증가시켜서 현재 큐의 범위를 좁히도록 했다.
def solution(queue1, queue2):
total_sum = sum(queue1) + sum(queue2)
if total_sum % 2 != 0:
return -1
answer = 0
target_sum = total_sum // 2
combined_queue = queue1 + queue2 + queue1
len_queue = len(queue1)
left = 0
right = len_queue - 1
current_sum = sum(queue1)
while right < len_queue * 2 - 1 :
if current_sum == target_sum:
return answer
elif current_sum < target_sum:
right += 1
if right < len_queue * 2:
current_sum += combined_queue[right]
answer += 1
elif current_sum > target_sum:
current_sum -= combined_queue[left]
left += 1
answer += 1
return -1
드디어 성공! 예상대로 combined_queue를 직접 조작하는 코드가 연산량이 과도하게 많았던것같다.
'코딩일기' 카테고리의 다른 글
| 알고리즘 코드카타 111 - 무인도 여행 (0) | 2024.07.08 |
|---|---|
| SQL 코드카타 110 - Product Price at a Given Date (0) | 2024.07.07 |
| 알고리즘 코트카타 - 26 ~ 30 (자바스크립트) (0) | 2024.07.06 |
| SQL 코드카타 109 - Consecutive Numbers (0) | 2024.07.06 |
| 알고리즘 코드카타 109 - 연속된 부분 수열의 합 (0) | 2024.07.06 |
