크래프톤 정글 TIL : 1013

lazyArtisan·2024년 10월 13일

TIL

정글 TIL

목록 보기

105/147

📝 배운 것들

🏷️ 파이썬 set()

https://www.daleseo.com/python-set/

remove()

>>> num_set = {1, 2, 3}
>>> num_set.remove(1)
>>> num_set
{2, 3}
>>> num_set.remove(3)
>>> num_set
{3}

세트의 remove() 메서드를 사용하면 세트로 부터 특정 값을 삭제할 수 있음

생성

>>> {'A', 'B', 'C'}
{'A', 'B', 'C'}

세트는 여러 가지 방법으로 생성할 수 있는데요.
가장 간편한 방법은 중괄호({}) 안에 여러 원소를 쉼표(,)로 구분해서 나열해주는 것입니다.

>>> {}
{} # dict

하지만 빈 세트를 생성할 때는 중괄호를 쓸 수 없으니 주의 바랍니다.
빈 중괄호는 파이썬에서 사전(dictionary)로 인식되기 때문입니다.

>>> set()
set()

대신에 빈 세트를 생성할 때는 set() 내장 클래스를 사용해야 합니다.

세트끼리 빼기

>> set1 = { 'a', 'b', 'c' }
>> set2 = { 'b', 'c' }
new_set = set1 - set2
print(new_set) # { 'a' }

차집합 연산도 가능하다.

🏷️ 파이썬 비트마스크와 sum()의 동작

a = 0b0010  # 2 (이진수: 0010, 'b'를 나타낸다고 가정)
b = 0b1000  # 8 (이진수: 1000, 'd'를 나타낸다고 가정)

# sum()으로 더하기
result = sum([a, b])

# 결과 출력
print(bin(result))  # 출력: '0b1010' (이진수 1010, 'b'와 'd'가 모두 포함됨)

sum으로 이진수를 더하면 or 연산처럼 작동한다.

👾 나만무

ppt 만듦

⚔️ 백준

📌 1062 가르침

내 풀이

# a, n, t, i, c 이 다섯 글자는 필수적으로 들어감.
# 고로 K가 4 이하면 읽을 수 있는 단어 없음.
# 각 단어에 필요한 문자를 알게되면
# a, n, t, i, c 중에 하나라면 포함 안 시켜도 됨
# 그리디로 못 품 -> (필요한 글자수)C(K) 의 조합 중 골라야 됨.
# n의 제곱이라는 건데, 글자가 작아서 ㄱㅊ을듯
# 각 글자들을 세트에 넣은 후에 리스트로 변환하고 인덱스를 재귀로 조합 경우의 수
# 각 단어들은 딕셔너리로 취급?
# 종료 조건 달성 (가르칠 수 있는 글자 다 가르쳤을 때) 하면 단어 몇 개 읽을 수 있는지 체크

# 백트래킹으로 조합에 대한 경우의 수 따지기
def combi(idx,remain):
    global max_val
    if remain == 0:
        cnt = 0
        for word in words:
            cnt+=1
            for w in words[word]:
                if w not in storage:
                    cnt-=1
                    break
        max_val = max(cnt, max_val)
        return
    for i in range(idx,len(letters)):
        storage.append(letters[i])
        combi(i+1,remain-1)
        storage.pop()
    
N,K=map(int,input().split())
words=dict()
if K < 5:
    print(0)
else:
    basics=set() # 필수 글자 적어놓기
    for s in 'antic': 
        basics.add(s) 
    letters=set()
    for _ in range(N): # 단어들을 순회하며 필요한 글자를 저장
        word = str(input())[4:-4]
        words[word]=set()
        for w in word:
            if w not in basics: # 기본 글자가 아니라면 필요 글자에 추가
                words[word].add(w)
                letters.add(w)
    letters=list(letters)
    storage = []
    max_val = 0
    combi(0,K-5)
    print(max_val)
    # letters 리스트에 대한 K-5 개의 인덱스 조합을 구한 뒤 읽히는 최대 단어 수 갱신

1번째 시도에는 시간 초과.

def combi(idx,remain):
    global max_val
    if remain == 0:
        cnt = 0
        for word in words:
            cnt+=1
            for w in words[word]:
                if w not in storage:
                    cnt-=1
                    break
        max_val = max(cnt, max_val)
        return
    for i in range(idx,len(letters)):
        storage.add(letters[i])
        combi(i+1,remain-1)
        storage.remove(letters[i])

