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

최근에 받은 트랙백

글 보관함

Leetcode 119. Pascal's Triangle II (Easy)

2022. 9. 29. 04: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


윤석열 대통령이 바이든과의 만남 후 한 "국회에서 이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

 

South Korean president’s hot mic US criticism goes viral

The crude comments appear to refer to Biden's drive to increase US funding to the Global Fund, which would require congressional approval.

www.dawn.com

 

 

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억 달러를 약속한 글로벌 펀드에서 조 바이든과 사진 촬영을 하는 동안 담소를 나눴다.

“How could Biden not lose damn face if these f**kers do not pass it in Congress?” Yoon was caught saying to his aides afterwards in footage that went viral in South Korea.

윤씨는 이후 한국에서 급속도로 퍼진 영상에서 자신의 측근들에게 이런 말을 하는 것이 포착됐다.

"국회에서 이 XX들이 승인 안 해 주면 바이든은 쪽팔려서 어떡하냐?"

 

A YouTube video of Yoon’s comments racked up over two million views just hours after it was posted, and “f**kers” became the number one trending topic on Twitter in South Korea on Thursday.

 

윤씨의 코멘트가 담긴 이 유튜브 영상은 게시된 지 몇 시간 만에 조회수 200만 회를 넘어섰고, 목요일 한국 트위터에서 'f**kers'가 trending topic 에서 1위를 차지했다.

 

“The president’s words and actions are the national dignity of the country,” one YouTube commenter wrote.

 

한 유튜브 댓글은 “대통령의 말과 행동이 국가의 존엄이다." 라고 언급했다.

 

Yoon’s crude comments appear to refer to Biden’s drive to increase US funding to the Global Fund, which would require congressional approval.

 

윤의 이 거친 발언은 바이든이 의회 승인이 필요한 글로벌 펀드에 대한 미국 자금 지원을 늘리려는 움직임을 가리키는 것으로 보인다.

 

The United States is South Korea’s key security ally, with Washington stationing about 27,000 troops in the country to help counter nuclear-armed North Korea.

 

미국은 한국의 주요 안보 동맹국으로, 워싱턴은 핵무장한 북한에 대응하기 위해 약 27,000명의 병력을 한국에 주둔시키고 있습니다.

 

Yoon, a former prosecutor, has made what analysts describe as a string of unforced errors during his first months in office, which is typically a honeymoon period for new presidents in South Korea.

 

전직 검사였던 윤은 일반적으로 한국의 신임 대통령에게 주어지는 honeymoon 기간인 취임 첫 달 동안 분석가들이 string of unforced errors라고 표현하는 일련의 실책을 범했다.

 

At one point, his approval rating dropped to 24 per cent, although it has since inched up to 32 percent.

 

한때 그의 지지율은 24%로 떨어졌지만 이후 32%까지 올랐다.

 

His predecessor, Moon Jae-in, enjoyed approval ratings of about 70pc at the same stage in his term, polling data showed, and Yoon started work with 52 percent of people polled thinking he was doing a good job.

 

여론조사 데이터에 따르면 그의 전임자인 문재인 대통령은 임기 내 같은 단계에서 약 70%의 지지율을 누렸고, 윤 후보는 설문조사에 따르면 임기 시작 할 때 52%의 지지율로 시작했었다.

 

The hot mic comments come just days after Yoon’s office was forced to defend his decision to skip paying respects to Queen Elizabeth II’s coffin lying in state, allegedly due to “heavy traffic”.

 

이 hot mic 발언은 윤의 대통령실이 엘리자베스 2세 여왕에 대한 조문을 하지 않기로 한 그의 결정을 "교통체증" 떄문이라고 변호해야 했던 지 며칠 만에 나온 것입니다.

 

In August, he was also criticised for a chaotic official response to US House Speaker Nancy Pelosi’s visit to South Korea, where she landed after a contentious stop in Taiwan.

 

지난 8월에는 낸시 펠로시 미 하원의장이 논쟁적인 대만 방문 후 한국을 방문 때 official한 대응이 혼란스러웠다는 비판을 받기도 했다.

 

Yoon’s critics were swift to seize on his latest alleged gaffe.

 

윤의 이 과실은 비평가들에 의해 빠르게 평가 됐다. 

 

Yoon’s “foul language tarnishing the US Congress caused a major diplomatic mishap,” said Park Hong-keun, floor leader of the opposition Democratic Party.

 

야당인 더불어민주당 박홍근 원내대표는 “윤대통령이 미 의회를 더럽히는 욕설이 외교적으로 큰 타격을 입혔다”고 말했다.

 

Yoon’s office told AFP it had no comment on the incident.

 

윤의 대통령실은 AFP에 이번 사건에 대해 논평이 없다고 전했다.

 

반응형

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. 17. 03: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

Leetcode - 88. Merge Sorted Array - Easy

2022. 9. 7. 05: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. 3. 06: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. 3. 05: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

이전 1 2 다음