[3015] 오아시스 재결합 - C++

온전히 내 힘으로 풀었다 할 수는 없지만, 첫 플레티넘 문제이고 내가 생각한 아이디어와 다른 사람의 아이디어를 적어보고 싶어 글로 작성해 본다.

---

아이디어

일단 규칙(?)을 찾아보려고 한다.

 

전 값보다 큰 게 들어온다면

 

전 값(2) 보다 큰 값이 들어온다면 앞의 2는 다음 사람을 보지 못하기 때문에 스택에 존재할 이유가 없어진다.

4와 같거나 큰 값, 또는 스택이 빌 때까지 POP해 준다.

 

전 값보다 작은 값이 들어온다면

카운트를 증가시킨다

 

같은 값이 들어온다면

예시 이미지

그렇다 (2, 2), (2, 2), (2, 2), (4, 2), (4, 2), (4, 2)가 가능하다.

중복된 값을 생략하여 넣는 방법을 스택을 하나 더 만들어 구현해 봤지만 아닌 것 같아 중간에 그만뒀다.

 

이 부분을 대체 어떤 식으로 구현해야 할지 몰라서 답을 봤다.

---

정답 풀이

stack에  값을 저장할 때

First : 현재 값과

Second : 중복된 값

을 저장한다.

stack<pair<int, int>> s;

전 값 보다 큰 값이 들어온다면

전 값의 중복된 개수를 더해가며 값을 스택에서 빼준다.

while(!s.empty() && s.top().first < now){
      cnt += s.top().second;
      s.pop();
    }

 

전 값과 같은 값이 들어온다면

전까지의 중복을 세어준 후

중복이 추가되는 것을 적용시킨다.

s.pop() 후에 size가 0 보다 크다면, 중복 이전에 큰 사람이 있었다는 것이므로 카운트 +1 해준다. 

if(s.top().first == now){
        cnt += s.top().second;
        same = s.top().second +1;
        s.pop();
        if(s.size() > 0)cnt++;
      }

 

전 값보다 작은 값이 들어온 다면

그냥 카운트 +1 해주면 된다.

else{
        cnt++;
      }

---

코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n;
long long cnt = 0;
stack<pair<int, int>> s;

int main(){
  init();
  cin >> n;
  
  while(n--){
    int now; cin >> now;
    
    //중복 카운트
    int same = 1;
    
    //전 값이 현재 값보다 작다면
    while(!s.empty() && s.top().first < now){
    
      //전 값의 중복 값들을 더해준다.
      cnt += s.top().second;
      s.pop();
    }
    
    //스택이 비어 있지 않고
    if(!s.empty()){
    
      //전 값과 현재 값이 같다면
      if(s.top().first == now){
      
        //전 값의 중복을 더해줌
        cnt += s.top().second;
        same = s.top().second +1;
        s.pop();
        
        //만약 중복 이외에 값이 있다면 나보다 큰값이 있다는 얘기 임으로 +1
        if(s.size() > 0)cnt++;
      }
      
      // 전 값이 현재 값보다 크다면
      else cnt++;
    }
    s.push({now, same});
  }
  cout << cnt;
  return 0;
}

같은 키를 이렇게 해결할 줄이야...

pair을 사용하여 해결할 줄이야....

---

문제를 풀며

문제를 보자마자 어? 쉬울 것 같은데라고 생각하며 임했다가 큰코다쳤다, 정말 어려운 문제다.

특히 같은 키의 사람들을 처리하는 부분이 제일 어려웠다.

 

처음에 아이디어를 생각할 때 정답과 비슷한 아이디어가 많이 나와 놀랐다. 하지만 구현하지 못하면 말짱 꽝이다.

 

첫 플레티넘 문제는 무조건 내 힘으로 풀고 싶었지만, 한 문제에 너무 많은 시간을 쏟는 것은 좋지 않기에

정답과 유사한 아이디어를 냈다는 것 만으로 만족하려 한다.

 

틀린 코드는 제출 번호로 들어가서 보면 된다.

꽤나(?) 비슷하다(?)

틀린 건 틀린 거다, 미련 버리고 다음에 다시 풀어보도록 하자

 

https://www.acmicpc.net/source/제출번호 입력