BOJ.20529

#BOJ20529

틀림

우선 이 문제를 보자마자 풀이방법이 생각은 났지만 분명 99퍼센트의 확률로 틀렸습니다가 나올만한 풀이였다. 그래도 복습한다는 생각으로 combination을 활용하는 코드를 짜보았다.

import sys
from itertools import combinations

T = int(sys.stdin.readline())
for _ in range(T):
   N = int(sys.stdin.readline())
   arr = list(map(str, sys.stdin.readline().split()))
   new_arr = combinations(arr, 3)
   ans = 0
   for i in new_arr:
       set1 = set(i[0])
       set2 = set(i[1])
       set3 = set(i[2])
       ans = max(ans, len(set1.intersection(set2)) + len(set2.intersection(set3)) + len(set3.intersection(set1)))
   print(12 - ans)

딱 보면 아시겠지만 시간 초과 나게 생긴 코드다. 그래도 뭔가 그냥 넘어가긴 아쉬우니 간단하게 combinations랑 set에 대해서 정리해보았다.
물론입니다, "문체를 보여준다"의 형식에 맞추어서 앞서 언급한 내용을 수정해 보겠습니다.

Python의 itertools.combinations 함수

주요 기능

• 조합 생성: 이 함수는 반복 가능한 객체로부터 지정된 개수의 항목을 조합하여 보여준다. combinations(iterable, r)는 iterable에서 r 개의 항목을 선택하여 조합을 생성한다.
• 순서 무시: 생성된 조합에서는 항목의 순서가 고려되지 않는다. 예를 들어, ('A', 'B')와 ('B', 'A')는 같은 조합으로 간주된다.
• 중복 없음: 동일한 항목을 여러 번 포함하는 조합은 생성되지 않는다.
• 반복자 반환: 조합의 반복자(iterator)를 반환하는 이 함수는 메모리를 절약하며, 필요에 따라 조합을 순차적으로 생성한다.

활용 예시

예시 1: 숫자 조합 생성

from itertools import combinations

numbers = [1, 2, 3, 4]
for combo in combinations(numbers, 2):
    print(combo)

이 코드는 [1, 2, 3, 4] 리스트에서 2개를 선택하는 모든 조합을 보여준다.

예시 2: 문자열에서 문자 조합 생성

from itertools import combinations

string = "ABCD"
for combo in combinations(string, 3):
    print(''.join(combo))

이 코드는 "ABCD" 문자열에서 3개의 문자로 이루어진 조합을 보여준다.

Python의 set() 함수

주요 기능

• 유일한 요소의 집합 생성: set() 함수는 반복 가능한 객체로부터 중복을 제거한 요소들의 집합을 생성한다. 예를 들어, 리스트나 문자열에서 중복된 요소를 제거하고 유일한 요소만 남기는 데 사용된다.
• 수학적 집합 연산 지원: set()을 통해 생성된 집합은 교집합, 합집합, 차집합, 대칭 차집합과 같은 기본적인 수학적 집합 연산을 지원한다.
• 가변성: 생성된 집합은 가변적이며, 이후에 요소를 추가하거나 제거할 수 있다.
• 순서 없음: 집합은 순서를 갖지 않는다. 따라서 집합 내의 요소들은 임의의 순서로 저장되고 접근된다.

활용 예시

예시 1: 중복 요소 제거

my_list = [1, 2, 2, 3, 4, 4, 4, 5]
unique_elements = set(my_list)
print(unique_elements)

이 코드는 리스트 my_list에서 중복된 요소를 제거하여 유일한 요소만 남기는 집합을 보여준다.

예시 2: 집합 연산

set1 = set([1, 2, 3])
set2 = set([2, 3, 4])

# 교집합
print(set1.intersection(set2))

# 합집합
print(set1.union(set2))

# 차집합
print(set1.difference(set2))

이 코드는 두 집합 사이의 교집합, 합집합, 차집합 연산을 보여준다.

예시 3: 요소 추가 및 제거

my_set = set([1, 2, 3])
my_set.add(4)     # 요소 추가
print(my_set)
my_set.remove(2)  # 요소 제거
print(my_set)

이 코드는 집합에 요소를 추가하거나 제거하는 방법을 보여준다.

본 문제 풀이

문항을 보다보니 MBTI의 종류가 16개 밖에 안되니 비둘기집의 원리에 의해 MBTI가 32개 이상인 경우에만 0을 출력해주면 문제가 사라지겠다는 생각이 들었다. 비둘기집의 원리에 대한 설명은 생략하겠습니다. 아래는 코드입니당.

import sys
from itertools import combinations

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    arr = list(map(str, sys.stdin.readline().split()))
    new_arr = combinations(arr, 3)
    ans = 0
    if N > 32:
        print(0)
        continue
    for i in new_arr:
        set1 = set(i[0])
        set2 = set(i[1])
        set3 = set(i[2])
        ans = max(ans, len(set1.intersection(set2)) + len(set2.intersection(set3)) + len(set3.intersection(set1)))
    print(12 - ans)