IT 기술 따라잡기

오늘의 문제는 입력값으로 정렬된 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;
    }
}

이번 문제는 입력받은 숫자의 제곱근을 구하는 문제 입니다.
리턴값은 정수 입니다. 그러니까 소수점 아래 숫자는 없애고 정수만 리턴합니다.
그래서 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는 거의 차이가 없는 것 같다.

오늘 문제의 입력값은 두개의 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 차이는 이렇습니다.

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

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

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

그 숫자들로 구성된 한 숫자에 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 루프를 하나밖에 안 쓴 두번째 로직 이 훨씬 빠릅니다.

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

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

그래서 내가 생각한 방법은 스페이스를 기준으로 입력된 문장을 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으로 맨 끝에 스페이스가 있다면 없애 주고요.

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

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

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

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

이번에 다룰 문제는 입력값이 3의 제곱근인지 여부를 가리는 문제입니다.

우선 패턴을 분석해 봅시다.

3의 제곱근은 이렇습니다.

3 (3*1), 9 (3*3), 27(3*3*3), 81(3*3*3*3), 243(3*3*3*3*3) ......

첫번째 패턴은 모든 3의 제곱근은 3으로 계속 나누면 결국은 3이 되고 이 3은 3으로 나누면 1이 됩니다.

1. 계속 나누면 마지막에 1이 되는 숫자 

이게 첫번째 패턴입니다.

그리고 두번째 패턴은 0은 3의 제곱근이 아닙니다. 그리고 음수 라도 안 됩니다.

2. 0이나 음수가 아닌 수

이걸 코딩을 하면 이렇게 됩니다.

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) { // 0이 입력 되면 false를 반환 한다.
            return false;
        }
        while (n % 3 == 0) { // 3으로 나눠 질 경우
            n /= 3; // 계속 3으로 나눈다.
        }
        return n == 1; // 결과가 1이면 true, 아니면 false 를 리턴한다.
    }
}

이것 말고 다른 방식으로 할 수도 있습니다.

수학에서 사용하는 수열의 합인 시그마와 Regular expression을 사용한 것입니다.

이걸 설명하기는 좀 어렵고 이걸 사용해서 만든 코드는 아래와 같습니다.

public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}

다음은 수학의 제곱근을 나타내는 식인 로그를 사용한 방법입니다.

코드는 아래에 복사해 넣습니다.

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

마지막 방법은 이렇습니다.

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

자세한 건 이해를 하지 못하겠고... 이 네가지 방법의 메모리 사용량과 처리 속도를 비교해 보겠습니다.

Approach 1. 첫번째 방법으로 한 것입니다. 

Approach 2. 

두번째 방법은 첫번째 방법보다 메모리와 런타임이 조금 더 많이 나옵니다.

Approach 3. 

이 세번째 방법은 첫번째와 거의 비슷한데 조금 더 많이 나옵니다. 두번째 보다는 적게 나오고요.

Approach 4. 

네번째 방법은 세번째 방법하고 거의 비슷하네요.

첫번째 방법이 가장 이해하기도 쉽고 퍼포먼스도 잘 나오는 것 같습니다.

Leetcode에 나와서 한번 공부해 봤는데... 복잡한 방법들을 사용하면 어떤 이점이 있는지는 모르겠네요.

전 그냥 첫번째 방법으로 할 것 같습니다. 나머지는 이해하기도 힘들고요.

Leetcode에서는 이렇게 말하고 있습니다.

입력값이 큰 값을 수록 Approach 4가 가장 빠르다고 합니다.

이걸 이해하기에는 아직 제 실력이 많이 부족하네요.

그냥 이렇게 있구나.... 하고 넘어가야 겠습니다.

지난 번에 Leetcode의 Anagram 문제를 한번 풀어 봤는데요.

이번에 Technical Interview 보면서 이 Anagram 문제가 나와서 한번 풀어봤습니다.

지난번 했던 방법으로 풀었기 했는데... 나중에 생각해 보니 또 다른 방법이 생각 나더라고요.

일단 지난번 글은 아래 링크에 있습니다.

https://coronasdk.tistory.com/1156

이 때 사용했던 로직을 풀면 아래와 같이 할 수 있습니다.

class Anagram1 {

