BAEKJOON : 15663, 1759, 11723

No. 15663

1. Problem

2. My Solution

• 첫 번째 방법
• 수열을 구한 뒤 res 에 이미 해당 수열이 존재하면 넘어감
• not in 연산 시간 -> 시간초과

import sys

def permutation(level):
    if level >= m:
        if arr not in res:
            res.append(arr.copy())
    else:
        for i in range(n):
            if visited[i] == True:
                continue
            else:
                arr[level] = nums[i]
                visited[i] = True
                permutation(level+1)
                visited[i] = False


n, m = map(int,sys.stdin.readline().rstrip().split())
nums = sorted(list(map(int,sys.stdin.readline().rstrip().split())))

arr = [0] * m
visited = [False] * n
res = []

permutation(0)

for i in res:
    print(' '.join(map(str,i)))

• 두 번째 방법
• itertools permutation 이용 (반환 값은 iterable tuple)
• set 자료형으로 변환하여 중복된 값을 제거

import sys
from itertools import permutations

n, m = map(int,sys.stdin.readline().rstrip().split())
nums = sorted(list(map(int,sys.stdin.readline().rstrip().split())))

for i in sorted(set(permutations(nums,m))):
    print(*i)

• 세 번째 방법
• set 자료형은 안에 요소로 값 또는 튜플만을 가질 수 있음
• 첫 번째 방법에서 수열을 저장하는 자료형을 튜플로 지정
• 튜플은 값을 변경할 수 없으니 리스트 자료형으로 arr 지정

import sys

def permutation(level):
    if level >= m:
        res.add(tuple(arr))
    else:
        for i in range(n):
            if visited[i] == True:
                continue
            else:
                arr[level] = nums[i]
                visited[i] = True
                permutation(level+1)
                visited[i] = False


n, m = map(int,sys.stdin.readline().rstrip().split())
nums = sorted(list(map(int,sys.stdin.readline().rstrip().split())))

arr = [0] * m
visited = [False] * n
res = set()

permutation(0)

for i in sorted(res):
    print(*i)

3. Learned

• tuple 자료형은 값을 변경할 수 없음 (변경하기 위해서는 + 연산)
• set 자료형은 요소로 값 또는 튜플만을 가질 수 있음 (list불가)
• print(*i) 에서 * 연산자는 여러 값을 갖는 자료형의 요소들을 ',' 으로 구분해서 인자로 보냄
• 함수의 매개변수로 (value, *args, **kargs) 받을 수 있고 *args 는 튜플로 감싸서 받음
  

No. 1759

1. Problem

2. My Solution

• 첫 번째 방법
• itertools 모듈의 combinations 함수 사용 (조합)
• 만약 알파벳이 자음이 아니면 -> 모음

import sys
from itertools import combinations
                                
l, c = map(int,sys.stdin.readline().rstrip().split())
alphabet = sorted(list(sys.stdin.readline().rstrip().split()))

for i in combinations(alphabet,l):
    count = 0
    for a in ['a','e','i','o','u']:
        if a in i:
            count += 1
    if l - count >= 2 and count > 0:
        print(*i,sep='')

• 두 번째 방법
• 오름차순의 수열만을 출력하도록 함 = 백트래킹을 이용한 조합

import sys

def permutation(level, pre):
    if level >= l:
        count = 0
        for i in arr:
            if i in 'aeiou':
                count += 1
        if l - count >= 2 and count > 0:
            res.append(arr.copy())
    else:
        for i in range(c):
            if visited[i] == True:
                continue
            else:
                if str(pre) < alphabet[i]:
                    arr[level] = alphabet[i]
                    visited[i] = True
                    permutation(level+1, alphabet[i])
                    visited[i] = False
                              
l, c = map(int,sys.stdin.readline().rstrip().split())
alphabet = sorted(list(sys.stdin.readline().rstrip().split()))

arr = [''] * l
visited = [False] * c
res = []
permutation(0,0)

