[백준/Python] #11652 카드

문제

11652번: 카드

---

Algorithm

 우선 리스트 A에 입력값을 넣고 정렬한다. 정렬된 값이므로 숫자가 바뀌면 이전 숫자는 다시 나타나지 않는다. A의 마지막 요소부터 시작하여 현재의 숫자 a를 다른 리스트 N에 추가하고 어떤 숫자의 빈도수를 기록하는 리스트 F에 1을 추가한다. A의 다음 숫자 b가 이전에 나타난 숫자 a와 같으면 F에 저장되어 있는 마지막 수에 1을 더하고 그렇지 않으면 F에 1을 추가하고 N에 b를 추가한다. 이 때 b가 a와 다를 경우가 발생하면 a의 등장 빈도수의 계산은 끝난다. N에 등장 빈도수를 비교할 두 수가 저장되어 있다면 F를 이용해 등장 빈도수가 더 큰 수를 계산한 후 등장 빈도수가 낮은 수는 N에서 제거되고 이 수의 등장 빈도수도 F에서 제거된다. 만약 두 수의 등장 빈도수가 같다면 더 큰 수와 이 수의 등장 빈도수를 각각 N과 F에서 제거한다. 이후 같은 과정을 반복한다.

 

---

 

 

Code

input = __import__('sys').stdin.readline

N = int(input())
stack = []

for _ in range(N):
    stack.append(int(input()))

stack.sort()
numbers = [stack.pop()]
freq = [1]

while True:
    if len(stack) == 0:
        if len(freq) > 1:
            numa = numbers.pop()
            numb = numbers.pop()

            a = freq.pop()
            b = freq.pop()
            if a > b:
                freq.append(a)
                numbers.append(numa)
            elif a == b:
                if numa < numb:
                    freq.append(a)
                    numbers.append(numa)
            else:
                freq.append(b)
                numbers.append(numb)
        break
    
    n = stack.pop()
    if numbers[-1] == n:
        freq[-1] += 1
    else:
        if len(freq) > 1:
            numa = numbers.pop()
            numb = numbers.pop()

            a = freq.pop()
            b = freq.pop()
            if a > b:
                freq.append(a)
                numbers.append(numa)
            elif a == b:
                if numa < numb:
                    freq.append(a)
                    numbers.append(numa)
            else:
                freq.append(b)
                numbers.append(numb)
        numbers.append(n)
        freq.append(1)

print(numbers[-1])