IT 기술 따라잡기

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

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

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

패턴을 한번 보겠습니다.

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에 대해 나중에 한번 살펴 봐야 겠습니다.

오늘은 이만......

지난달 9월 18 일 일요일에 집 근처 Lake Wilderness에서 철인 3종 경기가 열렸다.

이름은 IRONMAN 70.3 Washington이다.

구경하면서 찍은 비디오 클럽들이 있는데 딱히 유투브 영상 만드느라고 시간 들이기 아깝고 귀찮아서 방치해 두고 있었는데...

얼마 전 봤던 iMovie의 Magic Movie기능이 생각 났다.

일찍 잠에서 깨서 (나이 들 수록 아침 잠이 없어진다.) 뒤척거리다가 iPad를 켰다.

IMovie를 열고 그 때 찍었던 비디오들을 선택한 다음에 매직 무비 를 선택했다.

최근 순서대로 정렬 하는 바람에 일일이 매뉴얼로 다시 역순으로 배치했다.

그건 다음 나온 결과는.... 개인적으로 보기에 만족했다.

이거 편집 하려면 최소한 하루 온 종일 작업해야 하는데 그냥 순식간에 3분짜리 동영상을 만들어 버렸다.

https://youtu.be/w8DFagJ1PuU

이렇게 끝내기 아쉬워서 마무리에서 관련된 그림을 넣어 보기로 했다.

그림은 인공지능 화가인 DALL-E 2에게 맡겼다.

Description 은

Draw oil paintings of a man and an woman cheering after completing the triathlon at Maple Valley. 

메이플 밸리에서 열린 철인 3종경기를 완주하고 환호하는 남자와 여자를 유화로 그리라는 내용이다.

결과는

완전 마음에 들었다.

이렇게 점점 AI 가내 생활에 들어 오고 있나보다.

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

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

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

https://coronasdk.tistory.com/1150

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했지만 이렇게 까지 수학을 이용해서 코딩 해 본 적은 솔직히 없습니다.

좋은 걸 배웠지요.

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/

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

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

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

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

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

https://youtu.be/mR3C2wkFfGU

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

윤석열 대통령이 바이든과의 만남 후 한 "국회에서 이XX들이 통과 안 해 주면 바이든은 쪽팔려서 어떡하냐." 라는 막말이 한국은 물론 해외에서도 퍼져 나가고 있습니다.

AFP통신 발 이 기사는 제목이 남한 대통령이 한 미국에 대한 비판적인 hot mic (마이크 커진 줄 모르고 한 말) 이 퍼져 나가고 있다 입니다.

AFP 통신은 이 막말을 영어로 아래와 같이 번역 했습니다.

“How could Biden not lose damn face if these f**kers do not pass it in Congress?”

이 XX들이는 영어로 f**kers로 번역을 했고 쪽 팔려서는 lose damn face로 번역 했습니다.

AFP는 한국의 대통령실에 입장을 물어 봤지만 No Comment 였다고 전했습니다.

Lose face 는 면을 잃다, 체면을 구기다 정도로 해석되는데 여기에 damn을 넣어서 쪽팔리다 라는 의미를 전달했내요.

기사 링크와 전문은 아래에 있습니다.

https://www.dawn.com/news/1711411

Already battling record-low approval ratings, South Korea’s President Yoon Suk-yeol has landed in trouble again after his disparaging remarks about key ally the United States were caught on a hot mic.

이미 기록적인 저조한 지지율을 보이고 있는 남한의 대통령 윤석열이 핵심 우방인 미국에 대한 폄하 발언을 한 hot mic가려져 문제가 되고 있다.

Yoon, a political novice who took office in May, is in New York for the United Nations General Assembly, and chatted on Wednesday with Joe Biden during a photo op at the Global Fund where the US President had just pledged $6 billion.

지난 5월 취임한 정치 초보자 윤씨는 유엔 총회를 위해 뉴욕을 방문 중이며 수요일에 미국 대통령이 막 60억 달러를 약속한 글로벌 펀드에서 조 바이든과 사진 촬영을 하는 동안 담소를 나눴다.

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

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

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