[it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비] 정렬 - Special Sort

문제

N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다. 음의 정수는 앞쪽에 양의정수는 뒷쪽에 있어야 한다. 또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다.

💡 입력설명
첫 번째 줄에 정수 N(5<=N<=100)이 주어지고, 그 다음 줄부터 음수를 포함한 정수가 주어진 다. 숫자 0은 입력되지 않는다.

💡 출력설명
정렬된 결과를 출력한다.

💡 입력예제
8
1 2 3 -3 -2 5 6 -6

💡 출력예제
-3 -2 -6 1 2 3 5 6

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>

using namespace std;

int main() {
	int n, i, j, tmp;
	scanf("%d", &n);
	vector<int> a(n);
	
	for(i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	
	for(i = 0; i < n - 1; i++) {
		for(j = 0; j < n - i - 1; j++) {
			if(a[j] > 0 && a[j + 1] < 0) {
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			} 
		}
	}
	
	for(i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	
	return 0; 
}

 

---

설명

사용자로부터 N을 입력받고 N만큼 반복하는 for문을 작성하여 정수들을 입력받고 a배열에 할당한다.

선택정렬 같은 경우 너무 거리가 멀기 때문에 버블정렬을 이용하여 음의 정수와 양의 정수를 나열하도록 한다.

버블정렬 알고리즘을 작성하고 현재 정수가 양수이고 다음 정수가 음수일 때만 swap이 일어나도록 하여 음의 정수와 양의 정수를 분리하여 나열하도록 조건문을 작성한다.

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.