반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 받은 트랙백

글 보관함

Leetcode 136. Single Number (Easy)

2022. 9. 29. 11:32 | Posted by 솔웅


 

이번 문제의 입력값은 숫자로된 배열 인데 모두 쌍으로 되어 있고 하나만 single value 입니다.

이 입력값 중 single value인 것을 찾아 내면 됩니다.

 

첫번째 접근법은 add 와 remove가 가능한 ArrayList()를 사용하는 것입니다. 

ArrayList()의 contains() 메소드도 이용하겠습니다.

빈 ArrayList()를 만들어 놓 고 입력된 배열의 크기만큼 for 문을 돕니다.

 

만들어 좋은 ArrayList에 있는 값하고 i 번째 값을 비교해서 contain 하고 있다면 이것은 쌍이니까 이 ArrayList에 있는 값을 remove 합니다.

Contain 하고 있지 않다면 아직 쌍이 아닐 확률이 있으니까 이 array list에 add 합니다.

For 문을 모두 돌고 나면 single인 값 하나만 있을 겁니다.

 

이것을 코딩하면 아래와 같습니다.

 

class Solution {
  public int singleNumber(int[] nums) {
    List<Integer> no_duplicate_list = new ArrayList<>();

    for (int i : nums) {
      if (!no_duplicate_list.contains(i)) {
        no_duplicate_list.add(i);
      } else {
        no_duplicate_list.remove(new Integer(i));
      }
    }
    return no_duplicate_list.get(0);
  }
}

 

다음 방법은 key, value 쌍으로 되어 있는 HashMap을 사용하는 방법이다.

이 HashMap의 put(), getOrDefault(), get() 메소드를 사용할 것이다.

HashMap에서 제공되는 메소드들은 아래에 링크에서 살펴 볼 수 있다.

 

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

 

HashMap (Java Platform SE 8 )

If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null. If the function returns null no mapping is recorded. If the function

docs.oracle.com

이중 getOrDefault에 대한 설명은 아래와 같다.

 

다시 원래 문제로 돌아가서 HashMap을 사용해서 만든 코드를 분석해 보겠다.

 

class Solution {
  public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> hash_table = new HashMap<>();

    for (int i : nums) {
      hash_table.put(i, hash_table.getOrDefault(i, 0) + 1);
    }
    for (int i : nums) {
      if (hash_table.get(i) == 1) {
        return i;
      }
    }
    return 0;
  }
}

 

입력된 배열의 크기만큼 for문을 돌리면서 각 값들을 key 로 put 합니다.

그리고 value 부분에는 getOrDefault를 사용해서 key 값이 없으면 0+1 즉 1이 할당이 되고 있으면 그 값에 +1을 해 줍니다.

이렇게 되면 중복된 값은 value부분에 2가 될 것이고 중복되지 않은 값은 value가 1 인 채로 끝까지 남아 있을 겁니다.

여기서 HashMap의 특징을 알아야 하는데요.

해쉬맵에서 키 값의 중복은 허용되지 않습니다.

그러니까 첫번째 for문에서 기존에 key가 존재 하면 그 key에 value를 덮어 쓰게 됩니다.

그러니까 {2,1,2,1,4} 를 위 코드로 돌리면 HashMap은 이렇게 될 겁니다.

2 : 2

1 : 2

4 : 1

 

이런 상태에서 두번째 for 문을 돌려서 value가 1인 값을 찾으면 그 값은 4가 됩니다.

 

이렇게 되면 첫번째 방법보다 runtime 줄어드는 효과가 있습니다. 왜냐하면 첫번째 방법은 for문 안의 contains()에서 아이템을 모두 살펴봐야 하기 때문에 time complexity가 O(n의 제곱)인데 반해서 두번째 접근 법은 O(n)입니다.

 

위 3줄의 Runtime이 아래 3줄보다 훨씬 효율적인 것을 볼 수 있습니다.

 

 

세번째는 수학을 이용하는 방법 입니다.

 

코드는 아래와 같습니다.

class Solution {
  public int singleNumber(int[] nums) {
    int sumOfSet = 0, sumOfNums = 0;
    Set<Integer> set = new HashSet();

    for (int num : nums) {
      if (!set.contains(num)) {
        set.add(num);
        sumOfSet += num;
      }
      sumOfNums += num;
    }
    return 2 * sumOfSet - sumOfNums;
  }
}

 

위 수학식 중 (a+b+c)가 sumOfSet이 되고 (a+a+b+b+c) 가 sumOfNums가 됩니다.

For문 안의 첫번째 if 문에서 sumOfSet이 계산됩니다.

