[백준] 2920번 - 음계

문제: 

 

시도 횟수: 1번

처음 생각한 방법: 오름차순 벡터, 내림차순 벡터 정렬해서 만들어두고 원본 벡터와 비교해서 출력 
그런데 처음에는

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

int main()
{
    int a;
    vector<int> vec;
    for(int i = 0; i < 8; i++) {
        cin >> a;
        vec.push_back(a);
    }
    if(vec == sort(vec.begin(), vec.end()))
        cout << "ascending";
    else if(vec == sort(vec.begin(), vec.end(), greater<int>()))
        cout << "descending";
    else
        cout << "mixed";
    return 0;
}

이런 식으로 접근했었다. sort와 vec를 바로 비교했다가 오류가 났었는데, sort는 리턴값이 없는 void를 반환하는 함수라고 한다.
그래서 직접적인 비교가 불가능해서 벡터 변수를 두개 더 만들어서 해결했다.

내 코드:

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

int main()
{
    int a;
    vector<int> vec;
    for(int i = 0; i < 8; i++) {
        cin >> a;
        vec.push_back(a);
    }
    vector<int> ascending = vec;
    vector<int> descending = vec;
    sort(ascending.begin(), ascending.end());
    sort(descending.begin(), descending.end(), greater<int>());
    
    if(vec == ascending)
        cout << "ascending";
    else if(vec == descending)
        cout << "descending";
    else
        cout << "mixed";
    return 0;
}

모범답안: 

#include <iostream>
using namespace std;

int main(){
    int num;
    int asc = 0;
    int desc = 0;

    for(int i=0; i<8; i++){
        cin >> num;
        if(num == i+1) asc++;
        else if(num == 8-i) desc++;
    }
    if(asc == 8) cout << "ascending";
    else if(desc == 8) cout << "descending";
    else cout << "mixed";

    return 0;
}

대부분 이 방식으로 풀었다. 

내 코드의 개선할 점: sort 함수를 사용하는 게 연산 코스트가 얼마나 높은지는 모르겠지만 남용하면 안될 것 같은 느낌이 든다.
모범답안은 시간복잡도가 O(1)이고, 내 코드는 시간복잡도가 O(n log n)이다. 시간복잡도를 낮추기 위해서 구현방식을 바꿔야겠다. 

알고리즘 분류: 구현

난이도: 브론즈 II

복습하면서 참고해본 블로그 목록: 

https://carrot-farmer.tistory.com/59

[백준] 2920번: 음계 | C++ 풀이