[EPPER] 11회 6번

문제

 

---

풀이

 

접근을 잘못했던 문제. 하필이면 그 접근으로도 입력 예시는 전부 다 맞게 나와서 난 그게 맞는 줄 알았다. 근데 혹시나 하는 마음에 돌려본 테스트 케이스에서 오류를 발견했다. 먼저 기본틀을 설명하고 잘못됐던 풀이와 옳은 풀이를 설명하겠다.

 

일단 수를 입력받은 뒤 자릿수대로 쪼개어서 정수 배열에 집어넣었다. 1의 자리부터 집어 넣으니 뒤집혀서 저장될 것이다. 입력 예3의 경우라면 {1,1,7,7,2}가 저장됐을 것이다. 만약 입력 예2라면 {0,3,3}일 것이다. 보면 알겠지만 해당 배열이 감소 수열이 아니라면 문제의 조건을 만족하는 수는 없다.

 

난 처음에 이렇게 접근했다. 왼쪽부터 탐색하며 감소 수열이 되는 순간 양 옆의 수를 swap하고 그 swap 지점의 왼쪽 부분이 내림차순이 되도록 정렬했다. 말로 해서는 어려우니 입력 예3으로 설명하겠다.

위 배열을 보면 index가 2에 가서야 감소 수열의 형태를 보인다는 것을 알 수 있다. 그래서 7과 swap 했고, 해당 인덱스의 왼쪽 부분을 내림차순 정렬 했다. 이렇게 구현하면 위 문제에서의 입력에서는 전부 정답을 출력한다. 하지만 반례가 있었다.

 

바로 313220이다. 위 논리로 계산을 하면 330122라는 결과가 나온다. 하지만 정답은 320123이다. 어디서 틀린걸까? 감소 수열이 된 지점에서 바로 왼쪽에 위치한 수와 바꾼다는 내 판단이 틀렸다. 해당 인덱스의 왼쪽에 위치한 모든 수 중에서 그 수보다 큰 숫자와 바꿔야 한다. swap 과정만 그림으로 표현해보겠다.

인덱스의 수보다 큰 숫자를 찾자마자 break를 해도 되는가에 대한 의문이 있을 수 있다. 하지만 그래도 된다. 만약 2와 1사이에 2보다 작은 수가 있었다면 이미 해당 수에서 감소 수열 발견으로 인한 swap이 일어났을 것이기 때문이다. 아무튼 swap 과정을 이렇게 수정하고 해당 point를 저장한다. 이 point를 찾지 못했다는 것은 문제의 조건에 부합하는 수가 없다는 뜻이니 바로 0을 출력하고 그렇지 않으면 내림차순 정렬 후 num_arr로 쪼개놓은 수를 다시 합쳐서 출력한다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

void insertion_sort(int arr[], int point) { //삽입 정렬(내림차순 정렬)
	int temp = 0;
	
	for (int i = 1; i < point; i++) {
		temp = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] < temp) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}
}

int merge(int arr[], int length) { //배열로 쪼개놓은 숫자 다시 합치기. 근데 생각해보니 그냥 출력이니까 걍 출력해도 됐을듯
	int mul = 1;
	int sum = 0;
	
	for (int i = 0; i < length; i++) {
		sum = sum + (arr[i] * mul);
		mul *= 10;
	}
	return sum;
}

/*313220 이라면 022313으로 저장되어있을 것임.
맨 오른쪽 3부터 0으로 향하면서 내 왼쪽에 있는 수 중에 나보다 큰 수가 있는지 체크함
있으면 찾은거니까 findPoint true로 바꾸고 해당 지점 저장하고, 나랑 나보다 큰 애를 바꿈. 여기선 1과 2
다 돌았는데 findPoint가 여전히 false라면 오름차순이라는 것임(ex. 330) 이럼 얘가 제일 큰거니까 0 출력
그러고 나서 point 기준으로 왼쪽에 있는 배열을 내림차순 정렬함. 마지막에 합쳐주면 끝*/
int main() {
	int num_arr[6];
	int num;

	scanf("%d", &num);
	int cnt = 0;
	while (num != 0) { //문자 쪼개놓음
		num_arr[cnt++] = num % 10;
		num /= 10;
	}

	int point;
	bool findPoint = false;
	for (int i = 1; i < cnt; i++) {
		if (findPoint)
			break;
		for (int j = 0; j < i; j++) {
			if (num_arr[i] < num_arr[j]) {
				int temp = num_arr[i]; //swap
				num_arr[i] = num_arr[j];
				num_arr[j] = temp;
				point = i;
				findPoint = true;
				break;
			}
		}
	}
	if (!findPoint)
		printf("0");
	else {
		insertion_sort(num_arr, point);
		printf("%d", merge(num_arr, cnt));
	}
}