코딩테스트 복기 - 당장 행동하지 않고 나중에 필요할 때 행동하는 그리디 알고리즘 테크닉

1. 문제

 

코딩테스트 연습 - n + 1 카드게임 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

2. 풀이

 

무작위로 뒤섞인 1부터 n까지 카드가 n장 있고, coin개의 동전을 가지고 있는데 처음에 n/3장을 가지고 시작

 

각 라운드가 시작할때 카드를 2장 뽑는데 카드 1장당 동전 1개를 소모해서 가지거나 버릴 수 있다

 

가지고 있는 카드에 적힌 수의 합이 n+1이 되도록 카드 2장을 내고 다음 라운드로 넘어간다.

 

카드를 내지 못하거나 모든 카드를 뽑아 더 이상 뽑을 수 없으면 게임 종료

 

게임을 가장 길게 할려면 당연히 동전을 최대한 늦게 쓰는게 제일 좋을 것

 

게임 그대로 구현하자니 카드를 뽑은 순간, 이 카드를 버려야할지, 이 카드를 가지고 가야할지 결정하는게

 

미래에 어떻게 될지 모르는데, 동전을 버리고 가지고가야하나?

 

나중에 당장 필요할때, 이 지점으로 되돌아와서 카드를 가지고 다시 진행해야하나? 까다롭다.

 

 

이 문제의 핵심은 게임 설명 그대로 구현하지 않는 것에 있다

 

당장 뽑은 카드를 버릴지, 카드를 가지고 갈지 결정하지 말고 뽑은 카드는 일단 임시 배열에 저장해둔다.

 

여기서 현재 가지고 있는 카드는 처음에 뽑은 n/3장의 카드.

 

카드를 새로 뽑을때마다 일단 가지지는 않고 임시 배열에 저장

 

그리고 현재 가지고 있는 카드 중에서 최대한 동전을 쓰지 않고 n+1이 되면 카드를 버리도록 한다.

 

버리는데 성공하면 다음 라운드로 넘어가면 된다.

 

1라운드,2라운드,3라운드.. 계속 넘어가다보면... 어느 k라운드에서는 가지고 있는 카드만으로는 n+1이 되도록 낼 수는 없다.

 

그럴 때 현재 가지고 있는 카드 1장과 지금까지 저장해둔 임시 배열에서 1장으로 n+1이 되도록 낼 수 있는지 확인해본다.

 

 

그게 가능하다면.. 지금 이 시점에서 임시 배열에서 그 카드 1장을 동전 1개를 소모해서 가지고 와서 

 

현재 가지고 있는 카드 1장과 함께 버리면 된다.

 

프로그래밍 입장에서는 해당하는 '임시 배열의 그 카드'가 p (< k)라운드에서 뽑혔더라도 k라운드에서 가지고 와서 버려도 괜찮다.

 

그냥 p (<k)라운드에서 가지고 왔다고 치면 그만이니까

 

실제 현실에서는 과거로 돌아가는건 불가능하잖아..

 

하지만 프로그래밍 입장에서는 당장 카드를 버릴지 가지고갈지 결정하지 말고,

 

나중에 필요하다면 그 때 가서 결정한다면.. 과거에 한거로 치면 되니까 괜찮다.

 

 

이러한 테크닉에 입각해서 '현재 가지고 있는 카드'와 '임시 배열에 저장해둔 카드'를 모두 조합해서 n+1이 되는게 불가능하면

 

이제는 동전 2개를 소모해서 '임시 배열에 저장해둔 카드' 2장으로 n+1이 되는지 체크해본다

 

이게 가능하다면 이 때는 동전 2개를 소모해서 임시 배열에 저장해둔 카드 2장을 써서 n+1을 내면 된다

 

이것조차도 불가능하다면.. 더 이상 n+1을 만드는게 불가능하므로 게임을 종료하면 된다

 

-------------------------------------------------------------------------------------------------------------------------------------------------

 

1) A배열과 B배열을 다음과 같이 정의

 

A배열 = 처음 n/3장 카드를 뽑아 저장

 

B배열 = 라운드마다 뽑은 카드 2장씩 계속 저장

 

2) 매 라운드마다 카드 2장을 뽑고 B배열에 저장

 

3) 먼저 A배열의 카드 2장으로 n+1이 되는지 체크한다. 가능하다면 이 2장을 버리고 다음 라운드로 진행하고 2)로 돌아감

 

불가능하다면 4)로 넘어감

 

4) 3)이 불가능하다면, 동전이 1개 이상인지 검사.

 