for i in res:
    print(*i, sep='')

3. Others' Solutions

• 백트래킹을 이용한 조합
• 주어진 수를 왼쪽에서 오른쪽으로만 조합해야함
• 해당 숫자에서 오른쪽에 있는 숫자만을 이용하기 위해 i 정보를 인자로 넘김

import sys

def permutation(level, index):
    if level >= l:
        count = 0
        for i in arr:
            if i in 'aeiou':
                count += 1
        if l - count >= 2 and count > 0:
            res.append(arr.copy())
    else:
        for i in range(index, c):
            if visited[i] == True:
                continue
            else:
                arr[level] = alphabet[i]
                visited[i] = True
                permutation(level+1, i+1)
                visited[i] = False
            
                                
l, c = map(int,sys.stdin.readline().rstrip().split())
alphabet = sorted(list(sys.stdin.readline().rstrip().split()))

arr = [''] * l
visited = [False] * c
res = []
permutation(0,0)

for i in res:
    print(*i, sep='')

4. Learned

• 조합은 순서가 없는 수열이므로 오름차순으로 나열한다면 순열을 오름차순으로만 출력하도록 백트래킹한 것과 동일함

No. 11723

1. Problem

2. My Solution

• 파이썬의 장점을 이용하여 간단히 구현 (메모리 제약이 까다롭지 않음)

import sys

n = int(sys.stdin.readline())
arr = set()

for _ in range(n):
    op = sys.stdin.readline().rstrip().split()
    
    if op[0] == 'add':
        arr.add(op[1])
    elif op[0] == 'remove':
        arr.discard(op[1])
    elif op[0] == 'check':
        if op[1] in arr:
            print(1)
        else:
            print(0)
    elif op[0] == 'toggle':
        if op[1] in arr:
            arr.discard(op[1])
        else:
            arr.add(op[1])
    elif op[0] == 'all':
        arr = set(['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16','17','18','19','20'])
    else:   # empty
        arr = set()

3. Others' Solutions

• 비트 마스크를 이용하여 해결
• 0~20, n을 표현하기 위해 21개의 bit 가 필요함 (여기선 1부터 시작이니까 첫 번째 bit는 0 고정)
• 모든 비트를 1로 만들기 위해서 (1 << 21) -1
  - (1<<21) = 100000000000000000000
  - (1 << 21) -1 = 111111111111111111111

import sys

n = int(sys.stdin.readline())
bit = 0

for _ in range(n):
    op = sys.stdin.readline().rstrip().split()
    
    if op[0] == 'add':
        bit |= (1 << int(op[1]))
    elif op[0] == 'remove':
        bit &= ~(1 << int(op[1]))
    elif op[0] == 'check':
        if bit & (1 << int(op[1])) == 0:
            print(0)
        else:
            print(1)
    elif op[0] == 'toggle':
        bit ^= (1 << int(op[1]))
    elif op[0] == 'all':
        bit = (1 << 21) -1
    else:   # empty
        bit = 0

4. Learned

• 비트마스크에 대해 알게됨 (참고 블로그)
• 비트마스크
  - bit(0/1)로 구성된 이진수 정수를 이용하여 자료구조처럼 사용하는 기법으로 집합, 부분집합, 요소 구성 여부에 대한 문제 해결에 적용되는 알고리즘 기법
  - 집합에 존재하는 모든 요소의 수가 특정 수 n 보다 작다면 (n<30) 직접 접근하여 요소 존재 여부 판단가능 (1 << 0, 1<<20 -> 0이 있는지, 20이 있는지)
  - 보통의 경우에는 이미 존재하는 배열(리스트)에서 해당 index 번째 요소가 포함되었는지 판단하는 경우가 많음

• 비트마스크를 이용하여 계산 속도, 메모리 사용 공간에 대한 효율성을 높일 수 있음
• set 자료형 연산자 중에 discard() 함수는 요소가 존재하면 삭제하고 없으면 무시