boj 3015번 문제에 대한 새로운 풀이를 찾다가 발견한 색다른 방법에 대하여. 이런 형태로 작성하는 것을 이해해보자.

boj 3015번 문제를 풀고나서, 

색다르게 풀이한 사람들은 없을까 하고 맞힌사람 탭으로 들어가서 풀이들을 보는데, 가장 처음에 올라와있는 2일전에 제출해서 올린 사람의 풀이를 보니까 현재까지 내가 접하던 형식의 코드작성이 아닌듯한 느낌이 들어서 이렇게 첨부해본다. 

 

sharaelong 이라는 분의 풀이인데, 이 풀이의 경우는 내가 풀이한 방법은 2020KB, 72ms 인데, 

18404KB 12ms로 문제를 해결했다. 사용하는 메모리를 늘리고 그에 반해 시간복잡도를 더욱 줄일 수 있는 풀이로 보여진다. 

내부 로직은 결국 어떤 형태로 되는지 이해는 하겠는데, 그 위에 붙어있는 부분들이 어떤 형식으로 저렇게 붙어서 , 저렇게 하는것이 어떤 영향들을 미치는 지에 대해서는 아직 단박에 이해가 가지 않는다. 

현재 수준에서는 내가 현재 풀이하는 형태로 저런 부가적인 설정들 없이 사용해서 풀이하는 방법으로 더욱 알고리즘들에 익숙해지도록 하고,  취미 느낌으로 저런 위에 붙어있는 설정하는듯한 부분들에 대해서 공부하고 이해해보도록 하자. 

 

sharaelong 이라는 분이 궁금해서 개인정보를 보니까 

꽤나 구력이 있으신 분인것 같다. 

이분이 제출한 문제들을 풀어보고, 이런식으로 시간복잡도를 더욱 확 줄일 수 있는 방법으로 풀이한 것들이 있다면, 그 풀이드를 또 찾아보면서 공부하고 하면 조금 더 재미있을것 같다.

 조금 더 구력을 쌓고 한번 도전해보도록 하자. 

 

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

namespace fio {
    const int BSIZE = 1 << 23;
    char buffer[BSIZE];
    char wbuffer[BSIZE];
    char ss[30];
    int pos = BSIZE;
    int wpos = 0;
    int cnt = 0;

    inline char readChar() {
        if (pos == BSIZE) {
            fread(buffer, 1, BSIZE, stdin);
            pos = 0;
        }
        return buffer[pos++];
    }
    
    inline int readInt() {
        char c = readChar();
        while ((c < '0' || c > '9') && (c ^ '-')) c = readChar();
        
        int res = 0;
        bool neg = (c == '-');
        if (neg) c = readChar();
        while (c > 47 && c < 58) {
            res = res * 10 + c - '0';
            c = readChar();
        }

        if (neg) return -res;
        else return res;
    }
    
    inline void writeChar(char x){
        if (wpos == BSIZE) {
            fwrite(wbuffer, 1, BSIZE, stdout);
            wpos = 0;
        }
        wbuffer[wpos++] = x;
    }
    
    inline void writeInt(int x){
        if (x < 0) {
            writeChar('-');
            x = -x;
        }
        if (!x) {
            writeChar('0');
        } else {
            cnt = 0;
            while (x) {
                ss[cnt] = (x % 10) + '0';
                cnt++;
                x /= 10;
            }
            for (int j=cnt-1; j>=0; --j) writeChar(ss[j]);
        }
    }
    
    inline void my_flush() {
        if (wpos) {
            fwrite(wbuffer, 1, wpos, stdout);
            wpos = 0;
        }
    }
}

void solve() {
    int n = fio::readInt();
    
    ll ans = 0;
    vector<pii> st;
    for (int i=0; i<n; ++i) {
        int x = fio::readInt();
        
        while (!st.empty() && st.back().first < x) {
            ans += st.back().second;
            st.pop_back();
        }
        if (st.empty()) {
            st.push_back({ x, 1 });
            continue;
        }
            
        auto[h, m] = st.back();
        if (h > x) {
            ans++;
            st.push_back({ x, 1 });
            continue;
        } else {
            ans += m;
            if (st.size() >= 2) ans++;
            st.back().second++;
        }
    }

    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}

 