동전이 1개 이상이 아니라면 게임 종료.

 

동전이 1개 이상이라면 A배열의 카드 1장과 B배열의 카드 1장으로 n+1이 되는지 체크. 

 

가능하다면 동전 1개를 소모하고 A배열의 해당 카드 1장, B배열의 해당 카드 1장을 버리고 다음 라운드로 진행하고 2)로 돌아감

 

불가능하다면 5)로 넘어감

 

5) 4)가 불가능하다면, 동전이 2개 이상인지 검사.

 

동전이 2개 이상이 아니라면 게임 종료

 

동전이 2개 이상이라면 B배열의 카드 2장으로 n+1이 되는지 체크

 

가능하다면 동전 2개를 소모하고 B배열의 해당 카드 2장을 버리고 다음 라운드로 진행하고 2)로 돌아감

 

이것도 불가능하다면 게임 종료

 

6) 더 이상 카드뭉치에서 카드를 뽑을 수 없으면 게임 종료

 

from collections import deque

def solution(coin, cards):
    answer = 0
    
    A = [] #처음에 뽑은 카드 n/3장 저장해두는 배열
    B = [] #매 시작마다 뽑는 카드 2장을 저장해두는 배열
    cards = deque(cards)
    
    n = len(cards)
    
    #처음에 n/3장을 가지도록 카드 보유
    while len(A) < n//3:
        A.append(cards.popleft())
    
    
    while 1:
        
        answer += 1 #라운드 시작
        
        if len(cards) == 0: #더 이상 뽑을 카드가 없는 경우 게임 종료
            break
        
        #카드 뭉치 위에서 카드 2장을 뽑는다
        a = cards.popleft()
        b = cards.popleft()
        
        #카드 뽑으면 임시 배열 B에 저장
        B.append(a)
        B.append(b)
        
        #n+1을 낼 수 있는지 체크
        find = False
        
        #첫번째, 가지고 있는 카드만으로 n+1을 낼 수 있는 경우
        for i in range(len(A)):
            
            for j in range(i+1,len(A)):
                
                if A[i]+A[j] == n+1:
                
                     #i < j이므로 i번째 원소 제거했으면, j번째 원소는 j-1번째가 된다
                    del A[i]
                    del A[j-1]
                    find = True
                    break
            
            if find:
                break
        
        #첫번째가 불가능한 경우
        if find == False:
            
            #두번째, 동전이 1개 이상일때,
            if coin >= 1:
                
                #가지고 있는 카드 A와 임시로 저장해둔 B에서 1장씩 사용해서 n+1이 되는지 체크
                for i in range(len(A)):
                    for j in range(len(B)):

                        if A[i] + B[j] == n+1:
                            
                            del A[i]
                            del B[j]
                            find = True
                            break
                    
                    if find:
                        break
                
                if find:
                    coin -= 1 #가능하다면 동전 1개 쓰고 다음으로
                
                #두번째가 불가능한 경우,
                else:
                    
                    #세번째, 동전 2개 이상일때,
                    if coin >= 2:
                        
                        #임시로 저장해둔 배열 B에 저장된 카드 2장으로 n+1이 되는지 체크
                        for i in range(len(B)):
                            for j in range(i+1,len(B)):

                                if B[i] + B[j] == n+1:
                                
                                #i < j이므로 i번째 원소 제거했으면, j번째 원소는 j-1번째가 된다
                                
                                    del B[i] 
                                    del B[j-1]
                                    find = True
                                    break

                            if find:
                                break
                        
                        if find:
                            coin -= 2 #가능하다면 동전 2개 쓰고 다음으로 넘어감
                        
                        #여기마저도 불가능하다면 게임 종료
                        else:
                            break
                    
                    #동전이 2개 이상이 아니면 게임 종료
                    else:
                        break
            
            #동전이 1개 이상이 아니면 게임 종료
            else:    
                break        
    
        
    return answer

 

 

 

배열의 원소를 del로 삭제했는데 O(N)이라 조금 그럴 수 있다면

 

1) visited로 삭제한 원소면 인덱스를 표시해서 표시된 인덱스인지 검사하는것을 체크하거나

 

2) A,B를 dict로 구현해서 key를 삭제하면 O(1)이라 괜찮을수도 있지만

 

n 제한이 1000이라 작아서 그런지 if문을 많이 검사하고, hash때문에 그런건지 del보다 오히려 느리더라

 

n이 크다면 위 사항을 충분히 고려해볼만함