[가방 퀴즈]

[문제]

1부터 n까지 번호가 붙여진 n개의 가방이 있다. 각 가방은 다른 가방에 넣을 수 있으며, 다른 가방에 들어간 가방 역시 다른 가방을 넣고 있을 수 있다. 문제의 명확성을 위해 가방 i가 가방 j의 안에 있다는 것은 가방 i가 가방 j에 직접적으로 들어있음을 의미한다.예를 들어서, 가방 2가 가방 1 안에 있고, 가방 3이 가방 2 안에 있으면, 가방 3은 가방 2 안에 있지만 가방 1 안에 있지는 않다.

모든 가방은 처음에 다 빈 채로 바닥에 놓여 있다. 우리는 다음에 나열되는 것들 중 하나의 행동을 각각 단계적으로 취할 것이다.PUT i INSIDE j - 가방 i를 가방 j안에 넣는다. 이 행동을 취하기 위해서는 가방 i와 j는 반드시 바닥에 놓여있어야 한다.SET i LOOSE - 가방 i안에 있는 모든 가방을 다시 꺼내서 바닥에 놓는다. 이 행동을 취하기 위해서는 가방 i는 반드시 바닥에 놓여 있어야 한다.

SWAP i WITH j - 가방 i와 가방 j의 내용물을 서로 바꾼다 (다시 말하면, 가방 i의 모든 내용물을 꺼내서 가방 j에 넣고, 가방 j의 모든 내용물을 꺼내서 가방 i에 넣는다).

이 행동을 취하기 위해서는 가방 i와 j는 반드시 바닥에 놓여 있어야 한다.가방들이 놓여진 마지막 상태에서 어떤 가방도 자기보다 더 작은 번호의 가방 안에 들어가 있지 않을 때, 이 상태를 적절하다고 말한다.

주어진 가방의 개수 int n과 취할 행동의 단계 vector<string> actions를 이용하여 마지막 상태가 적절한지 판단하여라. 만약 적절하다면 마지막 상태에 바닥에 놓인 가방의 개수를 반환하여라. 적절하지 않거나 어느 단계의 행동이 유효하지 않다면 -1을 반환하여라.

풀이 1) - python

class Solution:
    def solution(self, n, actions):
        bags=[[] for _ in range(n+1)]
        check = [1]*(n+1)
        for action in actions:
            action = action.split()
            
            if action[0]=="SET":
                idx = int(action[1])
                if not check[idx]:
                    return -1
                
                for bag in bags[idx]:
                    check[bag]=1
                bags[idx]=[]
                
            elif action[0]=="PUT":
                x, y = int(action[1]), int(action[3])
                if not check[x] or not check[y]:
                    return -1
                
                bags[y].append(x)
                check[x]=0
            
            elif action[0]=="SWAP":
                x, y = int(action[1]), int(action[3])
                if not check[x] or not check[y]:
                    return -1
                    
                bags[x],bags[y]=bags[y],bags[x]
        
        for idx in range(1,n+1):
            if bags[idx] and max(bags[idx])>idx:
                return -1
        
        return sum(check[1:])

풀이 2) - python

class Solution:
    def solution(self, n, actions):
        floor = { i:dict() for i in range(1, n+1)}
 
        for action in actions:
            action = action.split(' ')
            i = int(action[1])
 
            if floor.get(i) is None:
                return -1
 
            if action[0] == 'PUT':
                j = int(action[-1])
                if floor.get(j) is None:
                    return -1
                floor[j][i] = floor[i]
                del floor[i]
            elif action[0] == 'SET':
                for bag in floor[i].keys():
                    floor[bag] = floor[i][bag]
                floor[i].clear()
            else:   # SWAP - WITH
                j = int(action[-1])
                if floor.get(j) is None:
                    return -1
                floor[i], floor[j] = floor[j], floor[i]
 
        if self.is_proper(n+1, floor):
            return len(floor)
        else:
            return -1
 
    def is_proper(self, n, floor):
        check = True
        if len(floor) == 0:
            return check
        else:
            for bag in floor.keys():
                if self.is_proper(bag, floor[bag]):
                    if n < bag:
                        check = False
                else:
                    check = False
            return check

풀이 3) - python

class Solution:
    
    def detector(key, map): # detect는 기초적인 노드탐색을 사용
        detected = False
        if len(map)>0 :
            for innerKey in map :
                if int(key) < int(innerKey) or Solution.detector(innerKey, map[innerKey]) :
                    detected = True
                    break
        else :
            pass
        return detected
    
    def solution(self, n, actions):
        bagmap = {}
        for i in range(n) : #기본 상황을 매핑해놓는다 바닥에 있어야 액션을 취할 수 있으므로
            bagmap[str(i+1)] = {}
        
        try :
            if len(actions) > 0 :
                for action in actions :
                    tempbag = {}
                    tempmap = {}
                    letters = action.split(" ")
                    tempchar1 = letters[1]
                    
                    if "PUT" in letters : # PUT 의 경우
                        tempchar2 = letters[3]
                        bagmap[letters[3]][tempchar1] = bagmap[tempchar1]
                        del bagmap[tempchar1]
                        
                    elif "SET" in letters : # SET Loose 의 경우
                        if len(bagmap[tempchar1])>0 :
                            bagmap.update(bagmap[tempchar1])
                        bagmap[tempchar1] = {}
                        
                    elif "SWAP" in letters : # else가 나머지 경우를 담기때문에 상관없지만 가시성을 위해 이와 같이 썼습니다
                        tempchar2 = letters[3]
                        tempbag[tempchar1] = bagmap[tempchar1]
                        bagmap[tempchar1] = bagmap[tempchar2]
                        bagmap[tempchar2] = tempbag[tempchar1]
                        
        except :
            return -1 #바닥에 없다는 오류가 나는 순간 -1 리턴해버리기
 
        for key in bagmap :
            if Solution.detector(key, bagmap[key]) :
                return -1
 
        return len(bagmap)