storage를 세트로 바꿔서 storage 탐색 시간 복잡도를 줄였더니 50%까지는 감.
근데 50%에서 틀렸습니다가 떠버림.

예제 테케 중 뭔가 이상하게 단어 입력이 씹히는 것들이 있길래

if K < 5:
    for _ in range(N):
        dummy = input()
    print(0)

일단 fake input을 받긴 했는데, 그래도 50퍼에서 틀렸습니다.

2 25
antatica
antaztica
0

질문게시판 봄.
2여야 하는데 0이 나옴. 어째서?

# 백트래킹으로 조합에 대한 경우의 수 따지기
def combi(idx,remain):
    global max_val
    if remain == 0 or idx == len(letters): 
        # 아 idx==len(letters) 조건 맨 처음부터 눈여겨보고 있었는데 안 넣음
        cnt = 0

다 가르치지 않았어도 모든 letters 글자 사용했으면 끝내고 단어의 수 계산해야되는데
이 조건을 안 넣었었음. 분명 해야 될 것 같다고 생각했었는데 아오

근데 이거 그냥 조건 때려넣으니까 시간초과 나버림.

    letters=list(letters)
    storage = set()
    max_val = 0
    # 가르쳐야 할 글자가 가르칠 수 있는 글자보다 적으면
    # 가르쳐야 할 글자들만큼만 확인
    K = min(len(letters)+5,K) 
    combi(0,K-5)
    print(max_val)

한 번만 계산하도록 바꿈

# a, n, t, i, c 이 다섯 글자는 필수적으로 들어감.
# 고로 K가 4 이하면 읽을 수 있는 단어 없음.
# 각 단어에 필요한 문자를 알게되면
# a, n, t, i, c 중에 하나라면 포함 안 시켜도 됨
# 그리디로 못 품 -> (필요한 글자수)C(K) 의 조합 중 골라야 됨.
# n의 제곱이라는 건데, 글자가 작아서 ㄱㅊ을듯
# 각 글자들을 세트에 넣은 후에 리스트로 변환하고 인덱스를 재귀로 조합 경우의 수
# 각 단어들은 딕셔너리로 취급?
# 종료 조건 달성 (가르칠 수 있는 글자 다 가르쳤을 때) 하면 단어 몇 개 읽을 수 있는지 체크

# 백트래킹으로 조합에 대한 경우의 수 따지기
def combi(idx,remain):
    global max_val
    if remain == 0:
        cnt = 0
        # 단어들을 순회하며 지금까지 가르친 글자들로 읽을 수 있는지 판별
        for word in words:
            cnt+=1
            for w in words[word]:
                if w not in storage: # 없는 글자가 있으면 cnt 원복
                    cnt-=1
                    break
        max_val = max(cnt, max_val)
        return
    for i in range(idx,len(letters)):
        storage.add(letters[i])
        combi(i+1,remain-1)
        storage.remove(letters[i])

N,K=map(int,input().split())
words=dict()
if K < 5:
    for _ in range(N):
        dummy = input()
    print(0)
else:
    basics=set() # 필수 글자 적어놓기
    for s in 'antic': 
        basics.add(s) 
    letters=set()
    for _ in range(N): # 단어들을 순회하며 필요한 글자를 저장
        word = str(input())[4:-4]
        words[word]=set()
        for w in word:
            if w not in basics: # 기본 글자가 아니라면 필요 글자에 추가
                words[word].add(w)
                letters.add(w)
    letters=list(letters)
    storage = set()
    max_val = 0
    # 가르쳐야 할 글자가 가르칠 수 있는 글자보다 적으면
    # 가르쳐야 할 글자들만큼만 확인
    K = min(len(letters)+5,K) 
    combi(0,K-5)
    print(max_val)
    # letters 리스트에 대한 K-5 개의 인덱스 조합을 구한 뒤 읽히는 최대 단어 수 갱신

일단 맞았습니다 뜸.

남 풀이

from itertools import combinations
N,K=map(int,input().split())
# 가장 먼저 K값에 따라서 분류
if K<5:
    print(0)
    exit(0)
elif K==26:
    print(N)
    exit(0)
