2021-01-02] Check Array Formation Through Concatenation

신년부터 다시 자기계발을 하고자 글을 쓴다. ( 1월1일은 신정이니 한 번 봐주자.. 나 자신 )

필자는 영어를 잘 못해서 Google님의 도움으로 문제를 읽고, 예시를 보며 문제를 이해한다. ( Thx, google.. )

그리고, Python으로 문제를 풀고 있어 문제풀이의 경우 python문법으로 풀이한다.

 

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3589/

Account Login - LeetCode

arr와 pieces라는 List를 주고, pieces의 List 값들로 arr과 동일하게 만들 수 있느냐를 묻는 문제이다.

 

arr는 List[int], pieces는 List[List[int]] 즉 조각난 리스트의 순서를 바꿔가며 arr과 같은지 맞춰보는 것임

( * 조각나있는 List 안의 값의 순서는 변경하면 안된다.)

 

예시를 보면서 좀 더 문제를 파악해 보자.

<예시 1 ~ 5>

핵심은 3,4,5이지 않나 싶다.

 

Example 3)

- arr: [49,18,16], pieces: [[16,18,49]]

- 마치 pieces에서 조각난 List 안의 값을 바꿔 arr를 만들면 될 것 같다. ( [[49,18,16]] 마치 이렇게.. )

하지만, 설명처럼 우리는 pieces의 조각난 List안의 순서를 재조정 할 수 없다. 그렇기 때문에, False

 

Example 4)

- arr: [91,4,64,78], pieces:[[78],[4,64],[91]]

- pieces의 1번과 3번을  바꾸면 [[91],[4,64],[78]]이 되고 순서가 arr과 동일하여, True

 

Example 5)

- arr: [1,3,5,7], pieces:[[2,4,6,8]]

- pieces의 값과 arr가 애초에 같지 않으므로, False

 

 

문제풀이) 브루트 포스 기법으로 문제를 풀었다.. (모든 경우의수를 다 찾는거라 3중 for문.. )

class Solution(object):
    def canFormArray(self, arr, pieces):
        """
        :type arr: List[int]
        :type pieces: List[List[int]]
        :rtype: bool
        """
        res=[]
        rtype=True
        for a in range(len(arr)): # arr의 길이만큼 반복
            for piece in pieces: # pieces에서 하나씩 조각난 List값을 얻는다.
                if arr[a] in piece: # 만약 한개의 조각난 List piece에서 arr의 값이 있다면
                    for pic in range(len(piece)): # piece의 길이만큼 반복
                        if a+pic >= len(arr):
                            continue
                        if arr[a+pic] == piece[pic]: #piece의 다음값과 arr의 값이 같으면 res에 add
                            if piece not in res: #중복되는 값이 없도록
                                res.append(piece)
        
        res2=[]
        for i in range(len(res)): # 조각난 piece를 합친거라 extend로 arr처럼 하나의 List로 만들어줌
            res2.extend(res[i])
        if arr != res2: # arr가 res2와 다르면 False return
            rtype=False
        return rtype