Special Sort(Google 인터뷰) / c / 제한시간 없음

▣ 문제

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

 

▣ 입력설명

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

 

▣ 출력설명

- 정렬된 결과를 출력한다.

 

▣ 입력 예시

8 1 2 3 -3 -2 5 6 -6

 

▣ 출력 예시

-3 -2 -6 1 2 3 5 6

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, i, j;
	int num[100];
	int temp;
	int pos = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}

	for (i = 0; i < n; i++) {
		if (num[i] < 0) {
			for (j = i; j > pos; j--) {
				temp = num[j];
				num[j] = num[j - 1];
				num[j - 1] = temp;
			}
			pos++;
		}
	}

	for (i = 0; i < n; i++)
		printf("%d ", num[i]);

	return 0;
}

 

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, i, j;
	int num[100];
	int temp;
	int pos = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}

	for (i = 0; i < n - 1; i++) {
		for (j = 0; j < n - i - 1; j++) {
			if (num[j] > 0 && num[j + 1] < 0) {
				temp = num[j];
				num[j] = num[j + 1];
				num[j + 1] = temp;
			}
		}
	}
	

	for (i = 0; i < n; i++)
		printf("%d ", num[i]);

	return 0;
}

버블 정렬의 개념을 이용해서 num[j]가 양수 num[j+1]이 음수일때마다 두 수의 위치를 바꿔주는 방식으로 구현했다.

 

.

내가 직접 한 코드는 배열중에서 음수가 있으면 해당 지점에서 계속해서 앞으로 옮기는 방식으로 구현했다.

 

기본적으로 버블 정렬의 개념을 빌려다가 짠 코드이다.

 

하지만 버블 정렬의 코드를 외워둔 상태에서 조건만 다르게 적용해서 작성하는 코드가

 

나중에 비슷한 유형이 나와도 더 빠르고 쉽게 풀것같다.