백준 17298 풀이 (오큰수, 스택)

처음에는 sort로 정렬을 하고 다음수를 바로 찾아내는 방법으로 풀이를 진행했다.

list : 3 5 2 7

sorted : 2 3 5 7

여기서 list에 해당하는 수를 sorted에서 찾으면 제거를 해서 출력값을 맞춰줬다. 그러나 문제는 시간이 준나게 오래걸렸다. 왜냐면 index로 어떤 수가 어디에 존재하는지 찾아야해서 연산을 너무 많이했다.

n = int(input())
tmp = list(map(int, input().split()))
stmp = sorted(tmp)
final = []
for i in tmp:
    index = stmp.index(i)
    if index != n-1 and len(stmp) != 1:
        print(stmp[index+1],end=' ')
    else:
        print(-1,end=' ')
    del stmp[index]

그래서 이번에는 로직을 더 단순하게 만들었다. 루프를 2번 돌려서 무식하게 코딩을 했으나 역시나 시간초과가 나왔다.

n = int(input())
tmp = list(map(int, input().split()))
for i in range(len(tmp)):
    big = 0
    for j in range(i+1, len(tmp)):
        if tmp[i] < tmp[j]:
            big = j
            break
    if big == 0:
        print(-1, end=' ')
    else:
        print(tmp[big],end=' ')

그래서 다른 사람 자료도 찾아보고 영상도 보면서 정리를 해보고 로직을 다시 짠 결과 문제를 해결할 수 있었다.

1. 우선 3부터 비교를 시작하는데 바로 뒤의 값이 오큰수 라면 result를 정의해준다. 따라서 3에 대해서는 5값이 들어가고, 5의 바로 뒤 값은 4이기 때문에 오큰수가 아니다. 이러한 경우 매칭이 실패했기 때문에 5의 인덱스를 스택에 넣어준다.

2. 4의 다음값은 2이기 때문에 오큰수가 아니다. 따라서 4의 인덱스를 스택에 넣어준다.

3. 2의 다음값은 7이기 때문에 오큰수이다. 이러한 경우 스택의 top값부터 인덱스 비교를 시작하여 해당 값이 7보다 작은지 큰지 비교를 한다.

4. 4보다 7이 크기 때문에 오큰수로 작용가능하다. 따라서 결과값에 7을 갱신시켜준다.

5. 스택이 비어있지 않기 때문에 남아있는 스택을 비교하여 5와 7을 비교한다.

6. 7이 더 크기 때문에 오큰수로 작용가능하다. 따라서 결과값에 7을 갱신시켜준다.

* 7은 마지막 값이기 때문에 반드시 -1이 나온다. 

** 오큰수를 찾고 스택과 비교를 하는 경우에 8과 7 처럼 매칭이 안되는 경우에는 바로 루프를 빠져나와야한다. 왜냐하면 스택에 누적된 값들은 아래층에 있을수록 값이 크기 때문에 무의미한 연산을 피해야한다.

즉, 위와 같이 10과 9가 존재할떄 스택의 탑인 9와 7을 비교해보고 매칭이 안된다면 굳이 스택의 아래로 내려가며 비교연산을 할 필요가 없다는 뜻이다.

 

이러한 방식으로 코딩을 진행했다. 깔끔한 코드는 아니지만 다행히 통과는 할 수 있었다.

n = int(input())
tmp = list(map(int, input().split()))
f = [-1 for i in range(n)]
s = []
for i in range(len(tmp)-1):
    if tmp[i] < tmp[i+1]:
        f[i] = tmp[i+1] #오큰수
        if len(s) != 0:
            slen = len(s)
            for t in range(slen-1,-1,-1):
                v = s[t]
                if tmp[v] < tmp[i+1]:
                    f[v] = tmp[i+1]
                    s.pop(t)#인덱스로 pop해줌
                else:
                    break
    else:
        s.append(i) # 찾지 못한 놈의 인덱스 넣는다.
for i in f:
    print(i, end=' ')

정말 어려운 문제였다. 단순히 자료만 저장한다고 생각했던 스택이 이런 방식으로 쓰이는게 너무나 신기했다.

내 비루한 실력이 여실히 드러나는 문제였기 때문에 참 갈길이 멀다고 느껴졌다ㅋㅋㅋ