위와 같은 풀이에 대해서 gpt에 검색해보니 아래와 같은 답을 얻을 수 있었다. 확실하게 이렇게 입출력 최적화를 통해서 연산시간을 줄일 수 있는 방법이 있는것 같다. 그리고 그걸 최적으로 적용해서 문제를 풀어야지 내가 풀때는 72ms가 걸리는 것을 이분이 풀었을때처럼 12ms만에 해결할 수 있을것 같다. 

아주 흥미로운 분야이다. 다음에 꼭 시간내서 취미로 공부해보도록 하자. 

 

 

=============

이 코드는 주어진 입력에 대한 문제를 해결하기 위한 C++ 프로그램으로, 입력 및 출력에 대한 입출력 최적화와 스택을 사용한 효율적인 알고리즘을 적용하고 있습니다.

프로그램의 주요 특징과 동작은 다음과 같습니다:

1. `#pragma GCC optimize("O3")`: GCC 컴파일러에게 최적화 수준을 높이도록 지시하는 프리프로세서 지시문입니다. 이렇게 최적화 수준을 높이면 코드 실행 속도가 향상될 수 있습니다.

2. `namespace fio`: 입출력 관련 함수들을 포함하는 사용자 정의 네임스페이스입니다.

3. `fio::readChar()`, `fio::readInt()`, `fio::writeChar(char x)`, `fio::writeInt(int x)`, `fio::my_flush()`: 입출력 함수들로, 입력 스트림에서 문자 및 정수를 읽고 출력 스트림에 문자 및 정수를 쓰는 데 사용됩니다. `fio::my_flush()`는 출력 버퍼를 비웁니다.

4. `void solve()`: 실제 문제 해결을 위한 함수로, 주요 로직이 포함됩니다.

5. `vector<pii> st`: 스택으로 사용할 벡터입니다. 각 원소는 수열의 높이와 해당 높이를 갖는 수열의 길이를 저장합니다.

6. 주요 로직:

   - 입력된 수열을 순회하면서 각 원소 `x`에 대해 다음을 수행합니다.
   - 스택 `st`에서 현재 원소 `x`보다 작은 높이를 갖는 수열들을 처리합니다. 이때, 해당 수열들의 길이를 결과 변수 `ans`에 누적합니다.
   - `st`가 비어있거나, 현재 원소 `x`보다 높이가 큰 수열이 스택에 없다면, 현재 원소 `x`를 스택에 추가하고 다음 원소로 넘어갑니다.
   - 스택 `st`의 맨 위 수열의 높이 `h`와 길이 `m`를 확인합니다.
     - `h`가 현재 원소 `x`보다 크다면, `x`와 길이 1의 새로운 수열을 스택에 추가하고 `ans`를 1 증가시킵니다.
     - 그렇지 않다면, `m`을 `ans`에 더하고, 스택의 크기가 2 이상이면 추가적으로 `ans`를 1 증가시킵니다. 그리고 스택의 맨 위 수열의 길이 `m`을 1 증가시킵니다.
   - 모든 원소에 대한 처리가 완료되면, `ans`에 조합 가능한 쌍의 수가 누적되어 있으며, 이를 출력합니다.

7. `main()`: 프로그램의 진입점입니다. `solve()` 함수를 호출하여 문제를 해결합니다.

이 코드는 입력 스트림과 출력 스트림에 대한 최적화를 포함하고 있어 입력을 빠르게 처리하고 결과를 빠르게 출력할 수 있도록 설계되어 있습니다. 또한 스택을 사용하여 문제를 해결하는 효율적인 알고리즘을 적용하여, 주어진 입력 크기에 대해서도 효율적으로 동작합니다.

 

=========