(BOJ) 17074 정렬

문제: https://www.acmicpc.net/problem/17074

 

문제 풀이:

오름차순인 구간을 나눔

ex) 123845인 경우

각각 0~3, 4~5번째 값들은 오름차순으로 정렬되어 있다.

그럼 경계에 있는 3, 4번 값이 뺄 수 있는 값의 후보이다

만약 3번을 뺐을 때, 4번을 뺐을 때 둘 다 정렬된 값이면 답은 2

즉, 답의 최대값은 2이다.

 

구간이 3개 이상이 나오면 어떤 값을 빼도 정렬될 수 없으므로 답은 0

case1: 왼쪽 구간이 한개만 존재하는 경우

   case1-1: 오른쪽 구간도 한개만 존재하는 경우

          -> 두 개다 뺄 수 있으므로 답은 2

   case1-2: 오른쪽 구간은 여러개인 경우

         -> 오른쪽 경계 뺐을 때 오름차순이면 답은 2

         -> 아니면 왼쪽 값만 뺄 수 있으므로 답은 1

case2: 왼쪽 구간이 여러개인 경우

   case2-1: 오른쪽 구간이 한개인 경우

        -> 왼쪽 경계 뺐을 때 오름차순이면 답은 2

        -> 아니면 오른쪽 값만 뺄 수 있으므로 답은 1

   case2-2: 오른쪽 구간도 여러개인 경우

       ->왼쪽 경계, 오른쪽 경계 빼보고 비교하고 오름차순 되는 경우 수가 답 (최대 2)

 

소스 코드:

int n,arr[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int l=0, r=n-1;
	for (int i = 1; i < n; i++) {
		if (arr[i-1] > arr[i]) {
			r = i - 1;
			break;
		}
	}
	if (r == n - 1) {
		cout << n << '\n';
		return 0;
	}
	else {
		l = r + 1;
		for (int i = l+1; i < n; i++) {
			if (arr[i-1] > arr[i]) {
				cout << "0\n";
				return 0;
			}
		}
		if (r == 0) {
			if (l == n-1) {
				cout << "2\n";
			}
			else {
				if (arr[r] <= arr[l + 1]) {
					cout << "2\n";
				}
				else  cout << "1\n";
			}
		}
		else {
			if (l == n - 1) {
				if (arr[r - 1] <= arr[l]) cout << "2\n";
				else	cout << "1\n";
			}
			else {
				int t = 0;
				if (arr[r - 1] <= arr[l]) t++;
				if (arr[r] <= arr[l + 1])t++;
				cout << t << '\n';
			}
		}
	}


	return 0;
}