그리고 if문 밖에서 sumOfNums가 계산됩니다.

그 값을 이용해서 위 수학식의 계산을 그냥 return 해 주면 됩니다.

 

마지막 방법은 Bit Manipulation입니다.

저도 잘 모르겠는데.... 그냥 이렇게 있구나... 하고 넘어가야 할 것 같습니다.

코드는 아래와 같습니다.

 

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}

 

실행결과를 보면 위로 갈수록 Runtime이 줄어 드는 것을 볼 수 있습니다.

 

각 Approach의 파이썬 코드는 아래와 같습니다.

 

Python

 

Approach 1

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        no_duplicate_list = []
        for i in nums:
            if i not in no_duplicate_list:
                no_duplicate_list.append(i)
            else:
                no_duplicate_list.remove(i)
        return no_duplicate_list.pop()

 

Approach 2

from collections import defaultdict
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_table = defaultdict(int)
        for i in nums:
            hash_table[i] += 1
        
        for i in hash_table:
            if hash_table[i] == 1:
                return i

 

Approach 3

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return 2 * sum(set(nums)) - sum(nums)

 

Approach 4

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a

 

 

반응형

Comment

Leetcode 119. Pascal's Triangle II (Easy)

2022. 9. 28. 12:04 | Posted by 솔웅


이번 문제를 풀기 전에 118번 문제를 먼저 풀면 도움이 된다.

118번 문제는 아래 글에 정리해 놓았다.

 

https://coronasdk.tistory.com/1150

 

Leetcode 118. Pascal's Triangle (Easy)

오늘의 Leetcode 문제는 118번 Pascal’s Triangle 이다. 난이도는 Easy. 전혀 Easy 하지 않은 것 같은데. 아래가 풀어야 할 문제이다. 우선 패턴을 분석하면 첫줄은 숫자가 한개이고 그 값은 1이다. 두번째

coronasdk.tistory.com

Pascal's Triangle에 대한 패턴은 118번을 다룬 글에 정리해 두었다.

 

그 패턴들을 기반으로 구한 공식은 아래와 같다.

Triangle[row][col] = triangle[row-1][col-1] + triangle[row-1][col-1]

 

자세히 알기를 원하면 위에 있는 링크를 따라 가면 된다.

 

우선 이 결과를 얻으려면 아래와 같은 코딩으로 할 수 있다.

 

class Solution {
    
    private int getNum(int row, int col) {
        if(row == 0 || col == 0 || row == col) {
            return 1;
        }
        
        return getNum(row -1, col -1) + getNum(row-1, col);
    }
    
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>();
        
        for(int i=0; i<= rowIndex; i++) {
            ans.add(getNum(rowIndex, i));
        }
        
        return ans;
    }
}

 

getNum() 메소드를 보면 첫번째 row 이거나 첫번째 col이거나 row와 col이 같다면 즉 맨 마지막 row 이면 값이 1이 주어진다.

getRow() 메소드에서 위 함수를 콜 한 부분을 보면 ans.add(getNum(rowIndex,i)); 이다.

즉 해당 값을 ans 에 넣는 것이다.

위에 설명한 1이 되는 경우 즉 맨 처음과 맨 마지막을 제외하면 getNum(row -1, col -1) + getNum(row-1, col) 로 계산된 값이 들어간다.

이는 재귀 함수 호출로 for 문과 같은 효과를 내는 방식인데 getNum() 함수 내에서 다시 getNum() 함수를 호출하는 방식이다.

 

이렇게 하면 원하는 답을 얻을 수 있다.

 

 

조금 다른 방법도 있다.

 

매번 재귀 함수를 호출하는 것이 아니라 이전에 호출했다 값은 미리 저장해 두고 계속 사용하는 것이다.

 

class Solution {
  private final class RowCol {
    private int row, col;

    public RowCol(int row, int col) {
      this.row = row;
      this.col = col;
    }

    @Override
    public int hashCode() {
      int result = (int) (row ^ (row >>> 32));
      return (result << 5) - 1 + (int) (col ^ (col >>> 32)); // 31 * result == (result << 5) - 1
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null) return false;
      if (this.getClass() != o.getClass()) return false;

      RowCol rowCol = (RowCol) o;
      return row == rowCol.row && col == rowCol.col;
    }
  }

  private Map<RowCol, Integer> cache = new HashMap<>();

  private int getNum(int row, int col) {
    RowCol rowCol = new RowCol(row, col);

    if (cache.containsKey(rowCol)) {
      return cache.get(rowCol);
    }

    int computedVal =
        (row == 0 || col == 0 || row == col) ? 1 : getNum(row - 1, col - 1) + getNum(row - 1, col);

    cache.put(rowCol, computedVal);

    return computedVal;
  }

  public List<Integer> getRow(int rowIndex) {
    List<Integer> ans = new ArrayList<>();

    for (int i = 0; i <= rowIndex; i++) {
      ans.add(getNum(rowIndex, i));
    }

    return ans;
  }
}

 

