1.1 Two Sum 파생문제(자작)

문제 똑바로 안 읽고

첫줄을 알아서 스킵해버림

그 결과 엄청나게 어려운 문제로 바뀌었다

이거 푼다고 3시간이나 붙어있었는데 ㅋㅋㅋㅋ 그럴 문제가 아니었음을...

 

input List에 들어있는 숫자의 조합으로 결과값을 만든다 <- 두개만 리턴하라는 것을 뇌에서 알아서 필터링하고 이것만 가지고 코드를 짜니까 진짜 세상 복잡했다

 

List 성분 하나하나마다 들어가는지 안 들어가는지 경우의 수를 분리해서

1번 성분 ooooxxxx

2번 성분 ooxxooxx

3번 성분 oxoxoxox

행은 2^성분개수 열은 성분개수인 포함/미포함 이차원 배열을 만들었다

그 성분이 포함이면 1 미포함이면 0을 넣어줌

 

들어온 리스트에 있는 걸 저 행렬에 곱해가지고

다 더해줌

 

타겟값이 되는지 확인해가지고 리턴함ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아무튼 코드를 내가 읽은 것에 충실하게는 짰는데 읽은게 잘못되어버린

 

나중에 조건 확인하고 두개의 성분만 썼는지 체크하는거 넣어봄

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        col = 1;
        row = len(nums);

        for i in range(len(nums)):
            col = col*2

        array = [[0 for c in range(col)] for r in range(row)]
        
        end = col;

        for i in range(row):
            end = end/2;
            count = False;
            for j in range(col):
                if(j%end == 0):
                    count = not count;
                if(count == True):
                    array[i][j] = 1;
                else:
                    array[i][j] = 0;

        for i in range(col):
            
            sum = 0;
            res = [];

            for j in range(row):
                sum = sum + array[j][i]*nums[j]
                if(array[j][i]==1):
                    res.insert(0,j)
                

            if(sum == target):
                if(len(res)==2):
                    return res;

 

하지만 일단 포함 미포함 행렬의 행이 2의 지수함수로 늘어나기 때문에 연산시간이 쌉 에바가 되게 되었다

 

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        col = 1;
        row = len(nums);

        for i in range(len(nums)):
            col = col*2

        array = [[0 for c in range(col)] for r in range(row)]
        
        end = col;

        for i in range(row):
            end = end/2;
            count = False;
            for j in range(col):
                if(j%end == 0):
                    count = not count;
                if(count == True):
                    array[i][j] = 1;
                else:
                    array[i][j] = 0;

        for i in range(col):
            
            sum = 0;
            res = [];

            for j in range(row):
                sum = sum + array[j][i]*nums[j]
                

            if(sum == target):
                for k in range(row):
                    if(array[k][i]==1):
                        res.insert(0,k)
                if(len(res)==2):
                    return res;

res 에 넣는거 한번만 연산하게 빼고 노력해보았으나 어차피 지수함수로 늘어난 행렬 연산이 이미 에바였기 때문에 또 시간초과뜸

 

 

저러고 있다가 정신차리고 for문 두번만 써서 문제를 풀었다