일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 개념
- Gold4
- glod4
- error
- jpa
- PYTHON
- 백준
- leetcode 69
- AWS
- mysql
- java
- LEVEL1
- LCS
- 배포
- Kakao
- gold5
- 오류
- 프로그래머스
- Thymeleaf
- HTML
- CSS
- siver3
- 9252
- gold2
- spring
- 백엔드
- 구현
- leetcode
- glod5
- LEVEL2
- Today
- Total
이 험난한 세상에서어어~
[KAKAO, python] 두 큐 합 같게 만들기 본문
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=python3
말 그대로 두 큐의 합을 같게 만드는 것이다.
문제를 처음 봤을 때는 완탐으로 푸나 싶었지만, 제한 사항에서도 알 수 있듯이 완탐으로 풀면 시간 초과 난다.
그리고 완탐으로 푸는 방법도 생각이 잘... 나지 않는다.
사실 문제를 단순하게 접근하면 어느 정도는 푸는 문제다. 하지만, 같게 만들 수 없을 때 '-1'을 반환하는 것과 파이썬으로 풀 경우 자료구조의 시간 초과 고려를 해줘야 한다.
문제 풀이
첫 번째 예시로 설명을 해보자면 일단 두 큐의 합을 각각 구해보자.
그럼 첫 큐의 합은 14이고 두 번째 큐의 합은 16이다.
여기서 중요한 건 위의 값들을 큐로 고려해줘야 한다는 것이다. 그러므로 합이 큰 두 번째 큐에서 첫 원소를 꺼내서 첫 번째 큐에 넣어준다.
그러면 첫 큐의 합은 18이 되고 두 번째 큐의 합은 12가 된다.
그러면 합이 더 큰 첫 큐에서 첫 번째 원소를 꺼내 두 번째 원소에 넣어주자.
그러면 합은 첫 큐가 15이고 두 번째 큐가 15가 되서 같아진다.
그러므로 최소 이동 수는 2가 된다.
위의 설명대로 풀면 되는데, 중요한 건 바로 합을 같게 만들 수 없는 경우이다.
예를 들어서 [1, 1]과 [1, 2]가 있다고 해보자.
그러면 1이 자꾸만 왔다갔다 해서 답은 안 나오고 시간 초과만 될 것이다.
그러므로 count의 한계를 큐들의 최대 길이인 300,000으로 잡아서 시간 초과를 막아야 한다.
또한 파이썬으로 풀 경우 큐의 자료 구조를 deque()로 해줘야 한다.
나는 처음에 그냥 list에다가 .pop(0)을 했는데, list를 쓰면 값을 뺄 때마다 O(n)만큼의 시간이 걸린다. 그러므로 큐로 값을 뺄 때 O(1)의 시간 복잡도를 가지는 deque()를 사용해줘야 한다!
여담이지만 투 포인터로도 풀 수 있을 거 같다.
코드
from collections import deque
def make_target(sum1, sum2, queue1, queue2):
count = 0
q1 = deque(queue1)
q2 = deque(queue2)
while sum1 != sum2:
if count == 300000:
count = -1
break
#print(f'{sum1} {sum2}')
if sum1 > sum2:
tmp = q1.popleft()
q2.append(tmp)
sum1 -= tmp
sum2 += tmp
elif sum1 < sum2:
tmp = q2.popleft()
q1.append(tmp)
sum2 -= tmp
sum1 += tmp
count += 1
return count
def solution(queue1, queue2):
answer = -2
sum1 = sum(queue1)
sum2 = sum(queue2)
sum_all = (sum1+sum2)
if sum_all%2 != 0:
return -1
return make_target(sum1, sum2, queue1, queue2)