코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다. 예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.
- 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
- 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항 1. clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 2. 코니가 가진 의상의 수는 1개 이상 30개 이하입니다. 3. 같은 이름을 가진 의상은 존재하지 않습니다. 4. clothes의 모든 원소는 문자열로 이루어져 있습니다. 5. 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
조합을 생각하고 combinations를 사용한다면 시간 초과가 나오게 되는 문제였습니다. 모든 조합을 고려해 원하는 조건을 추려내는 방법은 효율적이지 못하고 다른 방법을 사용해야 하는데, 각 의상의 종류별로 독립적인 사건을 곱하여 모든 가능한 조합의 수를 구하는 통계적 사고가 필요했습니다. 문제 해결 과정을 설명하면 다음과 같이 간단하게 진행됩니다.
의상 종류별로 그룹화하여 몇 개의 의상이 있는지 계산합니다.
각 종류별로 의상을 선택하지 않는 경우까지 포함하여 num + 1 을 곱합니다.
최종 결과에서 아무것도 입지 않는 경우의 수를 제외한 1을 빼고 남은 수를 반환합니다.
다음은 조합의 곱셈을 사용한 풀이를 진행하면서 효율적인 python 구현 방식을 적용한 순서입니다.
딕셔너리 초기화를 위한 반복문과 생성된 딕셔너리에 값을 더하는 반복문을 따로 만들어 구현했습니다.
for value in clothes:
categories[value[1]] = 0
for value in clothes:
categories[value[1]] += 1
위 코드처럼 반복되는 코드를 해결하기위해 조건문을 추가하여 하나의 반복문에 넣어보았습니다.
for value in clothes:
if value[1] not in categories:
categories[value[1]] = 0
categories[value[1]] += 1
두 번째 인덱스가 의상의 종류이므로 해당 Key 값의 존재 유무에 따라 조건문에서 Value 를 초기화 해주었습니다. 하지만 defaultdict를 사용하여 위와 같은 초기화 문제를 간결하게 해결할 수 있었습니다. defaultdict를 통해 int 로 default 초기화 된 의상 종류 딕셔너리를 생성해주니 다음과 같이 간결하게 코드가 구성되었습니다.
categories = defaultdict(int)
# 각 의상 종류별로 개수 세기
for value in clothes:
categories[value[1]] += 1
결국 defaultdict로 생성된 딕셔너리가 초기화가 필요한 부분에서 효율적인 구현이 가능하다는 것을 알 수 있습니다.
💡 내가 해결한 방식은?
combination을 사용한 풀이 (시간 초과)
from itertools import combinations
from collections import defaultdict
def solution(clothes):
# 의상 종류별로 그룹화
clothes_by_category = defaultdict(list)
for name, category in clothes:
clothes_by_category[category].append(name)
all_combinations = []
# 각 의상 종류별로 0개부터 1개까지 선택하는 조합 생성
for category, items in clothes_by_category.items():
for r in range(1, len(items) + 1):
for comb in combinations(items, r):
all_combinations.append(comb)
# 모든 조합을 카테고리별로 결합
valid_combinations = []
for r in range(1, len(clothes_by_category) + 1):
for comb in combinations(clothes_by_category.values(), r):
combined_combinations = [[]]
for item_list in comb:
combined_combinations = [prev + [item] for prev in combined_combinations for item in item_list]
valid_combinations.extend(combined_combinations)
return len(valid_combinations)
의상 종류 별 조합의 곱셈을 이용한 풀이
# from collections import defaultdict
def solution(clothes):
answer = 1
# categories = {}
categories = defaultdict(int)
# for value in clothes:
# categories[value[1]] = 0
# for value in clothes:
# categories[value[1]] += 1
# 의상 카테고리 딕셔너리에 저장
# for value in clothes:
# if value[1] not in categories:
# categories[value[1]] = 0
# categories[value[1]] += 1
# 각 의상 종류별로 개수 세기
for value in clothes:
categories[value[1]] += 1
# 조합의 곱셈
for num in categories.values():
answer *= (num + 1)
# 아무것도 입지 않는 경우 제외한 후 반환
return answer - 1
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다. 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다. 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.
제한 사항 1. priorities의 길이는 1 이상 100 이하입니다. 1-1. priorities의 원소는 1 이상 9 이하의 정수입니다. 1-2. priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다. 2. location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다. 2-1. priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.
