백준 11536번 [줄 세우기](C++) -yes6686- 티스토리

백준 문제 풀이: 11536 (줄 세우기)

---

문제 링크: https://www.acmicpc.net/problem/11536

문제 설명:

이름의 리스트가 주어졌을 때, 리스트가 사전 순으로 오름차순(INCREASING)인지, 내림차순(DECREASING)인지, 혹은 둘 다 아닌지(NEITHER)를 판별합니다. 이름은 알파벳 대문자로만 구성되며, 최대 20개의 이름이 입력됩니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

string s[21]; // 최대 20개의 이름을 저장할 배열

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

    int n;
    cin >> n; // 이름의 개수 입력
    for (int i = 0; i < n; i++) {
        cin >> s[i]; // 이름 입력
    }

    // 증가 여부와 감소 여부를 확인하는 플래그
    bool increasingCheck = true;
    bool decreasingCheck = true;

    for (int i = 1; i < n; i++) {
        if (s[i] > s[i - 1]) {
            decreasingCheck = false; // 증가하는 경우, 내림차순이 아님
        } else if (s[i] < s[i - 1]) {
            increasingCheck = false; // 감소하는 경우, 오름차순이 아님
        }
    }

    // 결과 출력
    if (increasingCheck) {
        cout << "INCREASING\n";
    } else if (decreasingCheck) {
        cout << "DECREASING\n";
    } else {
        cout << "NEITHER\n";
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 리스트를 순회하면서 사전 순서의 오름차순과 내림차순 여부를 검사합니다.
• 구현 세부사항:
  • increasingCheck와 decreasingCheck: 오름차순 및 내림차순 여부를 판별하기 위한 플래그입니다.
  • 두 번째 이름부터 차례로 이전 이름과 비교하면서 오름차순과 내림차순을 동시에 검사합니다.
• 시간 복잡도 분석:
  • 이름 리스트의 길이가 n일 때, 리스트를 한 번 순회하므로 시간 복잡도는 O(n)입니다.
  • 입력 제한이 20이므로 매우 빠르게 해결됩니다.

---

결과

주어진 이름 리스트의 순서를 정확히 판별하고 결과를 출력합니다.

• 오름차순: "INCREASING"
• 내림차순: "DECREASING"
• 둘 다 아닌 경우: "NEITHER"

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!