반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 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


 

오늘 문제는 숫자로 된 배열을 입력값으로 받고 그 숫자들이 매일 매일의 주식 가격이라고 생각하고 가장 큰 수익을 얻는 다면 그 수익은 얼마가 될까 입니다.

 

7,1,5,3,6,4 가 입력값이라면

 

7에 1에 팔면 -6이 되겠죠.

1에 사서 6에 팔면 +5가 되구요.

1에 사서 7에 팔 수는 없죠. 내일 사서 오늘 팔 수는 없으니까요.

 

즉 산 날은 항상 판 날보다 앞서야 됩니다.

 

Example 2를 보면 만약 수익을 낼 수 있는 상황이 아니면 Output은 0가 되어야 합니다.

어짜피 사고 팔면 마이너스이니까 아예 매매를 하지 않는 상황이 최선이 되는 것이죠.

매매를 하지 않으면 수익이나 손해 없이 0이 되니까요.

 

그렇게 어려운 문제는 아닙니다.

 

이중 for 문을 만들어서 계산하면 되겠죠.

 

우선 바깥의 for 문은 입력 된 배열의 크기만큼 돌려주세요.

안의 for 문은 각 숫자마다 그 이후의 값들 크기 만큼 돌려 줍니다. (미래에 사서 과거에 팔 수는 없으니까요)

 

이렇게 돌려주면 뒤의 숫자에서 앞의 숫자를 계속 빼 주고 그 중 가장 큰 값을 구하면 가장 높은 수익이 됩니다.

 

코드는 아래와 같습니다.

 

class Solution {
    public int maxProfit(int[] prices) {
        // buy on each day
        // find largest difference by selling on some day in buyDay's future
        int largestDifference = 0;
        
        for(int buyDay = 0; buyDay < prices.length; buyDay++) {
            for(int sellDay = buyDay +1; sellDay < prices.length; sellDay++) {
                int currentDifference = prices[sellDay] - prices[buyDay];
                if(currentDifference > largestDifference) {
                    largestDifference = currentDifference;
                }
            }
        }
        return largestDifference;
    }
    // time complexity = O(n^2)
    // space complexity = O(1)
}

 

이건 time complexity가 n의 제곱입니다.

모든 아이템을 대상으로 두번 루프를 돌리니까 그렇게 됩니다.

그러면 input 값의 크기가 크다면 시간이 엄청 걸리겠죠.

 

실제로 이 코드로 submit 하면 time limit exceed 가 나옵니다.

(입력되는 배열의 크기가 그렇게 크지 않다면 제대로 돌아 갑니다.)

 

 

그러면 이중 루프를 사용하지 않고 이 문제를 풀 수 있을 까요? Time complexity를 줄이기 위해서요.

 

배열의 모든 아이템을 비교해 보는게 아니라 가장 낮은 값일 때만 비교해 볼 수 있겠죠.

즉 for 문을 돌리면서 해당 값이 이전 값보다 작으면 계산 하는 겁니다.

 

Integer.MAX_VALUE는 Integer에서 가장 큰 숫자 입니다.

이 값부터 시작해서 for 문에서 그 값보다 더 작으면 minSoFar에 그 값을 넣습니다.

그 다음에도 더 작은 수이면 minSoFar에 넣고 그렇지 않으면 계산을 합니다.

즉 판 값이 산 값보다 더 크면 계산을 하는 겁니다.

계산 공식은 largestDifference 하고 나중 숫자에서 minSoFar (이전 숫자)를 뺀 값 중 더 큰 값을 largestDifference에 넣는 겁니다.

 

이렇게 되면 수익을 올리면 계산에 들어가서 더 큰 수익이 largestDifference에 들어가는 겁니다.

수익이 하나도 나지 않는다면 처음 pargestDifference에 할당 되었던 0이 return 되겠죠.

 

이 경우 time complexity는 O(n) 이 됩니다. For 문이 한번만 모든 아이템에 대해 돌기 때문에 아이템 갯수 만큼만 돕니다.

 

이렇게 하면 runtime과 memory 결과는 아래와 같습니다.

 

