백준(BOJ) 1881 공 바꾸기(Python)

문제 내용

 

그리디 문제.

뽑은 카드에 적힌 숫자의 공이 박스에 들어있다면 pass, 그렇지 않다면 박스에 공을 넣어야 하는데, 빈 박스가 존재한다면 바로 박스에 넣었다고 공의 상태를 갱신하고, 없다면 현재 박스에 있는 공 중 하나를 뺀 다음 넣어야 한다.

박스에 공이 들어있는 지는 단순한 0-1 리스트로 나타냈다.

교환 연산을 해야하는 경우 어떤 공을 뺄 것인지에 대해 그리디한 방식을 써야 하는데, 현재 박스에 들어있는 공 중 앞으로 카드에서 나오지 않는 공을 1순위, 가장 나중에 등장하는 공을 2순위로 두고 그 공과 교환 연산을 진행했다.

연산 횟수를 최대한 줄이기 위해서는 박스 안에 불필요한 공이 없어야 하는데, 앞으로 카드에서 나오지 않는 공은 박스 공간을 낭비하는 가장 큰 원인이기 때문에 1순위로 배정했다.

가장 나중에 등장하는 공 역시 위와 같은 이유인데, 이는 그 공이 등장하기 이전까지 공이 들어있는 박스 공간은 아무런 효용이 없기 때문이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
if n==0:
    print(0)
else:
    L=list(map(int,input().split()))
    X=[-1 for i in range(10)]
    Box=[0 for i in range(10)]
    for i in range(10):
        if i in L:
            X[i]=L.index(i)
    ans=0
    p=0
    for i in range(n):
        if L[i] in L[i+1:]:
            X[L[i]]=L[i+1:].index(L[i])+i
        else:
            X[L[i]]=-1
        if not Box[L[i]]:
            ans+=1
            if p<4:
                Box[L[i]]=1
                p+=1
            else:
                a=0
                k=0
                for j in range(10):
                    if X[j]==-1 and Box[j]:
                        k=j
                        break
                    if X[j]!=-1 and Box[j]:
                        if a<X[j]:
                            k=j
                            a=X[j]
                Box[k]=0
                Box[L[i]]=1
    print(ans)

 

문제를 풀면서 가장 오래 걸린 것 같다.

거의 하루종일 붙잡고 있었고, 이것 때문에 다른 문제도 잘 못 풀었다.

처음에는 뒤에 등장하는 번호의 개수가 가장 적은 공을 빼는 방식으로 풀었는데, 그렇게 한 후 틀린 뒤 반례를 물어물어 구하고 나서 방식을 위와 같이 바꿨다.

마지막에는 멘탈이 나갔었는지 다 해놓고 카드의 인덱스를 수정하는 과정에서 실수를 해서 계속 틀리고 있었다.

 

 

처참한 사건 현장

아무래도 나는 그리디가 진짜 쥐약인 것 같다.