문제
세 난쟁이의 수염 길이가 오름차순 또는 내림차순으로 정렬되어 있는지 판별하라.
입력
테스트 케이스 수 T, 각 케이스마다 세 정수가 주어진다.
출력
"Gnomes:" 출력 후 각 케이스마다 "Ordered" 또는 "Unordered"를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 1 2 3 3 1 2 | Gnomes: Ordered Unordered |
풀이
인접 차이의 부호가 일관되는지 확인한다.
- 연속 두 차이
(b[1]-b[0])과(b[2]-b[1])을 구한다 - 두 차이의 곱이 양수이면 단조 증가 또는 감소이므로 "Ordered"
- 그렇지 않으면 "Unordered"를 출력한다
핵심 아이디어: 연속 차이의 곱이 양수이면 방향이 일관되므로 정렬된 상태이다.
코드
#include <bits/stdc++.h>
using namespace std;
int t;
int main()
{
cin >> t;
cout << "Gnomes:\n";
while (t--)
{
vector<int> beard(3);
for (int i = 0; i < 3; i++)
cin >> beard[i];
if ((beard[1] - beard[0]) * (beard[2] - beard[1]) > 0)
cout << "Ordered\n";
else
cout << "Unordered\n";
}
}복잡도
- 시간: O(T)
- 공간: O(1)