소스 코드는 아래와 같습니다.

 

class Solution {
    public int maxProfit(int[] prices) {
        // keep track of the best buy day so far
        // keep track of the largest difference so far
        
        int largestDifference = 0;
        int minSoFar = Integer.MAX_VALUE;
        
        for(int i = 0; i < prices.length; i++) {
            if(prices[i] < minSoFar) {
                minSoFar = prices[i];
            } else {
                largestDifference = Math.max(largestDifference, prices[i] - minSoFar);
            }
        }
        return largestDifference;
    }
    // time coplmexity = O(n)
    // space complexity = O(1)
}

 

 

반응형

Comment

Leetcode - 125. Valid Palindrome - Easy

2022. 9. 16. 11:12 | Posted by 솔웅


오늘의 문제는 Palindrome인지 여부를 알아보는 건데요. 입력값에서 스페이스와 부호들을 다 빼고 모든 글자를 소문자로 바꾼 후 체크해야 합니다.

 

제가 만든 코드는 아래와 같습니다.

 

-

- 입력값에서 모든 스페이스를 제거 한다.  -> line 4

- 입력값에서 모든 부호를 제거한다. -> line 5

- 입력값에서 모든 대문자를 소문자로 바꾼다. -> line 6

 

그 다음에 StringBuilder의 reverse를 사용해서 그 값을 reverse합니다. -> line 8

그리고 String의 equals()를 사용해서 두 값을 비교합니다.

 

아주 간단하게 처리했습니다.

Runtime과 Memory는 아래와 같습니다.

Approach 2

 

아래 코드는 비슷한 로직인데 제가 한 것 처럼 정규직을 쓰지 않고 다른 내부 함수를 사용해서 코딩한 것입니다.

 

class Solution {
  public boolean isPalindrome(String s) {
    StringBuilder builder = new StringBuilder();

    for (char ch : s.toCharArray()) {
      if (Character.isLetterOrDigit(ch)) {
        builder.append(Character.toLowerCase(ch));
      }
    }

    String filteredString = builder.toString();
    String reversedString = builder.reverse().toString();

    return filteredString.equals(reversedString);
  }

  /** An alternate solution using Java 8 Streams */
  public boolean isPalindromeUsingStreams(String s) {
    StringBuilder builder = new StringBuilder();

    s.chars()
        .filter(c -> Character.isLetterOrDigit(c))
        .mapToObj(c -> Character.toLowerCase((char) c))
        .forEach(builder::append);

    return builder.toString().equals(builder.reverse().toString());
  }
}

 

위에 3개가 이 코드로 돌린 건데요.

제가 만든 코드로 돌린 것 보다 Runtime이 확실히 줄어 드네요. 메모리도 약간 줄어 들고요.

이 코드를 좀 공부 해 둬야 겠습니다.

 

Approach 3

 

 

다음은 입력문의 첫번째와 마지막 글자부터 비교하는 것입니다.

중간에 스페이스나 부호들은 건너 뜁니다.

그러니까 그것들을 remove하는 것을 하지 않아도 됩니다.

 

class Solution {
  public boolean isPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
        i++;
      }
      while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
        j--;
      }

      if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
        return false;
    }

    return true;
  }
}

 

마지막 방법이 훨씬 Performance가 좋네요.

 

내가 생각했던 쉽게 접근 하는 방법에서 조금만 더 머리를 쓴 건데 훨씬 좋은 performances 를 보이는 군요.

잘 배워 둬야 겠습니다.

반응형

Comment


이번에 면접보다 떄 나왔던 문제다.

문제는 아주 쉬웠다.

 

인터뷰 중에는 아래와 같이 풀었다.

 

이걸 조금 Refactoring 해 보겠다.

 

Refactoring

 

소스 코드는 아래와 같다.

 

class HelloWorld {
    public static void main(String[] args) {
        FizzBuzz(16);
    }
    private static void FizzBuzz (int x) {
        for(int i=1; i <=x; i++) {
            if(i % 3 == 0 && i % 5 ==0) System.out.println("FizzBuzz");
            else if(i % 3 == 0) System.out.println("Fizz");
            else if(i % 5 == 0) System.out.println("Buzz");
            else System.out.println(i);
        }
    }
}

 

