글 읽기 - python combinations 사용 시 유의사항 알려드립니다.

wjdals485 1년 전 3

저는 python의 combinations 함수를 사용하여 이 문제를 해결하였는데요,

이상하게 50%에서 계속 틀려서, 원인을 찾다가 발견한 사실이 있어서 공유해드립니다.

combinations 함수는 인자값으로 두 개의 변수를 받습니다.

1. iterator : 조합을 만들 대상들

2. r : 몇 개의 요소를 가지고 있는 조합인지, 그 수

이때, iterator의 길이보다 r이 더 클 경우 combinations 함수는 iterator되지 않는 객체를 반환합니다.

즉, 위 경우에서 반환 받은 객체는 for문에서 동작하지 않고 그냥 넘어가 버립니다. 왜냐하면 반복할 대상이 없기 때문입니다.

이것 때문에 한참을 해메다가 드디어 해결했네요ㅠ

다른 분들 코드보다 생각없이 따라했는데, 해당 함수에 대한 이해없이 따라하다보니 이런일이 발생하는 것 같네유

from itertools import combinations


def solution():
    global n, k, words, allSet
    
    if k < 5:
        return 0
    k -= 5
    alphas = set(['a','c','n','t','i'])

    remain_alphas = allSet - alphas
    
    ##################################################################
    # 이 부분에서 개수를 확인하지 않으시면 밑에 combinations 함수에서
    # 반복하지 않는 객체를 반환 시 문제가 발생합니다.
    if len(remain_alphas) <= k:
        return n

    ##################################################################
    
    # 비트 연산을 위한 딕셔너리 생성
    bit_dict = {}
    for alpha in remain_alphas:
        bit_dict[alpha] = len(bit_dict) 

    # 문자 set을 비트로 변환
    for i in range(len(words)):
        word = words[i] - alphas
        bit_word = 0b0
        for item in word:
            num = bit_dict[item]
            bit_word = bit_word | (1 << num)
        words[i] = bit_word


    # 가능한 모든 조합
    candidates = combinations(remain_alphas,k)
    
    ans = 0
    for candidate in candidates:
        cnt = 0
        candidate = set(candidate)
        bit_caditate = 0b0
        for item in candidate:
            num = bit_dict[item]
            bit_caditate = bit_caditate | (1 << num)

        for word in words:
            if word == bit_caditate & word :
                cnt += 1
        if cnt > ans:
            ans = cnt
    return ans


if __name__ == "__main__":
    n, k = map(int,input().split())
    words = []
    allSet = set({})
    for i in range(n):
        word = set(list(input()))
        words.append(word)
        allSet |= word

    print(solution())

yopark 1년 전 1

덕분에 무한 디버깅 없이 빠른 시간내에 풀었습니다. 감사합니다.

seogudwns12 1년 전 1

감사합니다!!! combination의 함정을 깜박하고 이왜틀? 하고 있었다가 보고 고쳤네요 ㅎㅎ

bh2980 1년 전 1

당신은 나의 신이에요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python combinations 사용 시 유의사항 알려드립니다.

wjdals485 1년 전 3

yopark 1년 전 1

seogudwns12 1년 전 1

bh2980 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말