문제 1
배열에 원소를 추가하는 작업을 하는데, 원소를 추가했을 때 기존 배열의 크기가 원소의 수보다 작으면 모든 원소를 담을 수 있는 새로운 배열의 크기(단, 원소의 수 이상인 2의 거듭제곱 중에서 최솟값)인 배열을 만들고 이 새로운 배열에 기존 배열의 모든 원소를 복사한 후 새로운 원소를 추가해줄거야.
반대로, 원소를 추가하더랄도 원소의 수가 배열의 크기보다 작거나 같다면, 기존 배열에 원소를 추가할거야.
처음 모든 배열의 크기는 0이야. 단, 기존 배열에 원소가 없을 경우에는 복사가 일어나지 않는 조건을 넣어야해. 배열 번호는 바뀌지 않아.
예를 들어 입력값에 [[2,10],[7,1],[2,5],[2,9],[7,32]] 를 넣어주면 리스트 리스트의 0번 인덱스들이 배열 번호가 되고, 1번 인덱스는 추가할 원소의 수를 의미해.
원하는 출력값은 위의 쿼리 과정을 수행했을 때 복사된 원소의 개수를 구하는거야.
Tipe Hinting
from typing import List, Dict
def min_power_of_two(n: int) -> int:
"""주어진 수 이상인 2의 거듭제곱 중에서 최솟값을 반환합니다."""
size = 1
while size < n:
size *= 2
return size
def count_copy_operations(queries: List[List[int]]) -> int:
# 배열 번호별로 독립적인 배열 상태를 저장할 딕셔너리
arrays: Dict[int, Dict[str, int]] = {}
copy_operations = 0 # 총 복사 횟수
for query in queries:
array_id, element_count = query
# 해당 배열 번호가 처음 등장하는 경우 초기화
if array_id not in arrays:
arrays[array_id] = {
"size": 0, # 현재 배열 크기
"elements": 0 # 현재 원소 수
}
# 현재 배열 상태 가져오기
array_info = arrays[array_id]
total_elements = array_info["elements"] + element_count
# 배열 크기가 추가할 원소 수를 수용할 수 없는 경우
if total_elements > array_info["size"]:
# 새로운 배열의 크기를 원소 수 이상인 2의 거듭제곱 중 최솟값으로 설정
new_size = min_power_of_two(total_elements)
# 기존 배열에 원소가 있을 때만 복사 작업을 수행
if array_info["elements"] > 0:
copy_operations += array_info["elements"]
# 배열 크기와 원소 수 갱신
array_info["size"] = new_size
array_info["elements"] = total_elements
else:
# 배열 크기 내에서 원소 추가가 가능한 경우
array_info["elements"] = total_elements
return copy_operations
# 사용 예시
queries = [[2, 10], [7, 1], [2, 5], [2, 9], [7, 32]]
result = count_copy_operations(queries)
result
Python
복사
문제 2
손님 n명이 일렬로 자리 1,...n 에 앉았다.
각 자리에는 젓가락이 두개씩 놓여있고, 젓가락의 종류는 A,B,C,D 네가지다.
각 자리에 놓인 두 젓가락의 종류가 같을 때 젓가락 짝이 맞다고 표현하는데,
몇몇 자리는 젓가락 짝이 맞지 않는다. 손님들은 자신과 인접한 자리에 앉은 손님과 젓가락을 한개씩 교환해 모든 자리의 젓가락 짝이 맞도록 하려고 한다. 이때, 젓가락 교환하는 최소 횟수를 출력하자.
입력값은 정수 n과 각 자리의 젓가락 초기 배치를 담은 1차원 문자열 배열 chopsticks가 매개변수로 주어진다.
예 : n= 4, chopsticks = ['BC','DB','AA','CD'] → 결과 : 4
Python
복사