이번 면접에서는 붙지 못했다.

 

인터뷰 중에도 이렇게 Refactoring까지 했어야 됐는지...

아니면 중간에 % 를 / 로 헷갈리게 스크립트를 하다가 바로 고친 부분이 마이너스가 됐는지...  (이게 큰 요인 같다.)

아니면 요즘 물가도 안 잡히고 구조조정도 더 늘어가는 마당에 사람을 적극적으로 뽑지 않기로 회사 방침이 바뀌었는지....

 

어쨌든 계속 코딩 실력을 연마 하면서 다른 포지션에 인터뷰를 도전 하는 방법 밖에는.....

반응형

Comment

  1. 저랑 관심분야가 비슷하시네요 :) 좋은 글 잘 보고 갑니다!! 다음에도 놀러올게요 ㅎㅎ

Leetcode - 88. Merge Sorted Array - Easy

2022. 9. 6. 13:37 | Posted by 솔웅


 

이번 문제는 두개의 integer array를 받고 또 두개의 숫자를 받습니다.

첫번째 배열과 첫번째 숫자의 의미는 숫자의 개수만큼 첫번째 배열의 아이템을 사용하고 나머지는 버린다 입니다.

두번째 배열과 두번째 숫자도 마찬가지 의미 입니다.

 

여기에 한가지 더 조건이 있습니다.

첫번째 배열의 아이템 숫자는 입력 받은 두 숫자의 합 이라는 겁니다.

 

이 조건 때문에 문제가 완전히 쉬워 졌습니다.

일단 첫번째 배열에서 첫번째 숫자 와 맞는 갯수 만큼만 채우고 두번째 배열에서 나머지를 그냥 채워 넣으면 되니까요. 

 

이 조건이 있는 이유는 배열은 그 크기를 변경하는 것이 불가능 하기 때문입니다.

 

크기를 변경하려면 List를 사용해야 합니다. (ArrayList, LinkedList etc.)

 

위에 얘기한 대로 코딩을 하면 아래와 같습니다.

 

참 결과 값은 정렬 되어 있어야 해서 마지막에 Arrays.sort()를 사용해야 합니다.

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[i + m] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

 

 

이렇게 하면 됩니다.

 

그런데 여기서 Arrays.sort()는 리소스를 좀 많이 차지 합니다.

좀 더 Refactoring을 하고 싶다면 아래와 같이 하면 됩니다.

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Make a copy of the first m elements of nums1.
        int[] nums1Copy = new int[m];
        for (int i = 0; i < m; i++) {
            nums1Copy[i] = nums1[i];
        }

        // Read pointers for nums1Copy and nums2 respectively.
        int p1 = 0;
        int p2 = 0;
                
        // Compare elements from nums1Copy and nums2 and write the smallest to nums1.
        for (int p = 0; p < m + n; p++) {
            // We also need to ensure that p1 and p2 aren't over the boundaries
            // of their respective arrays.
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
}

 

이 방법은 첫번째 배열의 뒷자리 부터 집어 넣는 것입니다.

첫번째 배열의 맨 마지막 숫자와 두번째 배열 맨 마지막 숫자를 비교해서 큰 숫자를 마지막에 넣는 것입니다.

 

하나 하나 볼까요?

 

처음에는 nums1[]을 nums1Copy[]라는 새 배열에 카피 합니다.

 

그리고 인지적 p1과 p2를 생성합니다.

 

이제 루프를 돌릴 텐데요.

m + n 만큼 돌립니다. nums1[]의 크기가 m+n이니까 첫번째 배열의 크기만큼 돌려도 됩니다.

 

If 문을 보면 p2가 n보다 크거나 같거나

p1이 m보다 작고 nums1Copy[p1] 이 nums[p2] 보다 작으면 실행합니다.

 

실행문 은 nums1[p] 에 nums1Copy[p1] 을 넣고 p1에 1을 더합니다.

 