    public static void main(String[] args) {

        boolean result = true;

        String s = "abcd";

        String t = "cdab";

        if(s.length() != t.length()) {

            result = false;

        }

        int[] sCounter = new int[26];

        int[] tCounter = new int[26];

        for(int i=0; i<s.length(); i++) {

            sCounter[s.charAt(i) - 'a']++;

            tCounter[t.charAt(i) - 'a']++;

        }

        for(int i = 0; i<26; i++){

            if(sCounter[i] != tCounter[i]){

                result = false;

            }

        }

        if(result) {

            System.out.println("This is Anagram.");

        } else {

            System.out.println("This is not Anagram");

        }

    }

}

ASCII Code를 이용한 방법인데요.

자세히 보시려면 위에 있는 링크로 가시면 설명한 것을 보실 수 있습니다.

이번엔 ArrayList로 루프 없이 만든 코드 입니다.

import java.io.*; 

import java.util.*; 

class Anagram2 {

    public static void main(String[] args) {

        boolean result = true;

        String s = "abcd";

        String t = "cdab";

        if(s.length() != t.length()) {

            result = false;

        }

        String[] sSplit = s.split("");

        String[] tSplit = t.split("");

        ArrayList<String> sList = new ArrayList<String>(

            Arrays.asList(sSplit));

        ArrayList<String> tList = new ArrayList<String>(

            Arrays.asList(tSplit));

        Collections.sort(sList);

        Collections.sort(tList);

        result = sList.equals(tList);

        if(result) {

            System.out.println("This is Anagram.");

        } else {

            System.out.println("This is not Anagram");

        }

    }

}

String 을 ArrayList로 만들어서 sorting을 하고 equals()를 사용해서 문제를 풀었습니다.

근데 역시 ASCII를 이용해서 for loop를 돌리는데 Runtime 이나 Memory 관리 면에서 훨씬 더 나은 방법인데요.

지난 글에서 Big O에 대해 알아보면서 Binary Search에 대해 언급 했습니다.

이번에는 Binary Search에 대해 공부 해 보겠습니다.

문제는 지난번 문제와 거의 유사합니다.

입력값은 정렬된 배열과 target 값입니다.

출력값은 target이 배열의 몇번째에 있는지 입니다.

또 한가지 조건은 지난번 배웠던 Big O 표기법으로 표시 됐습니다. O(log n)

이것을 충족 시키려면 Binary Search를 해야 합니다.

루프 내에서 배열의 첫번째 값에서 마지막 값까지 하나 하나 살펴 보는 것은 O(n) 입니다.

O(log n) 은 배열의 중간 값을 가져 와서 타겟 값과 비교 합니다.

그리고 타겟 값이 더 크면 왼 쪽 반을 버리고 오른쪽 반만 놓 고 다시 이를 반복 합니다.

그러면 검색을 하는 step 을 줄여서 시간과 리소스 사용량을 줄일 수 있습니다.

어떻게 작동 되는지 알아보기 위해 7번째 줄에 print 문을 넣었습니다.

루프의 첫번째 스텝에서는 가운데 값이 9를 가져 옵니다. 타겟값 5보다 크니까 오른쪽을 버리고 왼쪽만 가져 옵니다.

그 다음 다시 가운데 값을 가져오는데 그 값은 0 입니다. 타깃이 크니까 왼쪽을 버립니다.

다음 단계는 가운데 값이 3이라서 다시 왼쪽을 버립니다.

그 다음 가운데 값은 5 이 고 이는 타깃 값과 같으니까 이 값을 리턴 합니다.

배열의 아이템은 10 개 인데 4번만에 정답을 찾아 냈습니다.

타깃값을 14를 해도 4번째 만에 정답을 찾아 냈습니다.

이렇게 19를 넣었을 때는 3번쨰 만에 그리고 20을 넣었을 때는 네번째 만에 찾아냈습니다.

배열에 없는 값을 넣어도 4번째 만에 정답을 찾아 냈습니다.

이렇듯 배열에 있는 아이템이 10 개가 있는데도 최대 4번의 스텝 만으로 정답을 알아 낼 수 있는 것은 바이너리 검색을 사용했기 때문입니다.

이것을 Big O 표기법에 따르면 O(log n)으로 표시합니다.

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

class Solution {

    public int search(int[] nums, int target) {

        int left = 0, right = nums.length-1;

        int mid;

        while (left <= right) {

            mid = left + (right - left) /2;

            if(nums[mid] == target) {

                return mid;   

            } else if(target > nums[mid]) {

                left = mid+1;

            } else {

                right = mid -1;

            }

        }

        return -1;

    }

}

