2022.05.11

33. 3등은 누구

int main(){

	//freopen("input.txt","rt",stdin);
	int n;
	cin>>n;
	
	int tmp;
	vector<int> nums(101,0);
	vector<int> scores;
	for(int i=0; i < n; i++){
		cin>>tmp;
		if(nums[tmp]!=0){
			continue;
		}
		nums[tmp]=1;
		scores.push_back(tmp);
	}
	
	int idx;
	for(int i =0; i<scores.size()-1; i++){
		idx=i;
		for(int j=i+1; j<scores.size(); j++){
			if(scores[idx]<scores[j]){
				idx=j;
			}
		}
		tmp = scores[i];
		scores[i]=scores[idx];
		scores[idx]=tmp;
	}

	cout<<scores[2];
	
	return 0;
	
}

선택정렬

35. special sort

int main(){

	//freopen("input.txt","rt",stdin);
	int n;
	cin>>n;
	
	int tmp;
	vector<int> nums;
	for(int i=0; i < n; i++){
		cin>>tmp;
		nums.push_back(tmp);
	}
	

	for(int i =1; i<n; i++){
		
		if(nums[i]<0){
			for(int j=i;j>0; j--){
				if(nums[j-1]>0){
					tmp=nums[j];
					nums[j]=nums[j-1];
					nums[j-1]=tmp;
				}
				
			}
		}
	}

	for(int i:nums)
		cout<<i<<' ';
	
	return 0;
	
}

• 버블정렬을 사용하는 경우

37. LRU

int main(){

	//freopen("input.txt","rt",stdin);
	int size,n;
	
	cin>>size>>n;
	
	vector<int> cashMemory(size,0);
	int num;
	int tmp;
	for(int i=0; i < n; i++){
		cin>>num;
		int flag =0;
		for(int j=0; j<cashMemory.size();j++){
			if(cashMemory[j]==num){
				flag=j;
			}
		}
		if(flag!=0){
			for(int j=flag;j>0;j--){
					tmp=cashMemory[j];
					cashMemory[j]=cashMemory[j-1];
					cashMemory[j-1]=tmp;
				}
		}
		if(flag==0){
			for(int j=size-2;j>=0;j--){
				cashMemory[j+1]=cashMemory[j];
			}
		cashMemory[0]=num;
		}
	
	}
	for(int n: cashMemory)
		cout<<n<<' ';

	
	return 0;
	
}

• 삽입정렬, flag 를 이용해 코드를 더 가독성 있게, 삽입정렬시 뒤쪽에서부터 인덱스를 잡는 편이 깔끔하다.

38. Inversion Sequence

int main(){

	//freopen("input.txt","rt",stdin);
	int n,ivsNum;
	cin>>n;
	vector<int> answer(n,101);
	
	for(int i=1;i<=n;i++){
		cin>>ivsNum;

		int tmp=0;
		for(;ivsNum>=0;){
			if(answer[tmp]>i){
				ivsNum--;
			}
			tmp++;
		}
		answer[--tmp]=i;
	}

	for(int number: answer)
		cout<<number<<' ';

	
	return 0;
	
}

• 강의 풀이는 작은 숫자는 순서에 영향을 주지 않기 때문에, 큰 숫자부터 정렬한다. 가장 큰 수를 맨 뒤에 두고, 차례대로 인덱스를 줄여가면서 그 다음으로 큰 숫자의 inversion number만큼 오른쪽으로 이동시켜 배치하는 식으로 코드를 작성한다.
  이 방법이 삽입정렬을 활용한 것 같고, 시간 복잡도가 더 적게 나와 좋은 방법 같다.