즉 첫번째 배열의 첫번째 값이 두번째 배열의 첫번째 값보다 작으면 nums1[p]에 작은 값을 넣습니다.

반대로 else를 보면 첫번째 배열의 첫번쨰 값이 크면 두번째 배열의 첫번째 값 즉 더 작은 값을 넣습니다.

 

그 다음은 두번째 아이템으로 가서 똑 같은 일을 반복 합니다.

 

이렇게 되면 두 배열에서 작은 숫자 만큼 하나하나 채워 나가게 되므로 sorting을 할 필요가 없습니다.

 

반대로 배열의 뒤에서 부터 집어 넣을 수도 있습니다.

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int r1 = m-1;
        int r2 = n-1;
        
        for(int w=m+n - 1; w >= 0; w--){
            if(r1 >= 0 && r2 >= 0) {
                nums1[w] = nums1[r1] > nums2[r2] ? nums1[r1--] : nums2[r2--];
            } else if(r1 >= 0) {
                nums1[w] = nums1[r1--];
            } else {
                nums1[w] = nums2[r2--];
            }
        }
        return;
    }
}

 

이 방법은 첫번째 배열의 뒷자리 부터 집어 넣는 것입니다.

여기서는 새로운 배열을 생성하지 않고 nums1에 곧바로 값을 넣을 수 있습니다.

 

For 문은 m+n-1만큼만 돌립니다. 이 값은 w에 담깁니다.

w는 루프가 돌때마다 1식 마이너스 됩니다.

 

이것을 이용하면 nums1[]의 맨 마지막 부터 숫자를 채워 넣을 수 있습니다.

If문을 보면 r1과 r2 모두 0보다 클 경우 실행하게 되는데요.

첫번쨰 배열의 마지막에 값을 넣습니다.

그 값은 첫번째 배열 마지막 값과 두번째 배열 마지막값을 비교해서 더 큰 수를 넣고 해당 숫자 (r1 or r2)에서 1을 마이너스 합니다.

그러다가 r1이나 r2중 하나가 0보다 작게 된 경우 두번째 if로 가서 r1이 남아 있을 경우는 첫번째 배열의 r1번째 값을 넣고

r2 가 남아 있을 경우 두번째 배열의 r2값을 넣습니다.

 

이렇게 되면 배열의 뒤부터 큰 값을 채워 넣어서 나중에 정렬을 할 필요가 없어집니다.

 

 

결과를 보면 확실히 Arrays.sort()를 사용하지 않은 방법이 더 속도가 빠른것을 알 수 있습니다.

그만큼 리소스를 덜 사용하게 됩니다.

 

반응형

Comment


오늘의 문제는 입력값으로 정렬된 linked list를 받아서 중복된 값을 제외하는 겁니다.

 

소스코드 와 실행 결과는 아래와 같습니다.

입력값은 1,1,2,3,3 입니다.

 

로직을 하나하나 따라가 보겠습니다.

 

While문을 시작할 때는 current 값이 1, next 값이 1 그리고 next.next값이 2 입니다.

그러면 현재 값과 다음 값이 모두 1 이므로 if 문 안으로 들어가서 current.next 가 그 다음 값을 포인트에 하게 됩니다.

첫번쨰 While문을 끝내면 첫번째 1은 2를 포인트 하게 됩니다.

 

두번째 루프에서는 각각 값이 1,2,3이 됩니다. 

그러면 현재 값 두번째 1은 2가 됩니다.

 

세번째 루프에서는 2,3,3 이 됩니다.

또한 현재 값 2는 3이 되죠.

 

네번째 루프에서는 3,3,null 이 됩니다.

여기서는 current.next.next가 널 이라서 Current.next도 널 이 되는가 같습니다.

 

간단한 문제 인 것 같은데 좀 헷갈립니다.

Linkedlist에 대해 잘 모르는 부분이 있는것 같습니다.

 

이에 대한 자세한 설명은 아래 유튜브에 있습니다.

 

https://youtu.be/sq49IpxBl2k

https://youtu.be/LRfLzM5uVDg

 

 

