[백준][Python] 멀티탭 문제

오늘은 백준 1700번 문제입니다.

728x90

문제 설명

 

문제 해석

저는 이 문제를 보자마자 멀티탭 사용 숫자를 우선순위로 해석해서 1에 가까울 수 록 자주 쓰이고 높을 수 록 안쓰인다고 해석하기로 했습니다. 

first를 사용하기 이전에 sort해서 내림차순으로 하면 좋았겠지만 그렇게 하는게 불가능할 것 같아서 first라는 변수로 최대 숫자를 찾아내기로 했습니다.

 

문제 풀이 1차

N, K = map(int,input().split())
multitap = [0 for i in range(N)] #멀티탭
use = list(map(int, input().split())) #실제 전기용품 사용
count= 0 #사용횟수
first= 0 #비교시 우선 순위가 낮은 거 골라내기
for i in use :
    for j in range(len(multitap)):
        if i == multitap[j] or multitap[j]==0: # 사용할 제품이 이미 꽂혀있거나 멀티탭이 비어있을 때
            multitap[j] = i
            break
        elif first < multitap[j]: # 우선순위가 높을 경우
            first = j
    if first !=0:
        multitap[first] = i
        count+=1
    first=0

 

일단 답은 제가 원하는 답이 안나왔습니다...

첫번째 출력은 콘센트를 뽑은 횟수인 count이고 두번째 출력은 multitap입니다.

count는 맞지만 multitap이 틀렸습니다. 정상적인 답이라면 [1,7]이 나와야 정상입니다.

근데 그걸 눈치 못채고 count만 보고 백준에 답을 올려보니..

ㅋㅋ 역시나 틀렸습니다..

뭔가 중간부터 틀린 것 같아서 자세히 생각해보니 first라는 변수와 multitap[j]를 비교하는 것 자체가 성립이 안되는 것을 깨달았습니다.. first는 인덱스를 저장하는 변수인데 리스트랑 비교를 하는게 말이 안되는 내용이었죠..ㅎ...

또한 first가 0일 때, 즉 multitap의 가장 첫 번째를 교체해야할 때는 조건문에 들어가지 않아서 콘센트 교체가 이뤄지지 않습니다.

그래서 3차 풀이에는 big이라는 변수를 추가해주고 마지막 조건문을 수정하여 작성을 하게 되었습니다.

문제 풀이 2차

N, K = map(int,input().split())
multitap = [0 for i in range(N)] #멀티탭
use = list(map(int, input().split())) #실제 전기용품 사용
count= 0 #사용횟수
first= 0 #비교시 우선 순위가 낮은 거 골라내기
big=0
for i in use :
    for j in range(len(multitap)):
        
        if i == multitap[j] or multitap[j]==0: # 사용할 제품이 이미 꽂혀있거나 멀티탭이 비어있을 때
            multitap[j] = i
            break
        elif big < multitap[j]: # 우선순위가 높을 경우
            first = j
            big=multitap[j]
    if first:
        multitap[first] = i
        count+=1
    elif big==multitap[first]:
        multitap[first] = i
    first=0
    big=0
print(count)

와 이번엔 제대로 나왔습니다..! 리스트 출력도 좋고 count도 맞았습니다. 그럼 호다닥 백준으로 가볼까요~?

바로 틀려버렸습니다.. 도대체 무엇이 문제였을까요.. 근데 이제 보니 리스트 출력이 이상합니다. [2,3]일 때 1로 교체하려면 3을 빼고 1을 넣어서 [2,1]이 되고 결국엔 [7,1]이 되어야하는데 리스트가 이상하게 출력되었습니다. 보니까 두번재 elif문이 이상했습니다. 저는 저걸 첫 번째 인덱스가 가장 크면서 first가 0인 경우를 염두해두고 했는데 그러면 여러번의 교체가 일어나더군요..

 그래서 결국 최후의 수단으로 코드의 길이에 상관 없이 일단 정답이라도 맞추자 해서 change라는 변수를 넣어 첫 if문에서 꽂았을 때를 제외하기로 했습니다.

 

문제 풀이 3차

N, K = map(int,input().split())
multitap = [0 for i in range(N)] #멀티탭
use = list(map(int, input().split())) #실제 전기용품 사용
count= 0 #사용횟수
first= 0 #비교시 우선 순위가 낮은 거 골라내기
big=0
for i in use :
    for j in range(len(multitap)):
        change=1
        if i == multitap[j] or multitap[j]==0: # 사용할 제품이 이미 꽂혀있거나 멀티탭이 비어있을 때
            multitap[j] = i
            change=0
            break
        elif big < multitap[j]: # 우선순위가 높을 경우
            first = j
            big=multitap[j]
    if change:
        multitap[first] = i
        count+=1
    first=0
    big=0
print(count)

네 제가 말씀드렸던 대로 나왔죠? [7,1] 그래서 부푼 마음을 안고 백준한테 가보았지만 가차 없이..

하.... 도대체 나한테 원하는게 뭐야.... 이정도 했으면 그냥.. 통과시켜줘.....

그래서 백준 질문방에서 반례를 찾아서 넣어보았습니다.

다 틀리게 나왔습니다.. 물론 간간히 맞는 것도 있었지만 반례를 넣었을 때 다 맞아야 맞는 코드 이기 때문에 제 코드는 틀린 코드입니다. 곰곰히 생각을 해보니 이 문제는 사실 앞으로 많이 쓰일 것 같은 전자제품을 냅두고 나머지 중 가장 안쓰이는 것을 뽑아야하는 문제입니다. 따라서 제가 문제 해결을 위해 고안한 우선 순위는 애초에 문제에 맞지 않는 풀이라는 것을 알게 되었습니다.

결과

문제를 잘못 해석하여서 발생한 문제로 정말 한심했습니다.. 많은 시간을 소비했으므로 이 문제는 틀린 것으로 간주하고 구글링을 통해 학습하기로 했습니다. 찾아보니 이 문제는 그리디 알고리즘으로 해석하고 풀어야하는 문제입니다. 저는 따로 알고리즘은 배우지 않고 자료구조에서 그쳤는데 알고리즘을 다시 시작해야하나 생각하게 되는 문제였습니다..