글 읽기 - 2493 탑 문제 질문이요 ㅠㅠ

rhwnsrb1223 4년 전 0

위와 같은 코드로 실행을 하게 될 경우,

시간 초과가 나오게 되는데, 시간초과가 나오는 이유와 어느 부분을 해결하면 될지 답변부탁 드리겠습니다.

감사합니다.

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

int main (int argc, char *argv[]) {
    int testcase;
    std::cin >> testcase;
    std::vector<int> v;     // 입력을 위한 벡터 v
    std::vector<int> ans;   // 출력을 위한 벡터 ans

    for (int i = 0; i < testcase; i++) {
        int num;            // v에 넣어줄 정수 입력
        std::cin >> num;

        v.push_back(num);   // v에 정수 저장
    }
    
    /*
        i는 v의 맨 뒤부터 맨 처음까지 돈다.
        j는 v의 맨 뒤의 앞에서부터 맨 처음까지 돈다.
        v[i] <= v[j] 인 경우 
            ans 벡터에 그 배열의 위치에서 1을 더해서 저장을 하고
            cnt를 1개 증가시킨다.
        v[i] > v[j] 인 경우 
            다음 j의 값에 대한 반복문을 실행한다.
        위의 과정을 거쳤는데 cnt가 0인 경우 ans벡터에 0을 넣는다.
        그리고 해당 위치의 v의 배열을 삭제한다.
    */
    for (int i = v.size()-1; i >= 0; i--) {         
        int cnt = 0;    // 자신보다 높은 탑이 있는지 검출하기 위한 변수
        for (int j = v.size()-2; j >= 0; j--) { 
            if(v[i] <= v[j]) {
                ans.push_back(j+1);
                cnt++;
                break;
            }
            else
                continue;
        }
        if (cnt == 0)   ans.push_back(0);   // cnt = 0이면, ans 벡터에 0을 넣는다.

        cnt = 0;    
        v.pop_back();
    }
        
    for (int i = ans.size()-1; i >= 0; i--) 
        std::cout << ans[i] << " ";

    return 0;
}

djm03178 4년 전 0

이중 루프가 최악의 경우 O(N^2)을 만들기 때문에 당연히 시간 초과입니다.

이 문제는 대표적인 스택 문제입니다. 스택을 사용해서 모든 원소가 자신보다 왼쪽에 있는 모든 원소를 매번 확인하지 않아도 되게 만들어 보세요.

rhwnsrb1223 4년 전 0

답변 감사드립니다.

벡터로 해결하려햇는데 스택으로 풀어보는 연습을 해보겠습니다!!

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

문제

문제

출처

ICPC

2493 탑 문제 질문이요 ㅠㅠ

rhwnsrb1223 4년 전 0

djm03178 4년 전 0

rhwnsrb1223 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말