https://youtu.be/klZ0fFXxT6Q

 

https://youtu.be/TcNevBGuCAI

https://youtu.be/wleQHJBO63Q

소스코드는 아래와 같습니다.

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
           } else {
                current = current.next;
            }
        }
        return head;
    }
}

반응형

Comment

Leetcode - 69. Sqrt(x) - Easy

2022. 9. 2. 14:26 | Posted by 솔웅


이번 문제는 입력받은 숫자의 제곱근을 구하는 문제 입니다.
리턴값은 정수 입니다. 그러니까 소수점 아래 숫자는 없애고 정수만 리턴합니다.
그래서 8의 제곱근은 2.82842... 인데 소수점 아래를 없앤 2가 리턴되게 됩니다.

그렇다면 x 는 a의 제곱보다는 크거나 같고 a+1의 제곱보다는 작은 수가 될 겁니다.

코딩을 하기 전에 Math.pow() 메소드를 알아보겠습니다.


그리고 Math에서는 PI와 E라는 상수가 있다.
E는 자연상수 혹은 오일러 수(Euler's Number)라고 불리고, 값은 무리수이다.

그리고 로그 값을 구하는 Math.log() 메소드도 있다.

이것들을 이용해서 스크립팅을 하면 아래와 같이 할 수 있다.

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    int left = (int)Math.pow(Math.E, 0.5 * Math.log(x));
    int right = left + 1;
    return (long)right * right > x ? left : right;
  }
}

Python으로 하면 아래와 같이 하면 된다.

from math import e, log
class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left = int(e**(0.5 * log(x)))
        right = left + 1
        return left if right * right > x else right

두번쨰 방법은 Binary Search 이다.

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

JAVA

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    long num;
    int pivot, left = 2, right = x / 2;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      num = (long)pivot * pivot;
      if (num > x) right = pivot - 1;
      else if (num < x) left = pivot + 1;
      else return pivot;
    }

    return right;
  }
}

Python

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left, right = 2, x // 2
        
        while left <= right:
            pivot = left + (right - left) // 2
            num = pivot * pivot
            if num > x:
                right = pivot -1
            elif num < x:
                left = pivot + 1
            else:
                return pivot
            
        return right

세번째 방법은 아래와 같다.
(문과 출신의 한계로 제대로 수학이 나오면 이해하기 힘들다… 그냥 한번 읽어보고 이런게 있구나 하면서 넘어가야 겠다.)


코딩은 아래와 같습니다.

JAVA

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    int left = mySqrt(x >> 2) << 1;
    int right = left + 1;
    return (long)right * right > x ? left : right;
  }
}

Python

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left = self.mySqrt(x >> 2) << 1
        right = left + 1
        return left if right * right > x else right

네번쨰 방법입니다.


JAVA

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    double x0 = x;
    double x1 = (x0 + x / x0) / 2.0;
    while (Math.abs(x0 - x1) >= 1) {
      x0 = x1;
      x1 = (x0 + x / x0) / 2.0;
    }

    return (int)x1;
  }
}

Python

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        x0 = x
        x1 = (x0 + x / x0) / 2
        while abs(x0 - x1) >= 1:
            x0 = x1
            x1 = (x0 + x / x0) / 2        
            
        return int(x1)

이 네가지 방법의 Runtime과 Memory는 거의 차이가 없는 것 같다.








반응형

Comment

Leetcode - 67. Add Binary - Easy

2022. 9. 2. 13:54 | Posted by 솔웅


오늘 문제의 입력값은 두개의 String 타입인데 그 값은 이진수 입니다.

이 두 값을 이진수로 더한 값을 리턴하면 됩니다.

 

이 문제를 풀기에 앞서서 이 두 메소드를 살펴 보겠습니다.

Integer.parseInt(String, n), toBinaryString(int num)

 

우선 parseInt(String s, int radix)를 알아보겠습니다.

 

여기서 String s는 숫자로만 구성 되어야 합니다. 그런데 그 타입이 String 인 것입니다.