# 5개의 단어는 무조건 익혀야 하므로 -5해준다.
K-=5

# 모든 단어는 "anta"와 "tica"가 포함되어 있다.
# a,n,t,i,c 5개의 단어가 포함된다.
baseset=set('antic')
convert={chr(ord('a')+i):1<<i for i in range(26)}
words=[]
check=set()
ans=0
for _ in range(N):
    # 시작단어, 끝단어 제거
    word=set(input())-baseset
    # 5개의 단어로 읽을 수 있으면 ans +1
    if len(word) == 0:
        ans+=1
    # 배울 수 있는 단어보다 word의 길이가 같거나 짧은것만 읽을 수 있다.
    elif len(word) <= K:
        tmp=0
        # bit로 변환하여 저장
        for s in word:
            tmp +=convert[s]
        words.append(tmp)
        # 배워야 하는 단어의 후보군을 저장
        check |=word

check_size=len(check)
# 후보군을 bit로 변환한다.
check=map(lambda x: convert[x] ,check)
def compare(w):
    # 후보군의 전체 집합
    teach=sum(w)
    result=0
    # 각 단어들과 비교하여 읽을 수 있는지 counting한다.
    for word in words:
        if teach & word == word:
            result+=1
    return result

plus=max(map(compare,combinations(check,min(K,check_size))))
ans+=plus
print(ans)

내 시간 절반 이하인 사람들은 비트마스킹 씀.
이건 1등 풀이.

import sys
from itertools import combinations

N, K = map(int, sys.stdin.readline().split())

if K< 5:
    print(0)
    sys.exit(0)
elif K == 26:
    print(N)
    sys.exit(0)

words = [set(sys.stdin.readline().strip()) for _ in range(N)]

required = set(['a', 'c', 'i', 'n', 't'])
unique_set = set()
unique_list = []
max_learn = 0

for i in range(N):
    unique_list.append(words[i] - required)     
    unique_set.update(words[i] - required)      

if len(unique_set) <= K-5:      
        print(N)
        sys.exit(0)

for c in combinations(unique_set, K-5):
    learn_set = set(c)       
    temp = 0                 
    for unique_word in unique_list:      
        if unique_word <= learn_set:     
            temp += 1
    max_learn = max(max_learn, temp)        
print(max_learn)

이것도 다른 사람 코드인데 코드가 많이 간결해서 인상적.

from itertools import combinations
import sys
input = sys.stdin.readline

# word를 사용한 글자로 표현하는 비트
def bit(word):
    b = 0
    for c in word:
        b |= (1 << ord(c)-ord('a'))
    return b

N,K = map(int, input().split())
words = [input()[4:-5] for _ in range(N)] # 앞뒤 자름
#print(words)
*words_bit, = map(bit, words)
acint_bit = bit('acint')

ans = 0
if K >= 5:
    # acint 제외 나머지 21개의 글자를 bit로 표현
    letters = [1<<i for i in range(26) if chr(i+ord('a')) not in 'acint']
    for cb in combinations(letters, K-5):
        taught_bit = sum(cb) | acint_bit
        cnt = 0
        for word_bit in words_bit:
            if word_bit & taught_bit == word_bit: # word_bit이 taught_bit의 부분집합
                cnt += 1
        ans = max(ans, cnt)
print(ans)

와 *words_bit, = map(bit, words) 이 부분 미친 빠요엔이다
그리고 input 받을 때 sys.stdin.readline으로 받았어서 리스트 슬라이싱할 때
-4까지가 아니라 -5까지. 줄바꿈 문자까지 들어오기 때문.

map(bit, words)
- map() 함수는 첫 번째 인자로 주어진 함수를, 두 번째 인자인 반복 가능한 객체(리스트나 튜플 등)의 각 요소에 적용하여 결과를 반환하는 함수입니다.
- 여기서 bit 함수는 앞서 정의된 함수로, 주어진 단어를 비트마스크로 변환합니다. 즉, words 리스트에 있는 각 단어를 비트마스크로 변환하여 결과를 반환합니다.
- map(bit, words)는 words 리스트의 각 단어에 대해 bit() 함수를 적용한 이터레이터(iterator)를 반환합니다.
*words_bit,
- 이 구문은 언패킹을 사용한 부분입니다. *는 파이썬의 가변 인자(언패킹) 연산자입니다.
- *words_bit, = ...는 map() 함수로부터 반환된 결과를 모두 풀어서(unpack) words_bit라는 리스트에 저장합니다. 즉, map() 함수로부터 나온 여러 개의 값을 한꺼번에 words_bit 리스트에 할당하는 역할을 합니다.
예를 들어:
```
*a, = [1, 2, 3]
print(a)  # [1, 2, 3]
```
이와 비슷하게 *words_bit, = map(bit, words)는 words_bit에 map(bit, words)의 모든 결과를 리스트로 할당하는 역할을 합니다.

