백준 17074 (C++) 정렬

최초 업로드: 2025-10-29 23:54:56

최근 수정 시간: 2025-10-29 23:54:56

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 정렬

[문제 링크](https://www.acmicpc.net/problem/17074)

## 문제 설명

정렬이란, 배열의 모든 원소가 비내림차순이 되도록 순서를 바꾸는 것을 말한다. 예를 들어 배열 [2, 1, 2, 3, 1]을 정렬하면 [1, 1, 2, 2, 3]이 된다.

남규는 정수 N개로 이루어진 배열 하나를 갖고 있다. 이 배열에서, 남규는 맘에 들지 않는 수를 정확히 하나 골라서 버릴 것이다.

예를 들어, 남규가 가진 배열이 [1, 2, 3, 2]라면, 남규는 1을 버려 [2, 3, 2]를 만들거나, 첫 2를 버려 [1, 3, 2]를 만들거나, 3을 버려 [1, 2, 2]를 만들거나, 두 번째 2를 버려 [1, 2, 3]을 만들 수 있다. 그리고 네 가지 경우 중 결과가 정렬된 것은 [1, 2, 2]와 [1, 2, 3] 두 가지이다. 남규는 이처럼, 수 하나를 버린 뒤 결과 배열이 정렬되어 있기를 원한다.

남규가 갖고 있는 배열이 주어지면, 수 하나를 버려 정렬된 배열을 남기는 방법의 수를 구해보도록 하자.

## 입력

첫째 줄에 배열의 크기 N이 주어진다. (2 ≤ N ≤ 105)

둘째 줄에 배열의 원소 ai가 공백으로 구분되어 N개 주어진다. (-109 ≤ ai ≤ 109)

## 출력

남규가 수 하나를 버려 정렬된 배열을 만드는 경우의 수를 출력한다.

## 풀이
0부터 i-1까지 비내림차순인지 확인하는 배열과, i+1부터 n-1까지 비내림차순인지 확인하는 배열을 사용하여 풀었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100'000;

int a[MAX];
bool beforeSorted[MAX], afterSorted[MAX];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n;i++) cin >> a[i];

for(int i=0;i<n;i++) {
 beforeSorted[i]=true;
 if(i && a[i-1]>a[i]) break;
 }
 for(int i=n-1;i>=0;i--) {
 afterSorted[i]=true;
 if(i<n-1 && a[i]>a[i+1]) break;
 }

int cnt=0;
 for(int i=0;i<n;i++) {
 if(beforeSorted[i] && afterSorted[i] && (i==0 || i==n-1 || a[i-1]<=a[i+1])) cnt++;
 }
 cout << cnt;
}
```