[백준 N과M 시리즈, Python] N과M 시리즈
우선, 시리즈를 앞서서 열심히 풀어봤지만 뒤로 갈수록 거의 앞선 코드 복붙의 향연이라 순열조합 마스터의 목표와는 다르게 복붙의 왕이 되었다,, 순열 조합 순서가 중요하고 말고는 알지만 몇번 문제가 정확히 어느건지는 모르니껭,,틀려도 이해해달라능 *'ㅂ'*~ 공대지만 수포자니께~~~
그리고 기본format을 고냥 복붙해서,,함수이름이 순열이든 조합이든 다 combi다 머쓱타드 ^^;;;
간단하게 정리하면 일단 idx로 뽑아주는 개수를 넘기고 sel이라는 매개변수(list)로 뽑은 애들을 넘겨준다.
🤷♀️ 중복을 허용한다면 방문체크는 필요 없다! 그리고, 조합을 만들려면 순서가 상관없슴 =>
결국 앞선 idx는 뒤에 반복문에서 돌지 않아야함 (1,2)나 (2,1)은 같은거니까..그래서 마지막 방문 reset과정을 for문을 하나 추가하여 범위를 그 인덱스(i)보다 하나 큰 녀석부터(i+1) 0으로 만들어준다!!!
[N과M-(1)]
🐤 순열
자기랑 같은 애는 나오면 안되고, 순서를 고려해야한다.
from sys import stdin
def combi(idx,sel):
if idx == M:
print(*sel)
else:
#for문이 있어야 모든 numbers가 나온다
for i in range(N):
if visit[i] == 0:
visit[i] = 1
combi(idx+1,sel+[numbers[i]])
visit[i] = 0
#순열
N,M = map(int,stdin.readline().split())
numbers = [i for i in range(1,N+1)]
visit =[0]*(N)
combi(0,[])
[N과M-(2)]
🐤 조합
역시 마찬가지루 자기랑 같은건 안되고, 순서가 상관없다!
#조합
def combi(idx,sel):
if idx == M:
print(*sel)
for i in range(N):
if visit[i] == 0:
visit[i] = 1
combi(idx+1,sel+[num[i]])
#뽑았던 것은 다음 라운드에 안나오게 해주도록 i빼고 reset
for j in range(i+1,N):
visit[j] = 0
from sys import stdin
N,M = map(int,stdin.readline().split())
num = [i for i in range(1,N+1)]
visit =[0]*(N)
combi(0,[])
[N과M-(3)]
🐤 중복순열
1번 처럼 순열이지만, 같은걸 뽑아도 가능! 순서고려해야한다
from sys import stdin
N,M = map(int,stdin.readline().split())
def comb(idx,sel):
if idx==M:
print(*sel)
return
for i in range(N):
comb(idx+1,sel+[num[i]])
num = [i for i in range(1, N + 1)]
comb(0, [])
[N과M-(4)]
🐤 중복조합
비내림차순의 등장! 애초에 sel에 추가할때부터 마지막 인덱스와 비교하여서 같거나 큰 값들만 추가될 수 있도록 설정해준다. 만약 빈 list라면 그냥 추가해도 되니까 그 조건도 같이!
from sys import stdin
N,M = map(int,stdin.readline().split())
def comb(idx,sel):
if idx==M:
print(*sel)
return
for i in range(N):
if len(sel) == 0 or sel[-1] <= num[i]:
comb(idx+1,sel+[num[i]])
num = [i for i in range(1, N + 1)]
comb(0, [])
[N과M-(5)]
🐤 순열
다만 이제는 숫자 list를 만들지 않고, 주는 녀석을 사용.
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
print(*sel)
return
for i in range(N):
if visit[i] == 0:
visit[i] = 1
comb(idx+1,sel+[num[i]])
visit[i] = 0
visit = [0]*N
comb(0, [])
[N과M-(6)]
🐤 조합
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
print(*sel)
return
for i in range(N):
if visit[i] == 0:
visit[i] = 1
comb(idx+1,sel+[num[i]])
#앞에서 나왔던 숫자가 나오면 안될때는 i빼고 reset
for j in range(i+1,N):
visit[j] = 0
visit = [0]*N
comb(0, [])
[N과M-(7)]
🐤 중복순열
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
print(*sel)
return
for i in range(N):
comb(idx+1,sel+[num[i]])
comb(0, [])
[N과M-(8)]
🐤 중복조합
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
print(*sel)
return
for i in range(N):
if visit[i] == 0:
if len(sel) == 0 or sel[-1]<=num[i]:
comb(idx+1,sel+[num[i]])
for j in range(i+1,N):
visit[j] = 0
visit = [0]*N
comb(0, [])
[N과M-(9)]
🤢순열인디 주어지는 숫자 list에 중복되는 숫자가 있어서 자동으로 중복되는 순열이 만들어지구 그걸 없애줘야하는 것
이 문제가 제일 힘들었다, 그냥 단순히 sel을 result라는 큰 list에 추가한다음에 set으로 해서 sort하면 끝아녀~ 했는데 set안에는 list같은 mutable data가 들어가면 안되나보다..
그래서 처음에는 아예 sel을 문자열로 만들었다,, 예쩨는 통과햇는데 왜 미통과지 하고 질문칸의 반례들을 검색한 결과
1000과 같은 두자리 이상의 숫자들은 문자열에서 1 0 0 0 처럼 하나씩 인식되서 틀리는것,,
결국 sel을 tuple형태로 만들어서 처리하였다!
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
result.append(tuple(sel))
return
for i in range(N):
if visit[i] == 0:
visit[i] = 1
comb(idx+1,sel+[num[i]])
visit[i] = 0
visit = [0]*N
result = []
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
print(*r)
#not in으로 중복 점검 => 시간 초과
#str로 치환 경우에는 두자리 이상의 숫자가 하나하나로 처리
# ex)10000 => 1 0 0 0 0
[N과M-(10)]
🤢요상한 조합
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
result.append(tuple(sel))
return
for i in range(N):
if visit[i] == 0:
visit[i] = 1
if len(sel) == 0 or sel[-1] <= num[i]:
comb(idx+1,sel+[num[i]])
visit[i] = 0
visit = [0]*N
result = []
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
print(*r)
[N과M-(11)]
🤢요상한 중복 순열
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
result.append(tuple(sel))
return
for i in range(N):
comb(idx+1,sel+[num[i]])
result = []
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
print(*r)
[N과M-(11)]
🤢요상한 중복 조합
여기서 예상치 못하게 통과를 못했는데 아래와 같은 예시에서 걸렸던 것 같다. 그런데 반복 확인하는 visit없애고 다시 작성하니까 제대로 동작,,
#예시
3 2
1 11 111
#처음내코드 출력
1 1
1 11
1 111
11 111
111 111
#나와야하는 출력
1 1
1 11
1 111
11 11
11 111
111 111
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
if idx==M:
result.append(tuple(sel))
return
for i in range(N):
if len(sel) == 0 or sel[-1] <=num[i]:
comb(idx+1,sel+[num[i]])
result = []
visit= [0]*N
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
print(*r)