튜플

zzwwoonn·2022년 6월 27일
0

Algorithm

목록 보기
64/71

첫 번째 풀이

s = "{{2},{2,1},{2,1,3},{2,1,3,4}}"	
# result = [2,1,3,4]

# s = "{{1,2,3},{2,1},{1,2,4,3},{2}}"	
# result = [2,1,3,4]

from itertools import permutations

def solution(s):
    answer = []
    # print(s)
    L = s.split('},{')
    # print("0. L = ", L)
    L[0] = L[0][2:]
    L[-1] = L[-1][:-2]
    # print("1. L = ", L)

    # for i in range(len(L)):
    #     x = L[i]
    #     print(x)
    #     L[i] = list(x.split(','))
    # # ['1,2,3', '2,1', '1,2,4,3', '2']
    
    originL = []
    maxVal = ''
    for a in L:
        originL.append(a)
        if len(maxVal) < len(a):
            maxVal = a

    resultL = list(maxVal.split(','))
    resultL = list(map(int, resultL))
    L = list(permutations(resultL, len(resultL)))

    # print("2. L = ", L)
    # print("3. originL = ", originL)
    # L = 가능한 순서 조합 전부 -> 이 중에 답 있다

    for i in range(len(originL)):
        originL[i] = originL[i].split(',')
        originL[i] = list(map(int, originL[i]))
    
    print("3. originL = ", originL)
    originL.sort(key = lambda x : len(x))
    print(originL)


    for permu in L:
        # input()
        print("permu = ", permu)
        X = []
        XX = []
        for i in range(1, len(permu)+1):
            for j in range(0, i):
                XX.append(permu[j])
            X.append(XX)
            XX = []
        print(" X = ", X )
        print(" originL = ", originL )        
        
        

        for i in range(len(X)):
            state = True
            print(" i = ", i)
            for j in range(len(X[i])):   
                if X[i][j] not in originL[i]:
                    state = False
                    break

                else:
                    print("X[i][j] = ", X[i][j])
                    print("originL[i] = ", originL[i])
                    print()
            if state == False:
                break
            
            if i == len(X)-1:
                print("찾은 듯?")
                answer = list(permu)
                return answer

print(solution(s))

=> 4개 통과, 나머지 시간 초과

계속 코드를 보다보니 규칙을 찾을 수 있었다. 모든 조합을 다 볼 필요가 없고 구해놓은 배열에서 바로 이전의 값을 기억하고 있다가 그 값을 빼주면 answer에 추가해줄 원소가 된다.

=> 여기서 얕은 복사를 어떻게 하는지 몰라서 애 좀 먹었다..

얕은 복사(Shallow copy)

# 3. 얕은 복사(shallow copy)
# list의 슬라이싱을 통한 새로운 값을 할당해봅니다.
#아래의 결과와 같이 슬라이싱을 통해서 값을 할당하면 새로운 id가 부여되며, # 서로 영향을 받지 않습니다.
>> a = [1,2,3]
>> b = a[:]
>> id(a)
4396179528
>> id(b)
4393788808
>> a == b
True
>> a is b
False
>> b[0] = 5
>> a
[1, 2, 3]
>> b
[5, 2, 3]

간단한? 원리

s = "{{2},{2,1},{2,1,3},{2,1,3,4}}"	
# result = [2,1,3,4]

# s = "{{1,2,3},{2,1},{1,2,4,3},{2}}"	
# result = [2,1,3,4]

def solution(s):
    answer = []
    # print(s)
    L = s.split('},{')
    # print("0. L = ", L)
    L[0] = L[0][2:]
    L[-1] = L[-1][:-2]
    L.sort(key = lambda x : len(x))
    
    # print("1. L = ", L)

    for i in range(len(L)):
        L[i] = L[i].split(',')
        # print(L[i])
        L[i] = (list(map(int, L[i])))
        L[i].sort()
        # print(L[i])
    
    # print("2. L = ", L)
    # [[2], [1, 2], [1, 2, 3], [1, 2, 3, 4]]
    
    storeVal = []
    for i in range(len(L)):
        # print("storeVal = ", storeVal)
        if i == 0:
            storeVal = L[i]
            answer.append(L[i][0])
            continue
        
        XX = L[i]
        X = XX[:]
        # 얕은 복사
        # a = [1,2,3]
        # b = a[:]

        # print("// X = ", X)
        for j in range(len(storeVal)):
            X.remove(storeVal[j])
        # print("// X = ", X)
        answer.append(X[0])
        storeVal = L[i]
    
    return answer
    
        

    # originL = []
    # maxVal = ''
    # for a in L:
    #     originL.append(a)
    #     if len(maxVal) < len(a):
    #         maxVal = a

    # resultL = list(maxVal.split(','))
    # resultL = list(map(int, resultL))
    # L = list(permutations(resultL, len(resultL)))

    # # print("2. L = ", L)
    # # print("3. originL = ", originL)
    # # L = 가능한 순서 조합 전부 -> 이 중에 답 있다

    # for i in range(len(originL)):
    #     originL[i] = originL[i].split(',')
    #     originL[i] = list(map(int, originL[i]))
    
    # print("3. originL = ", originL)

    # for permu in L:
    #     # input()
    #     print("permu = ", permu)
    #     X = []
    #     XX = []
    #     for i in range(1, len(permu)+1):
    #         for j in range(0, i):
    #             XX.append(permu[j])
    #         X.append(XX)
    #         XX = []
    #     print(" X = ", X )
    #     print(" originL = ", originL )        
        

    #     for i in range(len(X)):
    #         state = True
    #         print(" i = ", i)
    #         for j in range(len(X[i])):   
    #             if X[i][j] not in originL[i]:
    #                 state = False
    #                 break

    #             else:
    #                 print("X[i][j] = ", X[i][j])
    #                 print("originL[i] = ", originL[i])
    #                 print()
    #         if state == False:
    #             break
            
    #         if i == len(X)-1:
    #             print("찾은 듯?")
    #             answer = list(permu)
    #             return answer

print(solution(s))

깔끔한 코드 (주석 제거)

def solution(s):
    answer = []
    L = s.split('},{')
    L[0] = L[0][2:]
    L[-1] = L[-1][:-2]
    L.sort(key = lambda x : len(x))
    
    for i in range(len(L)):
        L[i] = L[i].split(',')
        L[i] = (list(map(int, L[i])))
        L[i].sort()
        
    storeVal = []
    
    for i in range(len(L)):
        if i == 0:
            storeVal = L[i]
            answer.append(L[i][0])
            continue
        
        XX = L[i]
        X = XX[:]

        for j in range(len(storeVal)):
            X.remove(storeVal[j])
        answer.append(X[0])
        storeVal = L[i]
    
    return answer

시간이 좀 오래 걸렸는데.. 그래도 내 힘으로 풀었다. 다행

0개의 댓글