[BOJ 1083] 소트

황준하·2022년 1월 22일
0

소트


  • 문제
    • 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.
  • 입력
    • 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.
  • 소스 코드
#include <iostream>

/*
단순한 정렬 문제가 아님(차례대로[인덱스처음부터] 비교하며 바꾸는 횟수가 아님) -> ex. 10 20 30 40 에 S가 2이면 20 30 10 40이 나오는 것이 아닌 30 10 20 40이 나와야 함

S만큼 교환 가능한 범위에서 최댓값을 가장 앞으로 가져오기 -> S<N 일때, 배열의 S번째까지 가장 앞으로 가져올 수 있음

1. 배열의 S번째까지 최댓값 탐색 후 위치(index) 저장
2. 해당 배열의 위치부터 탐색시작위치(i)까지 교환 반복
3. 교환 횟수를 S에서 빼주고 위 과정 반복

경우 1: S값이 배열의 크기(N)보다 작을 때
경우 2: S값이 배열의 크기(N)보다 클 때

*/

// using namespace std;

int main() {
	int N, S, temp;
	int A[50];
	int i, j, max_num, max_idx = 0;

	std::cin >> N;

	for (int i = 0; i < N; i++)
		std::cin >> A[i];

	std::cin >> S;

	for(i=0; i<N; i++){
		if (S <= 0) break;
		max_num = A[i];  // 탐색 시작하는 위치를 최댓값이라고 가정 후 최댓값 탐색 시작
		max_idx = i;
		for (j = i+1; j < N; j++) {
			if (S-(j-i)>=0) {  // S>N 일 경우 i는 이미 정렬이 되어있으므로 i를 빼주어야 함
				if (max_num < A[j]) {
					max_num = A[j];
					max_idx = j;
				}
			}
		}

		for (int k = max_idx; k > i; k--) {
			temp = A[k - 1];
			A[k - 1] = A[k];
			A[k] = temp;
		}

		S -= (max_idx-i);  // S>N 일 경우 i는 이미 정렬이 되어있으므로 i를 빼주어야 함
	}

	for (int i = 0; i < N; i++)
		std::cout << A[i] << " ";

	std::cout << std::endl;

	return 0;
}
  • 헷갈렸던 점

    • 인덱스순서대로 탐색하는 것이 아니다.

      • ex. 10 20 30 40 에 S가 2이면 20 30 10 40이 나오는 것이 아닌 30 10 20 40이 나와야 함
      • 이 부분을 생각하는데 시간이 오래 걸렸다. 왜 당연히 순서대로 탐색한다고 생각했지...
    • 교환은 S번 할 수 있다. (이웃한 숫자끼리만 교환 가능)

      • S>N인 경우, S<N인 경우 고려해주기
      • S번 할 수 있는 범위 내에서 최댓값을 탐색해야 함

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN