직장인의 개발 일기

https://www.acmicpc.net/problem/3015

[ 문제풀이 ]

stack이라는 자료구조를 사용하면 쉽게 풀 수 있는 문제입니다.

항상 스택 안에는 키가 큰 순서로 정렬이 되게끔 만들어서 쌍을 구하는 방법으로 풀었습니다. 따라서 3개의 분기로 나누어야 합니다.

1. stack.top() < cur

먼저 내 앞에 있는 사람의 키가 나보다 작다면 나는 내 앞에 있는 사람보다 더 앞에 있는 사람을 볼 수 있습니다. 따라서 나보다 더 작은 사람을 stack에서 pop 해주고 ans에 키가 같은 사람의 수만큼인 cnt를 더해주면 됩니다. while을 통해 나보다 앞에 있는 사람 중 나보다 작은 사람들을 모두 pop 해주면 마지막에는 나보다 큰 사람이 내 앞에 있게 됩니다.

2. stack.top() == cur

만약 내 앞에 있는 사람이 나와 키가 같다면 내 앞에 키가 같은 사람의 수만큼 ans에 더해주고 cnt를 나를 포함한 같은 키를 가진 사람의 수만큼 갱신해줍니다. 이때 나보다 큰 사람이 존재한다면 stack의 사이즈가 1보다 크므로 사이즈가 1보다 클 때는 ans에 1을 한번 더 더해줍니다.

3. stack.top() > cur

만약 내 앞에 있는 사람이 나보다 키가 크다면 그 사람보다 앞에 있는 사람을 나는 볼 수 없기 때문에 ans에 1을 더해주면 끝이 납니다.

2
4
1
2
2
5
1

1. 위를 예로 들면 먼저 stack에 2가 들어갑니다.

ans = 0

2. 그리고 다음 수 4가 들어갈 때 stack.top() 보다 4가 더 크므로 stack을 pop 해주고 ans에 1을 더해준 후 4를 stack에 넣어줍니다.(1번 분기)

ans = 1

3. 그리고 1은 stack.top()인 4보다 작으므로 ans에 1을 더해준 후 push 합니다.(3번 분기)

ans = 2

4. 다음으로 들어올 수는 2인데 stack.top() 보다 크므로 stack을 pop 해주고 ans에 1을 더해준 후 push 해줍니다. (1번 분기)그리고 4는 2보다 크므로 ans에 1을 더해줍니다.(3번 분기)

ans = 4

4의 cnt = 1

2의 cnt = 1

5. 또 2라는 수가 들어오는데 stack.top()과 같은 수이므로 ans에 같은 수가 존재하는 만큼(1)을 더해주고, cnt에 나를 포함한 같은 수가 존재하는 만큼 갱신해줍니다. 또한 size가 1보다 크므로 ans에 1을 더해줍니다.(2번 분기)

ans = 5

4의 cnt = 1

2의 cnt = 2

6. 다음으로 들어올 수는 5입니다. while문을 통해서 나보다 더 작은 키를 가진 사람들을 pop 해주면서 cnt를 더하면 됩니다. 2의 cnt = 2, 4의 cnt = 1이므로 ans에 3을 더해줍니다.(1번 분기)

ans = 9

7. 마지막으로 1이 들어오면 stack.top()인 5보다 작으므로 ans에 1을 더해주면 됩니다.(3번 분기)

ans = 10

[ 소스 코드 ]