Int radix는 그 스트링 으로 돼 있는 숫자가 몇 진수 인지를 나타내는 겁니다.

 

그리고 그 값을 10진수 형태로 반환하는데 이 메소드가 하는 역할 입니다.

 

 

toBinaryString(int num) 은 숫자를 입력값을 받아서 그것을 진수로 바꿔서 이것을 String 타입으로 반환하는 겁니다.

 

그러니까 위 문제에서 요구한 두개의 스트링 입력값을 받아서 그것을 더한 후 그 이진수를 스프링으로 반환하는 것은 이 한 줄이면서 간단하게 해결 됩니다.

 

    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));

 

Integer.parseInt(a,2)는 입력받은 이진수 a를 10진수로 바꿉니다.

Integer.parseInt(b.2)는 입력받은 이진수 b를 10진수로 바꿉니다.

그리고 이 두 값을 더한 후 toBinaryString()이 다시 이진수로 만들고 이것을 String 타입으로 변환해서 반환합니다.

 

그러면 이 문제에 대한 해답이 될 수 있습니다. 그런데 여기에서 문제가 있습니다.

 

이렇게 하면 자릿수가 많은 입력값은 NumberFormatException이 발생합니다.

 

String을 numeric type으로 변환하는데 있어서 적당한 포맷이 없기 때문에 일어나는 예외 입니다.

 

Integer, Long, BigInteger 등 모든 Numeric type은 자릿수 제한이 있기 때문입니다.

 

이 문제를 해결하기 위해서는 좀 더 복잡한 로직을 만들어야 합니다.

 

첫번째 방법은 bit 별로 계산하는 겁니다.

 이진수에서 1+1 은 10 이 됩니다.

1+0 = 1, 0+0 은 0이 되구요.

이렇게 그냥 비트 단위에서 계산하는 겁니다.

 

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

 

class Solution {
  public String addBinary(String a, String b) {
    int n = a.length(), m = b.length();
    if (n < m) return addBinary(b, a);
    int L = Math.max(n, m);

    StringBuilder sb = new StringBuilder();
    int carry = 0, j = m - 1;
    for(int i = L - 1; i > -1; --i) {
      if (a.charAt(i) == '1') ++carry;
      if (j > -1 && b.charAt(j--) == '1') ++carry;

      if (carry % 2 == 1) sb.append('1');
      else sb.append('0');

      carry /= 2;
    }
    if (carry == 1) sb.append('1');
    sb.reverse();

    return sb.toString();
  }
}

 

입력 받은 두 값 중 자릿수가 큰 입력값의 크기 만큼 for 문을 돌립니다.

For 문 안에는 이진수 계산법을 하는 로직을 있습니다.

이렇게 비트 단위로 계산 한 후 결과 값을 리턴 하는 방법이 첫번째 방법입니다.

 

두번째 방법은 XOR로 처리한 후 carry하는 방법입니다.

알고리즘은 아래와 같습니다.

 

스크립트는 아래와 같습니다.

 

import java.math.BigInteger;
class Solution {
  public String addBinary(String a, String b) {
    BigInteger x = new BigInteger(a, 2);
    BigInteger y = new BigInteger(b, 2);
    BigInteger zero = new BigInteger("0", 2);
    BigInteger carry, answer;
    while (y.compareTo(zero) != 0) {
      answer = x.xor(y);
      carry = x.and(y).shiftLeft(1);
      x = answer;
      y = carry;
    }
    return x.toString(2);
  }
}

 

참고로 이것을 Python으로 하면 아래와 같습니다.

 

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]

 

첫번째 방법과 두번째 방법의 Runtime과 Memory 차이는 이렇습니다.

 

솔직히 저로서는 두번째 방법은 자세하게 이해하기는 힘드네요.

그냥 이렇게 있구나 하는 정도로 이해하고 넘어 가기로 했습니다.

반응형

Comment

Leetcode 66. Plus One - Easy

2022. 9. 1. 16:03 | Posted by 솔웅


이번 문제는 한자리 숫자들로 이루어진 배열을 입력받아서 처리하는 겁니다.

