코딩 테스트/Level 2
[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기
컴닥
2022. 8. 21. 07:10
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/118667
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
파이썬
투 포인터와 구간합을 이용해 풀 수 있습니다.
더보기
문제를 처음 읽을 때 다음 부분에서 오해를 했습니다.
"한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다."
원소를 pop했으면
그 원소를 다른 큐에 바로 insert 해줘야 하기 때문에
이 과정을 작업 1회로 한다는 말이며,
문제의 표현이 맞는데 ....
제 생각의 흐름은 엉뚱한 곳으로...
간단하게 풀기 위해,
두 큐를 합쳐서 하나의 큐로 만들었으며,
대신 출발점(left, right)을 각각의 큐의 원 시작점(0, len(queue1))으로 설정했습니다.
구간합이 전체 원소의 1/2가 되면 성공입니다.
totals에 구간합을 저장했습니다.
포인터를 이동할 때마다 카운트를 하나씩 올려줬습니다.
def solution(queue1, queue2):
total = 0
totals = [0]
for each in queue1 + queue2:
total += each
totals.append(total)
goal = totals[-1] / 2
count, left, right = 0, 0, len(queue1)
while left <= right < len(totals):
if (total := totals[right] - totals[left]) < goal:
right += 1
count += 1
elif total > goal:
left += 1
count += 1
else:
return count
return -1테스트 1 〉 통과 (0.01ms, 10MB)
테스트 2 〉 통과 (0.00ms, 9.96MB)
테스트 3 〉 통과 (0.01ms, 9.94MB)
테스트 4 〉 통과 (0.01ms, 10.1MB)
테스트 5 〉 통과 (0.03ms, 10.1MB)
테스트 6 〉 통과 (0.04ms, 9.96MB)
테스트 7 〉 통과 (0.07ms, 10.2MB)
테스트 8 〉 통과 (0.15ms, 10.1MB)
테스트 9 〉 통과 (0.19ms, 10.2MB)
테스트 10 〉 통과 (0.48ms, 10.3MB)
테스트 11 〉 통과 (32.51ms, 18.7MB)
테스트 12 〉 통과 (14.79ms, 18.4MB)
테스트 13 〉 통과 (15.55ms, 17.4MB)
테스트 14 〉 통과 (16.89ms, 18.4MB)
테스트 15 〉 통과 (20.86ms, 25.4MB)
테스트 16 〉 통과 (22.29ms, 26.6MB)
테스트 17 〉 통과 (21.94ms, 25.9MB)
테스트 18 〉 통과 (60.94ms, 57.8MB)
테스트 19 〉 통과 (68.31ms, 67.9MB)
테스트 20 〉 통과 (92.29ms, 71MB)
테스트 21 〉 통과 (84.12ms, 71.6MB)
테스트 22 〉 통과 (126.45ms, 71.5MB)
테스트 23 〉 통과 (111.62ms, 72.1MB)
테스트 24 〉 통과 (135.14ms, 71.9MB)
테스트 25 〉 통과 (0.11ms, 10MB)
테스트 26 〉 통과 (0.04ms, 10.2MB)
테스트 27 〉 통과 (0.04ms, 10.1MB)
테스트 28 〉 통과 (66.78ms, 29MB)
테스트 29 〉 통과 (2.02ms, 11.5MB)
테스트 30 〉 통과 (75.06ms, 30MB)
for 문은 리스트 컴프리헨션을 이용해서 줄일 수 있습니다.
하지만, 초기값 0이 문제였습니다.
reduce 함수로 초기값을 지정할 수 있습니다.
하지만, 추가 모듈을 불러오는 건 보기 싫죠.
'리스트'와 '제너레이터 익스프레션'을 이용했습니다.
파이썬 3.8의 귀여운 '바다코끼리 연산자(:=)' 도 사용했고...
'애스터리스크(*) 연산자'로 '언패킹'도...
def solution(queue1, queue2):
total = 0
totals = [0, *(total := total + each for each in (*queue1, *queue2))]
goal = totals[-1] / 2
count, left, right = 0, 0, len(queue1)
while left <= right < len(totals):
if (total := totals[right] - totals[left]) < goal:
right += 1
count += 1
elif total > goal:
left += 1
count += 1
else:
return count
return -1테스트 1 〉 통과 (0.01ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.01ms, 10.3MB)
테스트 4 〉 통과 (0.01ms, 10.2MB)
테스트 5 〉 통과 (0.03ms, 10.2MB)
테스트 6 〉 통과 (0.04ms, 10.3MB)
테스트 7 〉 통과 (0.05ms, 10.3MB)
테스트 8 〉 통과 (0.08ms, 10.3MB)
테스트 9 〉 통과 (0.18ms, 10.2MB)
테스트 10 〉 통과 (0.41ms, 10.4MB)
테스트 11 〉 통과 (32.60ms, 18.3MB)
테스트 12 〉 통과 (14.02ms, 18.3MB)
테스트 13 〉 통과 (12.27ms, 17.8MB)
테스트 14 〉 통과 (14.11ms, 18.9MB)
테스트 15 〉 통과 (18.93ms, 24.8MB)
테스트 16 〉 통과 (17.22ms, 25.9MB)
테스트 17 〉 통과 (17.55ms, 25.1MB)
테스트 18 〉 통과 (61.84ms, 60.1MB)
테스트 19 〉 통과 (69.91ms, 68.9MB)
테스트 20 〉 통과 (92.55ms, 71.5MB)
테스트 21 〉 통과 (125.80ms, 71.7MB)
테스트 22 〉 통과 (127.28ms, 71.7MB)
테스트 23 〉 통과 (110.70ms, 72.1MB)
테스트 24 〉 통과 (133.11ms, 71.9MB)
테스트 25 〉 통과 (0.11ms, 10.2MB)
테스트 26 〉 통과 (0.04ms, 10MB)
테스트 27 〉 통과 (0.04ms, 10.2MB)
테스트 28 〉 통과 (67.09ms, 28.4MB)
테스트 29 〉 통과 (1.81ms, 11.8MB)
테스트 30 〉 통과 (75.88ms, 30.7MB)
itertools를 사용해 보았습니다.
전반적으로 더 빠르군요...
from itertools import chain, accumulate
def solution(queue1, queue2):
totals = tuple(accumulate(chain(queue1, queue2), initial=0))
goal = totals[-1] / 2
count, left, right = 0, 0, len(queue1)
while left <= right < len(totals):
if (total := totals[right] - totals[left]) < goal:
right += 1
count += 1
elif total > goal:
left += 1
count += 1
else:
return count
return -1테스트 1 〉 통과 (0.01ms, 10.3MB)
테스트 2 〉 통과 (0.01ms, 10.1MB)
테스트 3 〉 통과 (0.01ms, 10.3MB)
테스트 4 〉 통과 (0.01ms, 10.3MB)
테스트 5 〉 통과 (0.03ms, 10.2MB)
테스트 6 〉 통과 (0.03ms, 10.2MB)
테스트 7 〉 통과 (0.03ms, 10.2MB)
테스트 8 〉 통과 (0.07ms, 10.1MB)
테스트 9 〉 통과 (0.09ms, 10.3MB)
테스트 10 〉 통과 (0.22ms, 10.4MB)
테스트 11 〉 통과 (28.32ms, 18.2MB)
테스트 12 〉 통과 (9.90ms, 17.9MB)
테스트 13 〉 통과 (6.63ms, 16.6MB)
테스트 14 〉 통과 (7.79ms, 17.6MB)
테스트 15 〉 통과 (11.27ms, 24.5MB)
테스트 16 〉 통과 (9.95ms, 25.6MB)
테스트 17 〉 통과 (12.72ms, 24.7MB)
테스트 18 〉 통과 (28.72ms, 53.6MB)
테스트 19 〉 통과 (38.64ms, 63.8MB)
테스트 20 〉 통과 (59.07ms, 67MB)
테스트 21 〉 통과 (51.56ms, 67.8MB)
테스트 22 〉 통과 (93.35ms, 67.9MB)
테스트 23 〉 통과 (81.81ms, 71MB)
테스트 24 〉 통과 (105.14ms, 71.1MB)
테스트 25 〉 통과 (0.06ms, 10.1MB)
테스트 26 〉 통과 (0.04ms, 10.2MB)
테스트 27 〉 통과 (0.05ms, 10.2MB)
테스트 28 〉 통과 (57.72ms, 27.7MB)
테스트 29 〉 통과 (0.93ms, 11.6MB)
테스트 30 〉 통과 (69.56ms, 28.7MB)
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Stream;
class Solution {
public int solution(int[] queue1, int[] queue2) {
int count = 0, left = 0, right = queue1.length;
long goal, total = 0;
var totals = new ArrayList<Long>(1 + queue1.length + queue2.length);
totals.add(0L);
for (var each : Stream.concat(Arrays.stream(queue1).boxed(), Arrays.stream(queue2).boxed()).toArray(Integer[]::new)) {
total += each;
totals.add(total);
}
goal = totals.get(totals.size() - 1) / 2;
while (left <= right && right < totals.size()) {
total = totals.get(right) - totals.get(left);
if (total < goal) {
right++;
count++;
} else if (total > goal) {
left++;
count++;
} else {
return count;
}
}
return -1;
}
}import java.util.ArrayList;
class Solution {
public int solution(int[] queue1, int[] queue2) {
int count = 0, left = 0, right = queue1.length;
long goal, total = 0;
var queue = new int[queue1.length + queue2.length];
var totals = new ArrayList<Long>(1 + queue.length);
System.arraycopy(queue1, 0, queue, 0, queue1.length);
System.arraycopy(queue2, 0, queue, queue1.length, queue2.length);
totals.add(0L);
for (var each : queue) {
total += each;
totals.add(total);
}
goal = totals.get(totals.size() - 1) / 2;
while (left <= right && right < totals.size()) {
total = totals.get(right) - totals.get(left);
if (total < goal) {
right++;
count++;
} else if (total > goal) {
left++;
count++;
} else {
return count;
}
}
return -1;
}
}동빛나님의 설명이 좋아서 퍼왔습니다.
https://www.youtube.com/watch?v=rI8NRQsAS_s
반응형