백준3015🐨오아시스 재결합.py

백준 3015번 “오아시스 재결합” 문제는 스택을 이용하여 각 사람이 볼 수 있는 다른 사람의 쌍을 구하는 문제이다. 아래에 주어진 코드를 바탕으로 문제 풀이를 설명한다:

n, *nums = map(int,open(0).read().split())
stack = []
result = 0

for i in range(n):
    count = 1
    while stack and stack[-1][0] <= nums[i]:
        top = stack.pop()
        result += top[1]
        if top[0] == nums[i]:
            count += top[1]
    if stack:
        result += 1
    stack.append((nums[i], count))
print(result)

코드 설명

1. 초기화 및 입력 처리:
   n과 nums에 입력 데이터를 받아오고, stack과 result를 초기화한다.
2. 스택을 이용한 탐색:
   각 사람의 키를 nums에서 하나씩 순서대로 처리한다. 현재 사람의 키 nums[i]를 기준으로, 스택에 쌓인 이전 사람들 중 nums[i]보다 작거나 같은 키를 가진 사람들을 제거한다. 이 과정에서 키가 같은 사람 수를 저장하고, 그 수만큼 결과 값에 더해준다.
3. 스택 처리 후 추가 작업:
   현재 처리 중인 사람이 스택의 마지막 사람보다 크면 그 사람은 보이지 않으므로, 결과에 1을 더해준다. 이후, 현재 사람의 키와 그 사람과 같은 키의 수를 스택에 저장한다.

예제 데이터 설명

예를 들어, 입력이 7 2 4 1 2 2 5 1일 경우, 다음과 같은 과정이 진행된다:

• 첫 번째 사람 2가 들어오면 스택은 [(2,1)]이 되고 결과는 0이다.
• 두 번째 사람 4는 첫 번째 사람보다 크므로, 스택에서 2를 제거하며 결과는 1이 된다. 스택에 [(4,1)]을 추가한다.
• 세 번째 사람 1이 들어오면 스택은 [(4,1), (1,1)]이 되며, 결과는 1이 추가되어 2가 된다.
• 네 번째 사람 2가 들어오면 1이 제거되고 결과가 3이 된다. 이후 4가 보이므로 결과는 4가 되고, 스택은 [(4,1), (2,1)]이 된다.
• 다섯 번째 사람도 2이므로, 앞서 추가된 사람과 같은 키를 가진 경우를 처리하고, 결과는 5가 된다.

이와 같은 방식으로 모든 사람을 처리한 후, 최종적으로 서로 볼 수 있는 쌍의 수는 10이 된다.

이 문제의 핵심은 스택을 이용하여 현재 처리 중인 사람과 비교하며 볼 수 있는 쌍을 효율적으로 계산하는 것이다. 스택에 중복되는 키와 해당 키의 등장 횟수를 저장하여, 스택의 마지막 원소와 비교하여 처리하는 방식으로 시간 복잡도를 줄인다.

이 문제에 대한 추가적인 정보와 설명은 다음 블로그에서 확인할 수 있다:

https://justicehui.github.io/coi/2018/11/06/BOJ3015/

백준3015 오아시스 재결합

https://hyundoil.tistory.com/106

⭐⭐⭐[백준] [파이썬] [스택] 3015번: 오아시스 재결합

https://mingchin.tistory.com/425

[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 3015번 _ 오아시스 재결합

https://guru.tistory.com/27

백준 3015_Python