But, it is worth noting that generating a number for a particular row requires only two numbers from the previous row. Consequently, generating a row only requires numbers from the previous row.

Thus, we could reduce our memory footprint by only keeping the latest row generated, and use that to generate a new row.

그러나 특정 행에 대한 숫자를 생성하려면 이전 행에서 두 개의 숫자만 필요하다는 점에 유의할 가치가 있습니다. 결과적으로 행을 생성하려면 이전 행의 숫자만 필요합니다.

따라서 생성된 최신 행만 유지하여 메모리 공간을 줄이고 이를 사용하여 새 행을 생성할 수 있습니다.

 

이 세가지 코드로 돌린 결과 입니다. 속도 면에서 아주 현격한 차이를 볼 수 있습니다.

 

이와는 아주 다른 접근법이 있을 수 있습니다.

이는 메모리를 절약할 수 있는 방법인데요.

 

여기서 행이 바뀔때마다 생기는 변화에 어떤 규칙성을 찾을 수 있습니다.

세번째줄 1,3,3,1에서 네번째 줄 1,4,6,4,1로 변화할 때의 규칙성을 보죠.

 

4번째 줄 맨 오른쪽은 1이 들어갑니다.

오른쪽에서 두번째 숫자는 3+1인 4가 됩니다.

그리고 오른쪽에서 세번째 숫자는 3+3 인 6이 됩니다. 오른쪽에서 네번째 숫자는 1+3인 4가 되구요. 

맨 왼쪽은 1이되구요.

이 규칙을 가지고 코딩을 하면 아래와 같이 할 수 있습니다.

 

class Solution {
  public List<Integer> getRow(int rowIndex) {
    List<Integer> row =
        new ArrayList<>(rowIndex + 1) {
          {
            add(1);
          }
        };

    for (int i = 0; i < rowIndex; i++) {
      for (int j = i; j > 0; j--) {
        row.set(j, row.get(j) + row.get(j - 1));
      }
      row.add(1);
    }

    return row;
  }
}

 

그 다음은 수학인데요.

이 부분은 제가 잘 이해를 못했습니다.

 

소스 코드는 아래와 같구요.

 

class Solution {
  public List<Integer> getRow(int n) {
    List<Integer> row =
        new ArrayList<>() {
          {
            add(1);
          }
        };

    for (int k = 1; k <= n; k++) {
      row.add((int) ((row.get(row.size() - 1) * (long) (n - k + 1)) / k));
    }

    return row;
  }
}

 

실행 결과를 보면 아래와 같습니다.

 

역시 수학 공식을 사용한 것이 Runtime과 메모리면에서 가장 효율적이네요.

 

20년동안 IT 분야에서 survival했지만 이렇게 까지 수학을 이용해서 코딩 해 본 적은 솔직히 없습니다.

 

좋은 걸 배웠지요.

반응형

Comment


DALL-E 2는 OpenAI에서 만들어 공개한 그림을 그리는 AI 입니다.

그리고 싶은 장면을 문장으로 넣으면 DALL-E 2가 멋진 그림 4개를 그려서 내 놓습니다.

 

DALL·E 2 is a new AI system that can create realistic images and art from a description in natural language.

 

https://openai.com/dall-e-2/

 

DALL·E 2

DALL·E 2 is a new AI system that can create realistic images and art from a description in natural language.

openai.com

 

이 시스템을 사용하려면 Invite를 받은 후 회원 가입하면 됩니다.

위 홈페이지에서 Join Waitlist를 클릭한 후 나오는 폼에 해당 정보를 입력하고 submit하면 됩니다.

 

가을밤 창문에 떨어지는 빗방울을 외롭게 바라보는 한 남자 라고 타이핑해 넣었더니 DALL-E 2가 위 그림 (사진)을 만들어 주었습니다.

 

가입하고 사용하는 방법을 유투브 클립으로 만들어 보았습니다.

관심 있으시면 한번 시도해 보세요.

 

https://youtu.be/mR3C2wkFfGU

 

 

https://www.tiktok.com/t/ZTRmhyfDn/

 

Changsoo Park on TikTok

Drawings with AI painter DALL-E 2.

www.tiktok.com

 

반응형

Comment