백준 3015 오아시스 재결합 파이썬 반례 설명 및 테스트케이스 공유

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

3015번: 오아시스 재결합

입력받은 배열 1개, stack배열 1개를 만들어서 풀었다.

원래 같은 숫자도 stack배열에 넣어줬는데 시간 초과가 나서 2중리스트 형태로 만들고 바로 다음이 중복되면 stack[1]+=1 해주는 형식으로 했다. (코드 보면 한번에 이해 가능) [숫자,중복된 횟수]

 

from collections import deque
import sys
input=sys.stdin.readline
n = int(input())
s=deque()#입력받은 숫자를 저장할 배열
stack = deque()#stack으로 사용할 배열, [숫자,중복된 횟수], 
re = 0#결과
for _ in range(n):
    s.append((int(input())))
  
while s:
    if not stack:
        stack.append([s.popleft(),1])#배열이 비었음으로 s배열에서 하나 뽑아줌
        #배열이 비는 경우: 처음, le리스트에 있는 모든 숫자보다 큰 수가 들어오면 밑에 코드로 인해 le배열이 비어짐
    elif stack[-1][0]<=s[0]:#
        if stack[-1][0]==s[0]:
            s.popleft()#리스트에서 하나를 빼준다.
            re+=stack[-1][1]#앞에 숫자가 같으아 모두 볼 수있으므로 나왔던 만큼 더해준다.
            
            if len(stack)>1:#그 다음 숫자가 4번 중복이여도 조건에따라 끝에 숫자만 가능하므로 +1만 해준다.
            	#ex) 6,6,6,5,2,5일때 마지막 5는 6,6,"6,5,2"만 볼 수 있다. 앞에 6,6은 못 본다
                re+=1
                
            stack[-1][1]+=1#중복되는 숫자가 나온것이므로 le[-1][1]+=1을 해준다.
            
        else:
            while stack[-1][0]<s[0]:#s[0]이 le의 모든 수 보다 크면 le배열은 비어진다.
                t=stack.pop()
                re+=t[1]# le는 비내림차순으로 정렬되어 있어서 중복된 숫자 모두 더해주면 된다.
                if not stack:#비어있으므로 종료
                    break
    else:
        re+=1# 우선은 바로 옆에만 볼 수 있다.
        stack.append([s.popleft(),1])#stack배열의 가장 작은 수 보다 더 작은 수가 왔으므로 추가해준다.
        
print(re)

아래는 반례입니다.

3
3
2
1

답: 2

3
2
2
2

답: 3

5
5
2
2
2
5

답: 10

6
6
6
6
5
2
5

답: 8

밑에는 대회때 사용된 테케이다.

테케.zip

0.00MB

테케 3에서 답: 17144인데 답이 17156이 나온다면 문제를 다시 읽어 보는 것을 추천한다. 주석에도 설명했지만 6,6,6,5,2,5 에서 마지막 5는 6,2,5밖에 못 본다.