그 숫자들로 구성된 한 숫자에 1을 더하는 겁니다.

즉 [1,2,3] 이면 123으로 생각해서 여기에 1을 더한 124를 한자리 숫자들로 이뤄진 배열인 [1,2,4] 로 만들어 반환하면 됩니다.

 

여기에는 세가지 경우의 수가 있습니다.

위와 같이 배열의 마지막 숫자가 9가 아니면 단순히 그 숫자에 1을 더하면 됩니다.

 

그런데 마지막 숫자가 9인 경우는 조금 다르게 접근 해야 합니다.

 

[1,2,9] 인 경우는 129가 되고 여기에 1을 더하면 130이 됩니다. 그러면 리턴값은 [1,3,0] 이 됩니다.

이 경우는 9인 값은 0이 되고 그 이전 값 중 9가 아닌 숫자에 1을 더하면 됩니다.

[8,9,9] 인 경우는 899가 되서 900으로 계산 되고 리턴값은 [9,0,0] 이 되겠죠.

 

한가지 경우가 더 있습니다.

 

모든 숫자들이 9인 경우입니다.

[9,9,9] 인 경우는 999 + 1 이 되서 1000이란 값이 계산 됩니다. 그럼 리턴 값은 [1,0,0,0] 이 됩니다.

모든 9는 0으로 되고 아이템을 하나 더 만들어서 그 값은 1로 해야 됩니다.

 

다음 3가지 조건을 만족하는 로직을 만들어야 합니다.

 

1. 맨 마지막 숫자가 9가 아닌 경우 : 마지막 숫자에 1을 더함

2. 마지막 숫자가 9 이 고 이전의 숫자 중 9가 아닌 숫자가 있는 경우 : 9를 0으로 바꾸고 9가 아닌 숫자에 1을 더하고 마친다.

