[백준][Python] 17299. 오등큰수

반응형

 

 

 

 

 

 

🙆‍♂️문제

---

 

🙋‍♂️풀이

---

오큰수 문제와 비슷하지만 오큰수문제는 오른쪽에 있는 수 중 가장 왼쪽에 있는 가장 큰 수였다면

오등큰수는 값이 큰 것이 아닌 등장 수가 가장 많은 수 중 가장 왼쪽의 수 입니다. 없는 경우 -1을 출력합니다.

 

🚀 입력받기

---

from collections import Counter
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

배열 속 요소를 세야하기 때문에 collections의 Counter함수를 사용합니다.

 

🚀 문제 풀이 핵심

---

cnt = Counter(arr)
stack = []
answer=[]
for i in range(n):
    answer.append(-1)
for i in range(n):
    if len(stack) == 0:
        stack.append(i)
    else:
        while 1:
            if cnt[arr[i]] > cnt[arr[stack[-1]]]:
                answer[stack[-1]] = arr[i]
                stack.pop(-1)
                if len(stack)==0:
                    stack.append(i)
                    break
            else:
                stack.append(i)
                break

각종 리스트를 초기화 해주고

cnt로 arr의 배열들의 요소를 Count화 합니다.

 

stack 리스트는 말 그대로 stack으로 사용하여 값 비교 때 사용합니다.

answer 리스트는 답이되는 부분을 append하는 리스트입니다.

 

 

from collections import Counter

arr = [1,2,3,4,1,1,1,2,3,3,2]

counter = Counter(arr)

print(arr)
print(counter)
print(dict(counter))

Counter함수의 간단 예시를 확인해보면 이런 출력을 한다면

이렇게 출력됩니다.

counter[값]을 하면 딕셔너리 처럼 해당 값이 출력됩니다.

 

본론으로 다시 돌아와서 얘기해보면

for i in range(n):
    answer.append(-1)

answer 리스트의 모든 값을 -1로 초기화 시켜줘서 조건에 맞지 않다면 -1로 둡니다.

 

for i in range(n):
    if len(stack) == 0:
        stack.append(i)

먼저 stack 리스트의 길이가 0이라면 즉 아무 값도 들어간 상태가 아니라면

해당 인덱스의 값을 stack에 넣습니다.

 

    else:
        #스택 사용
        while 1:
            if cnt[arr[i]] > cnt[arr[stack[-1]]]:
                answer[stack[-1]] = arr[i]
                stack.pop(-1)
                if len(stack)==0:
                    stack.append(i)
                    break
            else:
                stack.append(i)
                break

스택의 길이가 0이 아니라면

해당 인덱스의 값이 stack에 들어간 값보다 빈도수가 많다면

스택에 저장됐던 값의 answer 값을 현재 값으로 바꿔줍니다.

(왜냐하면 이게 오른쪽에 있는 거 중에 제일 많이 등장한 가장 좌측 수 이기 때문)

 

그래고 stack.pop(-1)로 마지막 스택 값을 지워주고 지웠을 때 값이 0이라면 현재 값의 인덱스를 stack에 추가해줍니다.

이렇게 지워주기 때문에 가장 왼쪽 수가 되어야 하는 문제도 해결됩니다.

그리고 if문이 거짓이 되거나 stack을 초기화 할 정도로 값이 나올 때 까지 while문으로 진행합니다.

 

if문이 거짓일 때는 그냥 stack에 현재 index를 추가합니다.

 

 

🚀 출력하기

---

for i in answer:
    print(i,end=" ")

answer list에 저장한 값을 print문을 통해 출력합니다.

728x90