결론적으로 *words_bit, = map(bit, words)는 words 리스트에 있는 각 단어를 비트마스크로 변환한 값을 words_bit 리스트에 할당하는 역할을 합니다.

bit() 함수는 각 단어를 비트마스크로 변환하고,
map()은 words의 각 요소에 bit()를 적용하며,
*words_bit, =는 그 결과를 리스트로 언패킹하여 words_bit 리스트에 저장합니다.

결과적으로, words_bit에는 단어들이 비트마스크로 변환된 값들이 리스트로 저장됩니다.

letters = [1<<i for i in range(26) if chr(i+ord('a')) not in 'acint']

ord는 문자를 유니코드로 바꾸고,
chr는 유니코드를 문자로 바꾼다.

for cb in combinations(letters, K-5):

letters 리스트에서 K-5개를 고른 부분 집합 리스트가 cb

combinations 그냥 프린트하면 <itertools.combinations object at 0x7711c927ed90> 이런 식으로 나옴. for문을 사용해서 각 요소를 순회해야 하는듯.

taught_bit = sum(cb) | acint_bit

이진법이 들어있는 리스트를 sum 하면 이진법 or 연산 느낌으로 해준다.
그래서 sum 결과도 이진법 숫자이고, 또 다시 or 연산 해줘도 되는거.

if word_bit & taught_bit == word_bit: # word_bit이 taught_bit의 부분집합

지금까지 가르친 것들이 전부 word에 들어가있는지 확인

📌 10974 모든 순열

from itertools import permutations
N=int(input())
L=[i for i in range(1,N+1)]
for p in permutations(L,N):
    for n in p:
        print(n,end=' ')
    print('')

일단 내장함수 딸깍으로 풀어봄.

N=int(input())
L=[i for i in range(1,N+1)]
visited=[False]*N
# 효율 상관없이 구하자면 다음 숫자 고를때마다 이번에 골랐는지 안 골랐는지 확인

def permu(remain):
    if remain == 0:
        for s in storage:
            print(s,end=' ')
        print('')
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            storage.append(L[i])
            permu(remain-1)
            storage.pop()
            visited[i] = False
storage = []
permu(N)

정성 들여서 풀어봄.
의외로 딸깍과 성능 차이 그리 차이 안 남.

for permutation in permutations(range(1, N+1)):
    print(' '.join(map(str, permutation)))

다른 사람 풀이에 나오던 것들인데,
join 써보면 편하고 좋은 문제가 있을수도?

def permu(n):
    if n == N:
        print(' '.join(map(str, L)))
        return
    for i in range(n, N):
        L[n], L[i] = L[i], L[n]  # 스왑
        permu(n+1)
        L[n], L[i] = L[i], L[n]  # 원상 복구 (백트래킹)

N = int(input())
L = [i for i in range(1, N+1)]
permu(0)

gpt한테 최적화해보라고 했더니 이런 깔끔한 코드를 줬다.

for i in range(n, N) 루프는 n번째 요소와 그 뒤에 있는 모든 요소를 한 번씩 스왑하면서 모든 가능한 조합을 탐색합니다.

이해는 됨. 유려한 코드인듯.
근데 제출했더니 틀림.

o1-mini한테 이거 왜 틀렸냐고 다시 물어보니까

사전식이 출력이 아니라고 함.

def permu(current, used, path):
    if len(path) == N:
        print(' '.join(map(str, path)))
        return
    for i in range(N):
        if not used[i]:
            used[i] = True
            permu(current + 1, used, path + [L[i]])
            used[i] = False

N = int(input())
L = sorted([i for i in range(1, N+1)])  # 사전 순을 보장하기 위해 정렬
used = [False] * N
permu(0, used, [])