15663번: N과 M (9)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
너무나 필수적인 N과 M시리즈의 9번째 문제이다. 개인적으로는 9번부터 더욱 필수다. 이 문제는 재귀와 백트래킹으로 해결하였다. 다만 문제를 읽고 주의할 점은, 똑같은 수가 여러 번 주어지면 모두 갖고는 있되, 각 경우의 수가 완전히 일치하는 경우는 배제한다는 점이다. 문제에서 주어진 예제를 보면,
3 1
4 4 2
가 있다. 이 경우, 하나를 뽑을 수 있는데 4가 2개 있어서
2
4
4
가 될 것 같지만, 4와 4는 중복이어서 카운트 하지 않는다는 것이다.
이 부분이 별거 아닌거 같지만, 필자는 문제 해결 시에 조금 애먹었던 기억이 있다. '저걸 어떻게 표현하지?'
정답은 정렬과 '이전 값 비교'이다.
여기서 잠깐 다른 얘기.
필자는 비전공자여서 컴퓨터공학과 및 IT관련 학과의 정확한 커리큘럼은 잘 모르지만, 알고리즘과 자료구조는 기본적으로 배우는 것으로 알고 있다. 그리고 그 내용에는 정렬이 반드시 포함된다. 정렬은 간단하게 오름차순, 내림차순 정렬 등이겠지만, 그 응용 범위가 상상을 초월할 정도로 넓다. 괜히 처음부터 배우는 게 아니다. (뭔가 굉장히 중요한 것들을 모르고 지나가는... 또는 깨닫지 못하는 안타까운 사람들을 위해 갑자기 할 말이 너무 많아져서 그에 관해 따로 포스팅을 해두겠다.) 알고리즘, 자료구조, PS(Problem Solving), CP(Competitive Programming)을 개인적으로 너무 좋아하여, 이쪽으로 조금씩이라도 꾸준히 공부하고 심지어 취미처럼 되어가고 있는데, 항상 느끼는 게 결국 기본이 쌓여서 큰 것을 이룬다. 세그먼트 트리, LCA, MST, HLD, KMP, Link Cut Tree 등등 어려운 내용들도 결국 파고 들면 배열, 리스트, 조건문, 재귀 함수, 정렬 등등의 기본 요소로 이루어져 있다. 이는 꼭 컴퓨터에 국한되는 얘기가 아니다. 모든 것이 그렇다. 벡터 미적분을 하기 위해 벡터와 미적분을 알아야 하고, 그중 미적분을 알기 위해서는 극한, 급수를 알아야 하고, 급수는 수열의 합에서 오는 것이고, 극한을 구할 때 차이 값을 작은 델타 값으로 나누지 않았던가? 우리가 처음 배우는 사칙연산까지 쪼개졌다.
결국 사칙연산부터 쌓아올려야 벡터 미적분까지도 가능하고, 미분 방정식도 풀 수 있게 되는 것이다.
정렬은 그 중 사칙연산 같은 것이다. 이전 포스팅에서 회의실배정, 강의실 배정과 같은 문제들도 시작 시간, 종료 시간 정렬 등을 통해 문제를 해결하였다. 정렬을 통해, 앞에 먼저 나오는 수가 가장 작은 수 혹은 가장 큰 수임을 보장하기 위함이다.
다시 문제로 돌아와서, 입력으로 받은 수를 정렬하여 앞에서부터 하나씩 뽑아 나간다.
그러다 다음 수가 이번에 뽑은 수와 같다면 (이전 값 비교) 스킵하고 넘어가는 것이다. 같은 수로 만들어진 케이스는 중복이라 세지 않을테니 말이다. 정렬을 통해 중복으로 들어온 수가 한데 모여있게 되고, 중복된 수를 만났다면 그대로 스킵할 경우, 나중에 갑자기 중복된 수가 다시 나타나지 않음이 보장된다.
while(arr[i+1]==arr[i])i++;위와 같이 arr안에 입력으로 들어온 수가 모여있고, 정렬되어 있다. 다음 수가 현재 수와 같다면 계속 넘기는 것이다.
<주요 내용>
백트래킹, 재귀 함수, 순열과 조합, 정렬, 방문 체크
<코드>
#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;
const int sz=8;
const int num=1e4+1;
bool visited[sz];
int cnt,a,n,m,arr[sz];
vector<int>hold;
void printer(int idx,int k){
if(k==m){
for(auto e:hold)cout<<e<<' ';
cout<<endl;
return;
}
for(int i=0;i<cnt;++i){
if(visited[i])continue;
visited[i]=1;
hold.push_back(arr[i]);
printer(i,k+1);
hold.pop_back();
visited[i]=0;
while(arr[i+1]==arr[i])i++;
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>m;
cnt=0;
for(;n--;){
cin>>a;
arr[cnt++]=a;
}
sort(arr,arr+cnt);
printer(0,0);
return 0;
}
아래는 파이썬 코드이다.
파이썬에서는 itertools라이브러리에 있는 permutations함수를 사용하였다.
중복은 허용하지 않으므로 set을 통해 중복제거를 하였다.
순서가 다르면 다른 케이스로 보기때문에 combinations를 사용하지 않았다.
from itertools import permutations as p
import sys
si=sys.stdin.readline
so=sys.stdout.write
def main():
nm = [int(e) for e in si().split()]
nList = [int(e) for e in si().split()]
nList = sorted(list(set(p(nList,nm[1]))))
for l in nList:
for e in l:
so(str(e)+' ')
so('\n')
if __name__=='__main__':
main()
nList = sorted(list(set(p(nList,nm[1]))))코드에서 위의 부분은 상당히 많은 역할을 한다.
먼저 입력값에서 m개를 뽑아서 퍼뮤테이션을 만든다. 그 전체를 set으로 감싸 중복을 제거하고, list 화하여 sorted를 통해 정렬될 수 있게 처리하였다. 이후에 nList에서 하나씩 뽑아서 마무리하며 되는 것이다.