3. 모든 숫자가 9인 경우 : 모든숫자를 0으로 바꾸고 맨 앞에 1을 하나 붙인다. (배열 크기가 하나 더 큰 새로운 배열을 만들어야 한다.

 

내가 만든 로직은 아래와 같습니다.

 

class Solution {
    public int[] plusOne(int[] digits) {
        
        int inputLeng = digits.length;
        
        if(digits[inputLeng-1] == 9) { // if last number is 9
            boolean allNine = true;
            for(int i=0; i < inputLeng - 1; i++) { // check if all numbers are 9
                if(digits[i] != 9) {
                    allNine = false;
                } 
            }
            if(allNine) { // if all 9s
                int[] newDigits = new int[inputLeng + 1]; // create new array (length is input + 1)
                newDigits[0] = 1; // first one is 1
                for(int n=1; n < inputLeng-1; n++) { // all others are 0
                    newDigits[n] = 0;
                }
                return newDigits;
            } else { // if at least one number is not 9
                for(int j=inputLeng-1; j >= 0; j--) {
                    if(digits[j] != 9) {
                        digits[j] = digits[j] + 1; // not 9 + 1
                        break; // escape for loop
                    }
                    digits[j] = 0; // not 9 should be 0
                }
            }
        } else { // if last number is not 9 then just +1
            int plusOne = digits[inputLeng-1] + 1;
            digits[inputLeng-1] = plusOne;
        }
        return digits;
    }
}

 

이것을 조금 더 간단하게 리팩토링 해서 만든 것이 아래 로직 입니다.

 

class Solution {
  public int[] plusOne(int[] digits) {
    int n = digits.length;

    // move along the input array starting from the end
    for (int idx = n - 1; idx >= 0; --idx) {
      // set all the nines at the end of array to zeros
      if (digits[idx] == 9) {
        digits[idx] = 0;
      }
      // here we have the rightmost not-nine
      else {
        // increase this rightmost not-nine by 1
        digits[idx]++;
        // and the job is done
        return digits;
      }
    }
    // we're here because all the digits are nines
    digits = new int[n + 1];
    digits[0] = 1;
    return digits;
  }
}

 

이 로직은 하나의 for 을 사용했는데요. 그 안에서 아래와 같은 일을 합니다.

- 일단 모든 9을 0으로 바꾼다. 0이 아닌 값이 있으면 1을 더해서 리턴한다.

 

이렇게 되면 위 경우의 수 1번과 2번이 해결 됩니다.

 

모든 숫자가 9인 경우는 for 문 안에 있는 else 가 실행되지 않고 그 아래 코드로 넘어 가는데요.

여기서 배열의 크기를 하나 늘린 새로운 배열을 만들어서 맨 앞에 1을 넣습니다.

 

 

아래 3개가 첫번째 로직 으로 돌린 것이고 위에 3개가 두번째 로직을 돌린 겁니다.

For 루프를 하나밖에 안 쓴 두번째 로직 이 훨씬 빠릅니다.

 

반응형

Comment

Leetcode - 58. Length of Last Word - Easy

2022. 8. 24. 18:15 | Posted by 솔웅


이번 문제는 입력된 문장 중에서 맨 마지막 단어의 알파벳 개수를 알아내는 문제입니다.

 

일단 문장 중에서 단어와 단어 사이에는 스페이스가 있습니다.

그래서 내가 생각한 방법은 스페이스를 기준으로 입력된 문장을 split해서 String 배열로 만드는 겁니다.

거기서 맨 마지막 단어를 가져와서 그 단어의 알파벳 개수를 세면 됩니다.

 

코딩은 아래와 같이 했습니다.

class Solution {
    public int lengthOfLastWord(String s) {
        int resultValue = 0;
        String[] splitString = s.split(" ");
        int lenSArray = splitString.length;
        resultValue = splitString[lenSArray-1].length();
        return resultValue;
    }
}

 

이 스크립트는 훌륭하게 작동합니다.

 

Leetcode에서 소개한 다른 방법들은 아래와 같습니다.

 

Approach 1

class Solution {
    public int lengthOfLastWord(String s) {
        // trim the trailing spaces
        int p = s.length() - 1;
        while (p >= 0 && s.charAt(p) == ' ') {
            p--;
        }

        // compute the length of last word
        int length = 0;
        while (p >= 0 && s.charAt(p) != ' ') {
            p--;
            length++;
        }
        return length;
    }
}

이 방법은 우선 문장 맨 마지막으로 갑니다. (S.length()-1)

그 값이 스페이스이면 그 이전으로 갑니다.

뭔가 스페이스가 아닌 문자가 나왔다면 거기서부터 그 전 알파벳을 살펴 봅니다.

계속 이 과정을 반복하다가 스페이스가 나오면서 멈춥니다. 마지막 단어의 첫 알파벳에서 멈추는 겁니다.

그러는 동안 length++를 해주니까 마지막에는 맨 마지막 단어의 알파벳 개수가 나오게 됩니다.

이것도 좋은 방법이긴 한데... 내가 한 방법이 더 마음에 드네요.

 

다른 방법도 있습니다.

 

Approach 2.

class Solution {
    public int lengthOfLastWord(String s) {
        int p = s.length(), length = 0;
        while (p > 0) {
            p--;
            // we're in the middle of the last word
            if (s.charAt(p) != ' ') {
                length++;
            }
            // here is the end of last word
            else if (length > 0) {
                return length;
            }
        }
        return length;
  }
}

 

이 방법은 Approach 1과 같습니다. 다만 두개의 루프를 하나의 루프로 줄인 것입니다.

 

Approach 3. 

class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();  // trim the trailing spaces in the string
        return s.length() - s.lastIndexOf(" ") - 1;
    }
}

마지막 방법인데요.

이 방법은 제가 만든 방법보다 더 깔끔한 것 같네요.

우선 trim으로 맨 끝에 스페이스가 있다면 없애 주고요.

문장의 전체 알파벳 개수를 구하고 (스페이스 포함) 거기에 이 문장의 마지막 스페이스의 위치를 구해서...

첫번째에서 두번째를 마이너스 하는 겁니다. 

그러면 딱 마지막 단어의 알파벳 개수가 나오겠네요.

 

오늘 방법 중에서는 이게 제일 난 것 같습니다.

반응형

Comment