[Python] 백준, 17298(스택)

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

17298번: 오큰수

슬슬 스택 자체는 감이 온다. 답을 제출하기 전 돌려보는 예시들도 대게 정답을 return 하는 수준에는 온 것 같은데, 두 가지가 아직 깔끔하지 않다.

 

첫 번째는 시간 복잡도이다. 대략적으로 시간 복잡도를 계산하는 방법은 알고 있다만, 문제를 풀 때 이를 적용시키는 부분에 대해서는 아직 잘 이해가 안 간다. 문제를 풀 때도 이를 고려하지 않다 보니, 뭔가 힌트가 될 여지 하나를 놓치며 접근하는 것 같아 굉장히 껄끄럽다.

 

두 번째는 깔끔한 정도이다. 기본적인 함수나 모듈들은 다양한 문제를 풀다 보니 슬슬 체화가 되어가는데, 맞은 사람들의 코드와 비교해 봤을 때 아직 상대적으로 코드의 깔끔함이 부족하다. 단순히 경험 부족일까? '프로그래머로 사는 법'이라는 책에서는 좋은 멘토를 만났을 때의 코딩 실력이 비약적으로 상승할 것이라는 내용이 등장하던데, 독학은 여전히 힘들다.

 

코딩 실력 하나만으로 누군가의 멘토가 되어주고 싶어진다....

 

 

# PYTHON CODE (1)

import sys
 
n = int(sys.stdin.readline())
stk1 = list(map(int, sys.stdin.readline().split()))
stk2 = []
answer = []
 
for _ in range(n):
    is_break = False
    k = stk1.pop()
    if not stk2:
        answer.append(-1)
        stk2.append(k)
    else:
        for i in stk2[::-1]:
            if k < i:
                answer.append(i)
                stk2.append(k)
                is_break = True
                break
        if not is_break:
            answer.append(-1)
 
print(*answer[::-1])

정답은 맞았지만 기다리는 건 시간 초과...

 

처음 목표는 스택을 이용은 하되, 메인이 되는 방향은 아니긴했다. 필연적으로 탐색이 필요하다고 생각했고, 이진 탐색은 적합하지 않은 것 같아 트리나 선형 탐색이지 않을까 판단하여 선형 탐색으로 작성해봤다. (최악의 경우가 작성하는 내내 머릿속에서 떠나지 않긴 했다..)

 

어쨌든 틀릴 수는 없는 코드였다.

마지막 줄은 원래 for문이었는데, *의 활용도를 새로 학습해서 저렇게 바꿨다. 훨씬 간결하고 보기 좋은 것 같다. 

오히려 join함수를 쓰는 것보다 나은 것 같은데, 시간 복잡도 측면에서도 차이가 크게 날지는 모르겠다.

 

 

# PYTHON CODE (2)

import sys
 
n = int(sys.stdin.readline())
stk1, stk2 = list(map(int, sys.stdin.readline().split())), []
answer = [-1] * n
 
for i in range(n):
    while stk2 and stk2[-1][0] < stk1[i]:
        trash, idx = stk2.pop()
        answer[idx] = stk1[i]
    stk2.append([stk1[i], i])
 
print(*answer)

세대의 교체는 3세대 단위로 진행된다고 한다. 새로운 문화가 완전히 자리잡기까지 무려 3세대가 지나야 한다는 말이다. 

 

지난번 스택 문제 풀이가 위의 풀이와 흡사했는데 이걸 풀면서 알아보지 못한걸 보면 나한테 스며들기까지도 시간과 노력이 더 필요한가보다. 맨날 스택만 잡고 있어서 느껴지는 건지는 모르겠는데, 세세한 부분은 물론 다르지만 틀은 꽤나 비슷하다는게 느껴져서 씁쓸하다.

 

zip이나 enumerate로 index를 처리해야겠다고 생각은 했었는데, 위의 것도 좋은 것 같다. 

문득 stk1[i]의 값을 return 할 때 1부터 i까지 값들을 증가시켜 stk1[i]를 return 하는 건지, dic메서드처럼 쓱 뱉어내는 건지 헷갈려졌다. 아마 후자일 것 같긴 한데...

 

어쨌든 풀이는 너무 좋다. 조금 시각만 다르게 해도 이런 풀이가 가능하다는 걸 항상 명심하도록.