오늘의 문제는 이렇습니다.

입력값은 정렬된 배열과 target 값입니다.

전형적인 Binary search 예 입니다.

Target 값을 정렬된 배열에 순서에 맞게 넣으려면 몇번째에 넣어야 하는지 그 값을 알아내는 문제 입니다.

문제에 보면 반드시 O(log n) 이라야 한다고 돼 있습니다.

우선 O(N) 인 코드를 보겠습니다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int resultVal = 0;
        
        if(nums[nums.length-1] < target) { // 타겟값이 정렬된 배열의 마지막 값보다 크면 타겟값은 맨 마지막에 들어가야 함
            resultVal = nums.length;
        } else {
            for (int i=0; i < nums.length; i++) { // 배열 갯수 만큼 루프를 돌림
                if(nums[i] > target || nums[i] == target) { // 해당 값이 타겟 값보다 크거나 같으면 그 자리에 타겟 값을 넣는다.
                    resultVal = i; // 이 자리가 타겟 값이 들어가야 하는 자리이다.
                    break; // 더 이상 루프를 돌리지 않고 빠져 나간다.
                }
            }
        }
        return resultVal; // 해당 값을 반환한다.
    }
}

이렇게 해도 답은 나옵니다. 그런데 이 로직을 time complexity 는 O(N) 입니다.

Time Complexity 에 대해 서는 아래 유튜브에서 아주 잘 설명 한 것 같습니다.

https://youtu.be/tTFoClBZutw

그러면 이 문제를 O(log n)으로 로직을 만들라는 요청에 맞게 코딩을 하면 아래와 같게 됩니다.

(Binary search를 해야 하는데요. 정렬된 배열을 다룰 때는 처음부터 끝까지 검색하지 않고 중간 값을 타겟값과 비교해서 중간 값이 작으면 오른쪽 반을 검색하고 그렇지 않으면 왼쪽 반을 검색함으로서 검색시간을 줄 이도록 하는 겁니다. 그 방법은 아래와 같습니다.)

class Solution {
  public int searchInsert(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1; // 중간 값 pivot,왼쪽 값, 오른쪽 값을 담는 세가지 변수가 필요하다.
    while (left <= right) { // left 가 fight 보다 작거나 같은 경우에만 while문을 돌린다.
      pivot = left + (right - left) / 2; // pivot에 배열의 중간이 몇번째 인지 계산해서 넣는다.
      if (nums[pivot] == target) return pivot; // 그 중간 값이 타겟 값과 같으면 그 값이 정답이 된다.
      if (target < nums[pivot]) right = pivot - 1; // 중간에 위치한 값이 타깃보다 크면 왼쪽 반을 검색하기 위해서 right 값을 pivot -1로 한다.
      else left = pivot + 1; // 그렇지 않으면  오른쪽 반을 검색하기 위해서 left값을 pivot + 1로 한다.
    }
    return left; // 마지막에 남은 값을 반환한다.
  }
}

only code.

class Solution {
  public int searchInsert(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1;
    while (left <= right) { 
      pivot = left + (right - left) / 2; 
      if (nums[pivot] == target) return pivot; 
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1; 
    }
    return left; 
  }
}

이 로직을 Python으로 할 경우 아래와 같이 된다.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = (left + right) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return left

이번 문제는 아주 쉬운 문제 입니다.

입력값은 두 스트링 입니다.

건초더미 에서 바늘 찾기를 연상 케 하는 이름인데요. Haystack 과 needle 입니다.

- Needle이 haystack에 포함돼 있으면 몇번째에 needle이 시작하는지 그 값을 리턴합니다.

- 포함돼 있지 않으면 -1을 리턴하구요.

- needle 이 empty면 0을 리턴합니다.

이렇게 패턴은 아주 간단합니다.

코드는 심플하게 String 관련된 메소드 들 중 isEmpty(), contains() 그리고 split() 을 사용했습니다.

class Solution {
    public int strStr(String haystack, String needle) {
        String[] haySplit = haystack.split(needle);
        
        if(!haystack.contains(needle)) {
            return -1;
        } else if (haystack.equals(needle) || haySplit.length ==0 || needle.isEmpty()) {
            return 0;
        } else {
            return haySplit[0].length(); 
        }
    }
}

다른 사람들이 한 것을 보니까 막 for 문을 돌리고 그러던데... 이렇게 하는게 아주 간단하지 않을까요?