[백준] 2493번 : 탑 - C/C++

 

하루 종일 걸렸다.

나는 너무 어렵게 풀었다.

 

어렵게 풀었다기 보다는 아직 이정도 난이도의 문제를 풀 정도가 아닌 것 같다.

엄청난 검색과 엄청난 참고를 통해 완성한 나의 코드

 

분류 보고 풀지 말라고 했는데,,, 나는 또 보고 풀었다.

 

일단 풀이를 시작해보겠다.

 

자료구조 문제이고 스택을 이용하라고 했으니까

그렇게 풀어보자.

 

탑의 개수와 높이 설정하기.

int n;
cin >> n;

stack<pair<int,int>> s;

 

pair가 무엇인지에 대해서는 이전 글에 설명했으니

아래 링크를 달아두겠다.

https://binaryroot.tistory.com/9

[백준] 10814번 : 나이순 정렬 - C/C++

 

for문을 이용하여 탑의 높이를 입력한다.

for(int i = 0; i < n; i++){
   int height;
   cin >> height;
}

 

그 다음, 왼쪽에서 가장 먼저 만나는 높은 탑을 찾아주자.

while(!s.empty()){
     if(height < s.top().first){
     cout << s.top().second << " ";
     s.push(make_pair(height, i+1));
     break;
     }
	s.pop();
}

 

• 스택이 비어 있지 않으면, height와 s.top().first(이전 탑의 높이) 비교
• 현재 height보다 높은 탑을 만나면, 그 탑의 위치를 출력
• 요구하는 조건에 맞는 탑을 찾으면
  스택에 '현재 높이'와 '현재 위치' 추가 후 while문 종료

위의 3단계로 while문은 동작한다.

 

마지막으로 추가해주어야 하는 코드는

레이저 신호를 수신하는 탑이 존재하지 않으면 "0"을 출력하는 것.

 

if(s.empty()){
  cout << "0" << " ";
  s.push(make_pair(height, i+1));
}

 

위와 같이 작성 가능하다.

 

 

이제 제출하면 정답이다.

시간초과;

 

근데 이건 마법과도 같은 코드 딱 세 줄만 추가해주면 된다.

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

 

• ios::sync_with_stdio(false); → C++ 입출력 속도 최적화
• cin.tie(0); → cin과 cout의 묶음을 풀어 속도 향상
• cout.tie(0); → 출력 지연 방지

 

진짜 제출해보자.

 

맞았습니다 !! 가 나오게 된다.

 

 

 

 

전체 코드

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

//탑
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;

    stack<pair<int,int>> s;

    for(int i = 0; i < n; i++){
        int height;
        cin >> height;

        while(!s.empty()){
            if(height < s.top().first){
                cout << s.top().second << " ";
                s.push(make_pair(height, i+1));
                break;
            }
            s.pop();
        }
        if(s.empty()){
            cout << "0" << " ";
            s.push(make_pair(height, i+1));
        }
    }
    cout << '\n';
    return 0;
}

 

무려 골드5의 문제였다.

설명을 하니까 되게 쉬워보인다.

그냥 수학문제도 그렇고

어려운 문제일 수록 뭐랄까,,

생각을 많이하면 풀이가 쉽고

생각을 안하고 다른 방법을 생각하려고 하면 어려운 것처럼

알고리즘 문제도 그런 것 같다.(???)

아무말이나 막하네

 

어쨌든,, 나는 아직 골드라는 난이도의 문제를 풀 실력이 아닌 것 같다.

기초를 더 탄탄하게 공부해서 도전해야겠다.

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️