프로그래머스 문제 1,2
두 큐 합 같게 만들기
길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다. 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다. 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.
입력: queue1 = [3, 2, 7, 2] queue2 = [4, 6, 5, 1]
출력: 2
내 풀이
def solution(queue1, queue2):
q1_sum = sum(queue1)
q2_sum = sum(queue2)
q1_sum_history = [queue1[:]]
q2_sum_history = [queue2[:]]
count = 0
while q1_sum != q2_sum:
if q1_sum > q2_sum:
queue2.append(queue1.pop(0))
else:
queue1.append(queue2.pop(0))
count += 1
q1_sum = sum(queue1)
q2_sum = sum(queue2)
if (queue1 in q1_sum_history) or (queue2 in q2_sum_history):
return -1
else:
q1_sum_history.append(queue1[:])
q2_sum_history.append(queue2[:])
return count
- queue1의 합을 구한 q1_sum와 queue2의 합을 구한 q2_sum을 비교해가며 합의 크기가 큰 리스트를 pop(0)하여 합의 크기가 작은 리스트에 append한다.
- 어떠한 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우를 찾기 위해 q1_sum_history와 q2_sum_history에 각각 queue1과 queue2를 append한다.
결과
정확성: 63.3
합계: 63.3 / 100.0
풀이 1
def solution(queue1, queue2):
answer = -1
a=sum(queue1)
b=sum(queue2)
s=(a+b)//2
i,j,t=0,0,len(queue1)
while i<2*t and j<2*t and a!=b:
if a<s:
a+=queue2[j]
b-=queue2[j]
queue1.append(queue2[j])
j+=1
else:
a-=queue1[i]
b+=queue1[i]
queue2.append(queue1[i])
i+=1
if a==s:
answer=i+j
return answer
- 해당 풀이는 q1_sum_history와 q2_sum_history와 같이 나온 큐를 저장하는 별도의 리스트가 없기 때문에 메모리 차지량에서 훨씬 더 효율적이다.
- 대신에 i와 j인 인덱스 변수를 설정하여서 두 개의 큐에 모든 값을 추가할때까지 큐의 합의 일치여부를 확인한다.
문자열 반복
데이터 처리 전문가가 되고 싶은 “어피치”는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 “aabbaccc”의 경우 “2a2ba3c”(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, “abcabcdede”와 같은 문자열은 전혀 압축되지 않습니다. “어피치”는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다. 예를 들어, “ababcdcdababcdcd”의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 “2ab2cd2ab2cd”로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 “2ababcdcd”로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다. 다른 예로, “abcabcdede”와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 “abcabc2de”가 되지만, 3개 단위로 자른다면 “2abcdede”가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다. 압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
입력: “ababcdcdababcdcd”
출력: 9
설명: 문자열을 ‘ababcdcd’로 8개 단위로 잘라 압축했을 때 가장 짧습니다.
내 풀이
def solution(s):
if len(s) == 1:
return 1
answer = []
# i는 윈도우 사이즈 -> 문자열 길이의 절반 만큼 반복함
for i in range(1, len(s)//2 + 1):
window = ''
n, j = 1, 0
prev_window = s[j:j+i]
shortened = ''
# 문자열을 반복하면서 shortened 변수에 줄인 문자를 더해나감
while j <= len(s):
j += i
window = s[j:j+i]
if window == prev_window:
n += 1
if window != prev_window:
if n > 1:
shortened = shortened + str(n) + prev_window
n = 1
else:
shortened += prev_window
prev_window = window
answer.append(len(shortened))
return min(answer)
- 첫번째 반복문에서 i는 윈도우 사이즈이다.
- 두번째 반복문에서 문자열을 반복하며 문자열을 압축해 나간다.
- 압축한 문자열의 길이를 answer에 저장하고 그 중 가장 작은 값을 리턴한다.
결과
정확성: 100
합계: 100 / 100.0
Comments