20240411(프로그래머스 n+1카드, 파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/258707

프로그래머스

 

먼저 while등 반복문 사용 시 종료되는 조건을 생각하고 해야함.

 

 

아이디어

round가 종료되는 경우

1. round시작 시 받을 카드가 없을 경우

2. round끝날 시 가지고 있는 두 카드의 합이 n+1이 되는 카드가 없을 경우

 

 

 

i카드와 합이되어 n+1이 되는 카드는 n+1-i밖에 없음을 생각

 

i카드를 뽑을 때 만약 n+1-i카드를 가지고 있다면(이건 최초에 n/3개 뽑을 때만 존재), 항상 살 수 있도록 함(코인 1개 소모)

n+1-i카드가 없다면, 일단 n+1-i카드가 있었다고 기록함

 n+1-i카드가 최초 뽑을 때는 없었지만 카드 기록이 있었다고 한다면, 2개의 코인을 소모해서 한 라운드를 벌 수 있는 기회가 생김

 

이러한 아이디어를 기준으로

뽑은 기록과 소지한 카드 기록은 리스트의 index를 통해서 바로 조회할 수 있도록 만들어서 시간을 줄임

 

 

 

 

def solution(coin, cards):
    co = coin
    life = 0
    answer = 0
    n = len(cards)
    exist_card = [0] * (n+1) # 1 최초 소지 카드
    possible_card =  [0] * (n+1) # 사지는 않았지만 나왔던 것, life < 0 이되는 순간 정리 (일단 1개)
    possible_life = 0
    r = 0
    
    for i in range(0,int(n/3)):
        exist_card[cards[i]] = 1
        if exist_card[n-cards[i]+1]:
            life += 1
    
    while life >= 0:
        r += 1
        if int(n/3 + 2*r -1) >=n: # 뽑을 것 없을 때
            return r
            break
        nc1, nc2= cards[int(n/3+2*r-2)], cards[int(n/3+2*r-1)]
        if  exist_card[n + 1 - nc1]:
            if co >= 1:
                co -= 1
                life += 1    
        else:
            if possible_card[n + 1 - nc1]:
                possible_life += 1
            else:
                possible_card[nc1] = 1
        
        if  exist_card[n + 1 - nc2]:
            if co >= 1:
                co -= 1
                life += 1    
        else:
            if possible_card[n + 1 - nc2]:
                possible_life += 1
            else:
                possible_card[nc2] = 1
        
        life -= 1
        
        if life < 0 and possible_life >= 1:
            if co >= 2:
                co -=2
                life += 1
                possible_life -= 1
        
    
    return r