정말 오랜만에 업로드를 한다.
이유는, 여러가지가 있지만 그 중 가장 주된 이유는 최근 한달?정도를 국방부에서 열리는 2021 육군창업 경진대회 준비를 하느라 한동안 연등 시간 및 개인정비 시간에 창업경진대회 준비에 매진했다..
아직 결과는 발표되지 않았지만, 많은 시간을 투자한만큼 꼭 결선까지 갔으면 좋겠다..
https://www.army-startup.co.kr/
만약 1차가 붙으면, 아니 붙지 않더라도 조만간 무슨 아이템을 준비했고, 어떠한 동기 및 목적에서 이 아이템을 준비하게 되었는지 업로드를 하겠다. +그리고 아직 업로드를 하지 못했지만, 업로드를 하고 싶은 문제들이 있는데 추후에 차차 하도록 하겠다.
그리고 이건 여담이지만, 휴가 나가고싶다. 사람들이 많이 보고싶다.
자.. 오늘 업로드할 문제는, 교집합(투포인터 알고리즘)에 관한 문제이다.
두 집합 A,B가 주어지면 두 집합의 교집합을 출력하는 프로그램을 작성해야한다.
이 집합 A,B는 오름차순 혹은 내림차순으로 주어지지 않고 그냥 주어지기 때문에 우선 정렬부터 해야한다. 그래서 나는 처음에 문제를 보자마자 일단 정렬을 해야겠다고 생각했고, 집합 A와 B의 크기가 최대 30,000이길래 최대한 시간복잡도가 적은 '퀵정렬'을 이용해 정렬해보았다.
하지만 정말 어처구니없게도
include<algorithm> 에서 제공하는 sort 함수를 이용하면, 굳이 퀵정렬을 직접 구현하지 않아도, 단 한줄 만으로도 배열 정렬을 해준다는거.. 심지어, 저 라이브러리에서 제공해주는 함수를 쓰는게 훨씬 빠르다.. 직접 구현했더니, 크기가 30,000일 때에는 time_limit이 생겼다.. 이래서 사람은 공부를 해야된다..아는게 많아야 되고..
아무튼, 정렬 부분만 빼면 정답 코드와 거의 유사하게 코드를 짰고, 이왕 퀵정렬 구현하는 김에 다시한번 공부하면서 디테일하게 짜보았다.
코드는 아래와 같다.
#include<iostream>
using namespace std;
//퀵소트 정렬 매우 자세하고 쉬움 => https://hongku.tistory.com/149
void quick_sort(int *arr, int start, int end ){
//arr는 정렬할 배열, start는 맨 처음 인덱스, end는 맨 끝 인덱스
if(start>=end){ // 원소가 1개인 경우
return;
}
int pivot = start;
int i = pivot + 1; //i는 포인터인데, 피보 다음에서 시작
int j = end; //j 또한 포인터이며, 맨 끝에서 시작
int temp; //이따 i,j,pivot의 교환을 위해 필요
while(i<=j){
//포인터가 서로 엇갈릴때까지 반복
while(i<=end && arr[i]<=arr[pivot]){
//포인터 i가 맨끝(end)보다 작고, pivot보다 커지면 스탑
i++;
}
while(j>start && arr[j]>=arr[pivot]){
//여기서 i는 end보다 작거나 '같고' j는 start보다 '큰 '이유는
//애초에 start는 pivot위치로 선정되어 있기 때문
j--;
}
if(i>j){//둘이 엇갈리는 상황 => j와 pivot를 swap
temp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = temp;
}
else{// 엇갈리는 상황이 아닐경우에는 걍 i와 j 위치를 바꿔줌
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//위 과정을 재귀식으로 반복
quick_sort(arr,start,j-1);
quick_sort(arr, j+1, end);
//여기서 j가 기준이 되는 이유는, 어찌됐던 간에 j와 swap해주기 때문에
}
int main(){
int N, M, i;
int A[30001]={0,}, B[30001]={0,};
cin>>N;
for(i=0; i<N; i++){
cin>>A[i];
}
cin>>M;
for(i=0; i<M; i++){
cin>>B[i];
}
quick_sort(A, 0, N-1);
quick_sort(B, 0, M-1);
int p=0, q=0; //둘다 포인터
while(p<=N && q<=M){
if(A[p]<B[q]){
p++;
}
else if(A[p]>B[q]){
q++;
}
else{
if(A[p]==0){
break;
}
cout<<A[p]<<" ";
p++;
q++;
}
}
}위의 코드중의 퀵 정렬 부분을 간단하게 sort함수로 구현한 코드가 아래 코드다.
솔직히 어이가 없다.. 도대체 몇줄이 줄은거지.. 그래도 퀵 정렬 공부한셈 치자 ㅎㅎ
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int N, M, i;
int A[30001]={0,}, B[30001]={0,};
cin>>N;
for(i=0; i<N; i++){
cin>>A[i];
}
cin>>M;
for(i=0; i<M; i++){
cin>>B[i];
}
sort(A, A+N);
sort(B, B+M);
int p=0, q=0; //둘다 포인터
while(p<=N && q<=M){
if(A[p]<B[q]){
p++;
}
else if(A[p]>B[q]){
q++;
}
else{
if(A[p]==0){
break;
}
cout<<A[p]<<" ";
p++;
q++;
}
}
}