12/14 스터디

15650 N과 M(2)

앞서 풀었던 15649 문제 N과 M(1)이 순열 문제였다면, 이 문제는 조합 문제였다. 마찬가지로 combination을 쓰면 금방 풀 수 있지만 이것도 백트래킹을 활용해 풀어야한다. 순열과 조합 자체가 유사한데 한가지 다른 점은 순열은 [1,2]와 [2,1]이 다르지만 조합은 서로 같다. 이 점을 이용해서 15649 코드를 조금 변형하면 된다.

n, m = list(map(int, input().split()))
s = []
def dfs(start):
    if len(s) == m:
        print(' '.join(map(str, s)))
        return

    for i in range(start, n + 1):
        if i not in s:
            s.append(i)
            dfs(i + 1)
            s.pop()
dfs(1)

변형한 부분은 2가지 이다. 하나는 for문을 돌 때 start를 생각하며 돈다는 것, 그리고 재귀를 돌 때 i+1을 넘겨준다는 것이다. 그 이유는 다음과 같다.

(1) start 설정
먼저 start가 설정된 이유는, 뒤로 돌아갈 필요가 없기 때문이다. 무슨 소리냐면, 만약 3을 다룬다고 하면 [3,1]은 생각할 필요가 없다. 왜냐하면 [1,3]에서 이미 다뤘기 때문이다. 즉, 이전 것은 생각할 필요가 없고 3은 4부터, 4는 5부터 다루면 되기 때문에 start를 설정해준다.

 

(2) dfs(i+1)

start를 설정한 이유와도 연관이 되는데, 왜냐하면 start라는 것 자체가 dfs에 들어가는 i값이기 때문이다. 이 또한 마찬가지고 조합이기 때문에 이전 것들은 다루지 않아도 돼서 dfs에서 1로 시작하는 것들을 다루었으면 이제는 2부터 시작하는 것들만 다루고, 그 다음은 3부터 시작하는 것들만 다루고 ... 이런식으로 나아간다.

 

이전 것들은 다룰 필요가 없다는 것과, [1,2]와 [2,1]은 서로 같다는 것이 핵심인 문제였다.

 

10816 숫자카드 2

풀고나서 검색해보니 풀이가 5개나 나올만큼 여러 풀이가 가능한 문제였다. 개인적으로 category가 binary search였기 때문에 이분탐색으로 풀어보고 싶었는데 실패해서 Counter로 풀게 되었다. 일단 Counter에 대해 알아야하는데, Counter는 리스트를 넘겨주면 각 원소들이 몇 번 등장했는지 세어 딕셔너리 형태로 반환한다. 정말 이 문제를 위한 함수라고 할 수 있다. 예시는 다음과 같다.

ex1)
입력 - print(Counter("hello world"))
출력 - Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

ex2)
입력 - print(Counter(["hi", "hey", "hi", "hi", "hello", "hey"]))
출력 - Counter({'hi': 3, 'hey': 2, 'hello': 1})

이런식으로 딕셔너리 형태로 각 원소들을 세어 반환해준다. 그래서 우리는 numlist의 원소들이 cardlist에서 몇번 등장했는지 확인해야하므로 일단 cardlist를 Counter에 넘겨줘서 개수를 세어주고, numlist의 원소들을 하나씩 in으로 확인해보면서 체크하면 된다. 이때, 3이 1개 4가 5개 이런식으로 key 와 value가 매칭되기 때문에 우리가 확인할 것인 key들이고, 출력할 것은 value이다. 따라서 if numlist[i] in count 로 key들과 비교해준 뒤 만약 in이 true라면 출력해주는 것은 value값인 count[ numlist[i] ] 가 된다. 만약 false로 없다면, 그냥 0을 출력해준다.

import sys
from collections import Counter # 해당 원소들이 몇번 등장했는지 카운팅해서 dict로 반환

n = int(input()) # 숫자카드 n개
cardlist = list(map(int, sys.stdin.readline().strip().split()))

m = int(input()) # 정수 m개
numlist = list(map(int, sys.stdin.readline().strip().split()))

count = Counter(cardlist)
#형태 =>> Counter({10: 3, 3: 2, -10: 2, 6: 1, 2: 1, 7: 1})

for i in range(m):
    if numlist[i] in count: # key 들이랑 대조
        print(count[numlist[i]], end = ' ')
    else:
        print(0, end=' ')