IT 기술 따라잡기

아이디와 이메일이 있는 Person이라는 테이블이 있습니다.

여기서 id는 키 컬럼이라서 유니크 합니다.

이메일에는 중복된 데이터가 들어갈 수 있습니다.

이메일이 중복 됐을 경우 하나만 남기고 나머지를 지워서 유니크하게 만드는 쿼리를 만들라는 문제 입니다.

이메일은 모두 소문자 입니다.

일단 하나 하나 접근해 보겠습니다.

테이블은 하나 이지만 이 하나인 테이블을 조인 할 수 있습니다.

우선 이 조인을 사용해서 이메일이 중복된 걸 찾아 보겠습니다.

SELECT p1.*
FROM Person p1,
    Person p2
WHERE
    p1.Email = p2.Email
;

이렇게 하면 중복된 이메일 리스트를 얻을 수 있습니다.

여기서 중복된 이메일들 중에 아이디가 더 큰 것을 골라 보겠습니다.

SELECT p1.*
FROM Person p1,
    Person p2
WHERE
    p1.Email = p2.Email AND p1.Id > p2.Id
;

이렇게 하면 지우고 싶은 데이터만 출력 되는 것을 보실 수 있습니다.

그러면 이 where 절을 사용해서 지우면 됩니다.

DELETE p1 FROM Person p1,
    Person p2
WHERE
    p1.Email = p2.Email AND p1.Id > p2.Id

이번 문제도 지난번 같이 SQL을 만드는 문제 입니다.

Customers와 Orders 테이블이 있고 여기서 한번도 주문을 하지 않은 사람만 골라 내는 문제입니다.

위의 예제에서 보면 Henry와 Max가 한번도 주문을 하지 않았습니다. 이런 고객만 골라서 display 해 주는 SQL문을 만들면 됩니다.

이건 간단하게 아래와 같이 풀 수 있습니다.

select customers.name as 'Customers'
from customers
where customers.id not in
(
    select customerid from orders
);

Where 문 에서 not in 을 사용하면 됩니다.

이밖에 LEFT JOIN 을 사용해서 아래와 같이 할 수 있습니다.

select Name as 'Customers'
from Customers c
LEFT JOIN Orders o
ON c.Id = o.CustomerId
where o.CustomerId IS NULL;

실행 시간은 둘 다 비슷한 것 같은데 첫번째 방법이 좀 더 안정적인 것 같네요.

오늘은 SQL쿼리를 만들어야 하는 문제 입니다.

Person이라는 테이블에 id 와 email이라는 컬럼이 있는데,
이 중에서 이메일이 두개 이상 되는 것을 찾아 내는 겁니다.

쉽게 생각하면 Group By와 Having을 사용해서 만들면 됩니다.

select Email
from Person
group by Email
having count(Email) > 1;

Email로 그룹바이 한 다음에 email count가 1을 넘는 Email을 표시하는 겁니다.

두 번째 방법으로는 Email과 Email count를 select 한 다음에 이 중에서 email count가 1 보다 큰 것만 표시하도록 하는 방법이 있습니다.

select Email from
(
    select Email, count(Email) as num
    from Person
    group by Email
) as statistics
where num > 1;

저는 이 방법 보다는 위에 첫번째 방법이 익숙한데…. 이렇게 해도 되겠네요.

그리고 이렇게 해도 됩니다.

select distinct p1.Email
from Person p1, Person p2
where p1.Email = p2.Email and p1.id != p2.id;

실행 결과 역시 첫번째 방법이 가장 빠른 것 같네요.

그냥 직관적으로 Group By와 Having을 사용하는게 제일 좋은 것 같습니다.

오늘 문제는 바로 이전 글에서 다룬 Climb Stairs와 기본적으로 같은 문제 입니다.

피보나치 수 입니다.

https://ko.wikipedia.org/wiki/피보나치_수

자바로 이것을 구현 하는 방법은 여러가지가 있습니다.

이전 글에서도 몇가지 살펴 보았고 이번 글에서도 몇가지 예를 배울 계획입니다.

이전 글 https://coronasdk.tistory.com/1185

그 중에 하나가 Recursion Function 인데요. 오늘은 이 방법을 이해해 보고 그 다음 예들을 간단히 살펴 보겠습니다.

피보나치 수에 대한 정의는 아래와 같습니다.

피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

공식은 F(n) = F(n-1) + F(n-2) 입니다.

코드는 아래와 같습니다.

class Solution {
    public int fib(int n) {
        if(n<=1) return n;
        return fib(n-1) + fib(n-2);
    }
}

여기서 Recursion Function이 사용 됩니다.

return fib(n-1) + fib(n-2) 는 아래와 같이 작동합니다.

자 그럼 이 Recursion Function을 이용한 코드를 보겠습니다.

class Solution {
    public int fib(int n) {
        if(n<=1) return n;
        return fib(n-1) + fib(n-2);
    }
}

위 그림을 이해했다면 이 코드는 쉽게 이해 할 수 있을 겁니다.

이제 다른 방법을 알아 볼까요?

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }
                  
        int[] cache = new int[N + 1];
        cache[1] = 1;
        for (int i = 2; i <= N; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
    
        return cache[N];
    }
}

이것은 피보나치 식을 재귀 함수를 이용하지 않고 for 루프를 이용해서 코드를 작성한 겁니다.

방법은 같습니다.

Runtime은 for loop가 조금 더 빠른 것 같습니다.

그 이외에 아래와 같은 방법들이 있습니다.

