정올 1141: 불쾌한 날 풀이

Question

문제 링크

How

그냥 단순하게 앞의 소부터 뒤의 소를 전부 검색하면 시간 초과로 인해 통과가 안된다. 그래서 아래와 같이 최소한으로 list 를 검색하도록 해야 한다.

아래와 같은 로직으로 풀었다.

• Stack 에 소를 넣을 때, 현재 들어오는 소보다 작은 소들은 Stack 에서 전부 뺀다. 그리고 Stack 에 남은 소들의 개수를 결과 변수에 더해준다.
• 이렇게 진행할 경우, Stack 의 소들은 항상 정렬되어 존재한다.
• 앞에서부터 소를 한마리씩 넣으면, 해당 소보다 키가 큰 소만 현재 들어오는 소를 볼 수 있기 때문에 작은 소들은 버리는 것이다.
• Java 로 풀었을 때 위의 로직만으로는 시간제한을 어기게 된다. 그래서 현재 들어오는 소보다 키가 작은 소의 위치를 찾을 때, 앞에서부터 찾을 것인지 뒤에서부터 찾을 것인지를 미리 판단해서 조회 방향을 다르게 했다.

문제에 예시를 보면 [5, 2, 4, 2, 6, 1] 크기의 소들이 있다. 앞에서부터 Stack 에 넣고 위의 로직으로 처리하는 경우, Stack 과 결과값은 아래와 같다.

1. S [5] and Result 0
2. S [5, 2] and Result 0+1=1
3. S [5, 4] and Result 1+1=2
4. S [5, 4, 2] and Result 2+2=4
5. S [6] and Result 4+0=4
6. S [6, 1] and Result 4+1=5

이래서 답은 5가 된다.

주의할 사항은 결과값은 long type 의 변수이여야 한다. Python 3.x 의 경우는 int 가 long 이므로 별도로 지정할 필요가 없다. 그리고 같은 크기의 소들이 연속으로 들어오기도 하는데, 이런 경우 뒤의 소는 앞의 소를 볼 수 없다.

Answer

# Input
# n = input()
# cowList = []
#
# for i in range(n):
#     cowList.append(long(input()))

# Sample input
n = 6
cowList = [5, 2, 4, 2, 6, 1]

# Make stack for calculate
cowInput = []
result = 0

for i in range(n):
    # firstTaller: Index of first value which larger than current input cowList[i]
    firstTaller = -1

    # Set direction to search, True is -> and False is <-
    travelDirection = True if len(cowInput) < 3 or abs(cowInput[0] - cowList[i]) < abs(cowInput[-1] - cowList[i]) else False
    travelNum = []

    if travelDirection:
        travelNum = range(len(cowInput))
    else:
        travelNum = range(len(cowInput)-1, -1, -1)

    # Find firstTaller
    for j in travelNum:
        if cowInput[j] < cowList[i]:
            firstTaller = j
            break

    # Add to the result and reset stack status
    if firstTaller != -1:
        result += firstTaller
        cowInput = cowInput[:firstTaller]
    else:
        result += len(cowInput)

    cowInput.append(cowList[i])

# Print result
print(result)