[백준 3015] 오아시스 재결합 (C++/Python)

C++)

#include <iostream>
#include <stack>
#include <map>
using namespace std;

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

	int n;
	cin >> n;

	long long ans = 0;
	int temp = 0;

	stack<int> st;
	map<int, int> m;

	while(n--) {
		cin >> temp;

		while (!st.empty() && st.top() < temp) {
			m[st.top()]--;
			st.pop();
			ans++;
		}

		if (!st.empty()) {
			if (st.top() == temp) {
				if (st.size() == m[temp])
					ans += st.size();
				else
					ans += (m[temp] + 1);

				m[temp] ++;
			}
			else {
				m[temp] = (m[temp] == 0) ? 1 : m[temp] + 1;
				ans += 1;
			}
		}
		else
			m[temp] = 1;

		st.push(temp);
	}

	cout << ans;

	return 0;
}

게시판에 있는 반례가 다 맞았는데 틀렸다면 ans 자료형이 틀렸을 가능성이 크다.

 

 

Python)

import sys
read = sys.stdin.readline

n = int(read().rstrip())
st = []
ans = 0
dict = {}

for _ in range(n):
    temp = int(read().rstrip())

    while st and st[-1] < temp:
        dict[st[-1]] = dict[st[-1]] - 1
        st.pop()
        ans += 1
        
    if st:
        # 스택의 top과 입력 값이 같고
        if st[-1] == temp:
            # 스택의 길이와 입력 값의 갯수가 같다면
            if len(st) == dict[temp]: # ex) 2 2 2 2 / 2
                ans += len(st)
            # 다르면
            else: # ex) 5 4 2 2 / 2
                # 4 2 2 / 2 만 더해주기
                ans += (dict[temp] + 1) 

            dict[temp] = dict[temp] + 1
        else :
            dict[temp] = (dict[temp] + 1) if temp in dict else 1
            ans += 1
    else:
        dict[temp] = 1

    st.append(temp)

print(ans)

 

 

이 정도면 된 것 같는데 왜 틀렸지 싶을 때 넣은 반례)

5

3

2

2

1

2

 

정답 : 8