class Solution {
    // Creating a hash map with 0 -> 0 and 1 -> 1 pairs
    private Map<Integer, Integer> cache = new HashMap<>(Map.of(0, 0, 1, 1));

    public int fib(int N) {
        if (cache.containsKey(N)) {
            return cache.get(N);
        }
        cache.put(N, fib(N - 1) + fib(N - 2));
        return cache.get(N);
    }
}

-----------

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }

        int current = 0;
        int prev1 = 1;
        int prev2 = 0;

        for (int i = 2; i <= N; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
}

--------------------

class Solution {
    int fib(int N) {
        if (N <= 1) {
          return N;
        }
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        matrixPower(A, N - 1);

        return A[0][0];
    }

    void matrixPower(int[][] A, int N) {
        if (N <= 1) {
          return;
        }
        matrixPower(A, N / 2);
        multiply(A, A);

        int[][] B = new int[][]{{1, 1}, {1, 0}};
        if (N % 2 != 0) {
            multiply(A, B);
        }
    }

    void multiply(int[][] A, int[][] B) {
        int x = A[0][0] * B[0][0] + A[0][1] * B[1][0];
        int y = A[0][0] * B[0][1] + A[0][1] * B[1][1];
        int z = A[1][0] * B[0][0] + A[1][1] * B[1][0];
        int w = A[1][0] * B[0][1] + A[1][1] * B[1][1];

        A[0][0] = x;
        A[0][1] = y;
        A[1][0] = z;
        A[1][1] = w;
    }
}

--------------

수학 공식을 이용하는 방법

class Solution {
    public int fib(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, N) / Math.sqrt(5));
    }
}

실행결과 Runtime, Memory는 거의 모두 동일 합니다.

이번 문제는 꽤 유명한 문제 입니다.

계단을 오르는 데 한번에 한 칸을 올라가거나 혹은 두칸을 올라갈 수 있습니다.

계단의 숫자를 입력값으로 받은 후 그 계단을 올라 갈 수 있는 방법은 몇가지가 있을 지 계산해야 합니다.

패턴을 한번 보겠습니다.

1. 계단이 1개 이면 방법은 1개 입니다.

2. 계단이 2개 이면 방법은 한 칸- 한 칸, 한번에 두칸 이렇게 두가지 방법이 있습니다.

3. 계단이 3개면 방법은 3가지 입니다. 1번 방법과 2번 방법을 더하면 됩니다.

일단 한칸 올라온 다음에 남은 방법은 나머지가 두칸이니까 2번에서 구한 2가 됩니다.

이단으로 두칸 올라온 다음에 남은 방법은 나머지가 한칸이니까 2번에서 구한 1이 됩니다.

그래서 1+2 =3 이 됩니다.

4. 그러면 4 칸 일 때는 3번과 2번을 더한 값인 5가 되겠죠.

일단 한칸 올라간 다음에 남은 방법은 나머지가 3칸이니까 3번에서 구한 3 가지 입니다.

이단으로 두칸 올라간 다음에 남은 방법은 나머지가 2칸 이니까 2번에서 구한 2가 됩니다. 

그러면 3+2인 5가 됩니다.

5. 계단이 5개 이면 당연하 4번 더하기 3번이겠죠. 그러면 5+3이 되서 총 8가지 방법이 있습니다.

이렇게 되면 공식을 구할 수 있죠.

N(current) = N(previous) + N(previous-1) 이 됩니다.

이걸 로직으로 만들어서 코딩을 하면 됩니다.

저에게 가장 쉬운 방법은 아래 방법입니다.

class Solution {
    public int climbStairs(int n) {
        if(n <=2) return n;
        
        int prev1 = 1;
        int prev2 = 2;
        int cur= prev1 + prev2;
        
        while(n>=3) {
            cur = prev1 + prev2;
            prev1 = prev2;
            prev2 = cur;
            n -= 1;
        }
        return cur;
    }
}

실행 결과는 아래와 같습니다.

다른 설명서 보니까 이런 방법도 있던데...

class Solution {
    public int climbStairs(int n) {
        return climb_Stairs(0,n);
    }
    
    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        
        if(i == n) {
            return 1;
        }
        
        return climb_Stairs(i+1, n) + climb_Stairs(i+2, n);
    }
}

이해하기도 어렵고 별로 좋은 방법인 것 같지는 않습니다.

Runtime을 조금 더 줄이려면 아래 방법이 있습니다.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

이런 방법도 있고요.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Runtime은 모두 비슷하고 바로 위 코드가 메모리를 조금 덜 차지하는 것 같습니다.

그 다음에 제가 이해하기 힘든 코드는 아래 두가지가 있습니다.

수학 공식을 사용하던데...

 public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

그리고

public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double phi = (1 + sqrt5) / 2;
        double psi = (1 - sqrt5) / 2;
        return (int) ((Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / sqrt5);
    }

어쩄든 제가 만든 첫번째 스크립트하고 Runtime하고 Memory 결과 값은 비슷하더라구요.

첫번째 제가 시도한 방법은 Fibonacci Number라고 합니다.

Fibonacci Number에 대해 나중에 한번 살펴 봐야 겠습니다.

오늘은 이만......

이번 문제의 입력값은 숫자로된 배열 인데 모두 쌍으로 되어 있고 하나만 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

이중 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

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

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)
}

오늘의 문제는 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 를 보이는 군요.

잘 배워 둬야 겠습니다.

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

문제는 아주 쉬웠다.

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

이걸 조금 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까지 했어야 됐는지...

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

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

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

이번 문제는 두개의 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()를 사용하지 않은 방법이 더 속도가 빠른것을 알 수 있습니다.

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