[Baekjoon]백준 3015 오아시스 재결합(플래티넘 5) - Python

문제설명

예제

문제를 살펴보면 서로 볼 수 있는 사람의 수를 구해야한다

문제를 제대로 이해하기 위해 총 몇 쌍이 나오는지 직접 구해보았는데, 

(2, 4), (4, 1), (4, 2), (4, 2), (4, 5), (1, 2), (1, 2), (2, 2), (2, 5), (5, 1) 이렇게 총 10개이다(앞에서부터 정렬)

즉, 마주보고 있는 사람도 포함하되, 중간에 위치한 사람의 키가 크지 않은 경우도 동시에 계산해야한다

 

스택을 1차원으로 해결해보려고 했는데 도저히 방법이 생각이 안 나서 찾아보았다

검색을 해보니 2차원으로 사용하는 방법이 대부분이었고, 현재 키와 개수를 스택에 넣는 방법을 사용하였다

stack에는 키와 해당 키의 개수를 저장하고, total_views에는 총 시야의 개수,

cnt에는 같은 키를 가진 사람의 수를 저장하도록 설정하여 코드를 작성하였다

 

for문을 돌면서 해당 index를 확인하고 스택의 top에 위치한 값이 현재 키보다 작거나 가으면 pop을 하게 된다

그리고 pop된 키의 개수를 결과에 더하고, pop한 결과가 현재 키와 같다면 cnt를 증가한다

스택이 비어있지 않으면 추가적으로 +1을 수행하는데, 이는 더 큰 키를 가진 사람을 볼 수 있다는 뜻이다

i	height	stack 변화 과정	total_views
0	2	[(2,1)]	0
1	4	[(4,1)] (2 pop)	1 (2를 제거하며 1 증가)
2	1	[(4,1), (1,1)]	2 (4을 볼 수 있음)
3	2	[(4,1), (2,1)] (1 pop)	4 (1을 제거하며 1 증가, 4도 볼 수 있음)
4	2	[(4,1), (2,2)]	6 (이전 2와 같은 키로 추가, 2 증가)
5	5	[(5,1)] (2,2,4 pop)	9 (2+2=4, 4=1 → 총 3 증가)
6	1	[(5,1), (1,1)]	10 (5를 볼 수 있음)

보기 좋게 동작과정을 표로 표시하였다(오류가 있다면 댓글로 알려주시면 감사하겠습니다)

플래티넘 문제라 그런지 푸는 내내 머리가 복잡해졌던 것 같다 추후에도 다시 복습해보아야겠다