https://www.acmicpc.net/problem/2493
무슨 말인지는 금방 이해했는데 코드화를 어떻게 시키면 좋을까에 대한 고민이 많았다.
다행히 몇 개의 반례말고는 온전히 내 손으로 해결한 케이스. (몇 없는..)
처음엔 이렇게 생각했다
- 입력을 받는대로 스택에 넣는다.
- 스택에서 비교 할 대상을 꺼낸다. 이제 다음으로 꺼내는 원소와 비교를 할 것이다.
- 2번에서 비교 할 대상으로 꺼낸 첫 아이템보다 큰 원소가 나오는 경우, 지금까지 나온 탑들의 수령지를 지금 나온 원소로 지정한다.
지금 정리해보니 말이 안된다. 이게 가능하려면,
2번에서 3번으로 넘어오던 중에 꺼내는 아이템이 2번에서 처음 꺼낸 아이템보다 순차적으로 적어져야한다.
꺼낸 순으로 적어보겠다. 9 8 7 6을 하다가 7이 나오면? 그럼 6 입장에서는 지금 막 나온 7이 레이저 신호 수령 타워가 되지 않을까?
하지만 위의 논리 대로 하면 10이 나와야 한다는 말이 된다.
그래서 꺼내 온 수 보다 더 큰 숫자가 나타나면 즉시 적용 하는 루틴을 추가 했다.
그러니 이에 대한 반례가 없을 정도로 결과가 깔끔해졌다.
import sys
topCnt = int(sys.stdin.readline())
topField = list(map(int, sys.stdin.readline().strip().split()))[:topCnt]
resultArr = [0] * 500001
compareField = []
while len(topField) != 0:
item = topField.pop()
itemPos = len(topField) + 1
canContinue = True
while canContinue:
if(len(compareField) == 0):
itemPair = (item, itemPos)
compareField.append(itemPair)
canContinue = False
continue
else:
if(compareField[len(compareField) - 1][0] < item):
resultApply = compareField.pop()
resultArr[resultApply[1]] = itemPos
else:
itemPair = (item, itemPos)
compareField.append(itemPair)
canContinue = False
for i in range(1, topCnt + 1):
print(str(resultArr[i]) + " ", end="")
#compareField.top의 높이..랑 같은 내용
topField가 모든 탑의 입력을 받고, compareField에 잠깐 꺼내두는 형태를 생각했다.
canContinue로 세션을 구분 짓고, compareField의 내용이 이미 있는지 없는지에 따라 작동 루틴을 다소 구분했다.
'문제풀이' 카테고리의 다른 글
[PY] 10830 : 행렬 제곱 (0) | 2025.03.26 |
---|---|
[PY] 6549 : 히스토그램에서 가장 큰 직사각형 (0) | 2025.03.26 |
[PY] 8983 : 사냥꾼 (0) | 2025.03.25 |
[PY] 2470 : 두 용액 (0) | 2025.03.25 |
[PY] 17608 : 막대기 (0) | 2025.03.24 |