글 읽기 - 출력 초과 질문입니다.

suno 4년 전 0

예제와 질문 게시판의 반례들 대상으로 했을 땐 정답이 나오는데, 채점하면 출력 초과가 발생하는 이유를 모르겠습니다.

도움주시면 감사하겠습니다ㅜㅜ

제출한 소스입니다.

https://www.acmicpc.net/source/19249682

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

/* 문제 정의
탑의 높이 수열 -> 각 탑의 신호를 받는 탑 번호
신호를 받는 탑? 왼쪽에 있는 탑 중에서 자신보다 높거나 같은 탑 중 가장 가까운 탑
N <= 5*10^5 O(NlgN)
탑의 높이 <= 10^8
 */

/* 해결 알고리즘 생각

스택에 push할때
스택 top이 자신보다 작으면 => 가려지는 애들. pop해도 무방.
자신보다 큰 애 나올 때까지 pop. 나오면 걔가 수신탑.
스택 top이 자신보다 크거나 같으면 => 내 레이저 수신하는 탑. push하고 수신탑 출력.
*/

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

    int n, k, count;
    stack<int> height;
    cin >> n;
    cin >> k;
    height.push(k);
    cout << 0 << ' ';
    for (int i = 2; i <= n; i++)
    {
        cin >> k;
        //count = 0;
        //탑이 stack top보다 크면
        //  stack top보다 작거나 같을 때까지 pop
        //  count++
        //  empty면 0출력하고 종료
        //i-1 - count 출력 (자기보다 크거나 스택이 빈 상황)
        //자기보다 크면 i-1 - count 출력
        //비었으면 0 출력
        count = 0;
        while (height.top() < k)
        {
            height.pop();
            count++;
            if (height.empty())
                break;
        }
        if (height.empty())
            cout << 0 << ' ';
        else
        {
            cout << i - 1 - count << ' ';
        }
        height.push(k);
    }
    return 0;
}

/*
        if (height.top() < k) //탑이 stack top보다 크면
        {
            count = 0;
            // 
            do
            {
                height.pop();
                cout << "pop ";
                count++;
                if (height.empty())
                {
                    cout << 0 << ' ';
                    break;
                }
            } while (height.top() < k);
            cout << i - 1 - count << ' ';
            height.push(k);
        }
        else
        {
            // printf("02\n");
            height.push(k);
            cout << i - 1 << ' ';
        }
*/

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

출력 초과 질문입니다.

suno 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말