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

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

카테고리


반응형



저작권료에 대해 부정적인 나로서는 이 유투브 클립이 반가왔다.
이 세상에 무에서 유의 창조가 어디 있는가?

아이는 온 마을이 기른다는 옛말이 있다.
교통 통신이 발달한 지금은 전 세계가 한 아이를 키우는 것이다.

그 아이가 평생에 걸쳐 나오는 모든 것은 그가 접한 모든 것들의 혼합과 변형이다.

그 결과를 한 사람의 독점적 이윤 획득의 수단으로 규정 짓는게 올바른 일이라고 나는 생각하지 않는다.

그 결과물 들로부터 막대한 자본 이익이 생긴다면 그를 있게 한 이 세상에도 수익이 돌아가도록 해야 올바르다고 생각한다.

요즘 표절 관련 목소리들이 많이 나온다.

표절을 너무 과하게 적용하는 것 같다.

표절을 했다는 원곡 조차도 그 원곡자 의 100% 창작물이 아니다.

100층 건물 꼭대기에 피뢰침을 꽂을 수 있는 이유는 그 건물의 모든 층들이 있기 때문이고
그것을 꽂아야 되는 이유는 번개를 만들어 내는 기후, 그리고 그 기후를 만들어 내는 지구의 움직임.. 그 지구의 움직임을 만들어 낸 빅뱅으로부터 기인한다.

그런 것 없는 피뢰침은 탄생할 수 없었다.

 

https://youtu.be/tPrrHB-YSBQ

 

반응형

Leetcode - 58. Length of Last Word - Easy

2022. 8. 25. 10: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으로 맨 끝에 스페이스가 있다면 없애 주고요.

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

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

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

 

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

반응형

Leetcode - 326. Power of Three - Easy

2022. 8. 25. 09:23 | Posted by 솔웅


반응형

이번에 다룰 문제는 입력값이 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

 

Leetcode - 242. Valid Anagram : Easy

오늘의 문제는 이것입니다. 2개의 Strings가 input이고 그 두개의 문자열이 같은 문자들을 포함하고 있으면 (순서는 바뀌어도 됨) true 이고 아니면 false 입니다. 먼저 Pattern을 찾아 보겠습니다. 1. 두

coronasdk.tistory.com

 

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

 

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 관리 면에서 훨씬 더 나은 방법인데요.

 

반응형

Leetcode - 704. Binary Search - Easy

2022. 8. 22. 12:44 | Posted by 솔웅


반응형

지난 글에서 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

 

 

반응형

Leetcode - 28. Implement strStr() - Easy

2022. 8. 18. 08:45 | Posted by 솔웅


반응형

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

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

건초더미 에서 바늘 찾기를 연상 케 하는 이름인데요. 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 문을 돌리고 그러던데... 이렇게 하는게 아주 간단하지 않을까요?

반응형

Leetcode - 27. Remove Element - Easy

2022. 8. 18. 07:29 | Posted by 솔웅


반응형

이번 문제는 아래와 같습니다.

 

입력값은 int 배열과 int 숫자 입니다.

결과 값은 해당 배열에서 두번쨰 입력값 인 숫자를 제외한 나머지 숫자들의 갯수 입니다.

 

첫번째 예제를 보면 입력값이 3,2,2,3 과 3인 경우 3을 제외하면 2,2 가 남으니 정답은 2 가 됩니다.

두번째 예제는 입력값이 0,1,2,2,3,0,4,2 와 2 이니 2를 제외하면 0,1,3,0,4 가 남으니 정답은 5가 됩니다.

 

이번 문제는 비교적 쉬운것 같습니다.

 

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0; // 결과 값을 저장할 변수 
        for(int j=0; j < nums.length; j++) { // 입력된 배열의 아이템 숫자 만큼 for 문을 돌린다.
            if(nums[j] != val) { // 배열 내 해당 숫자가 입력된 val과 같지 않으면 아래 문을 실행한다.
                nums[i] = nums[j]; // nums의 i 번째에 nums의 j번째를 넣는다.
                i++; // i를 1씩 증가한다.
            }
        }
        return i;
    }
}

 

어떻게 돌아가나 알아보기 위해 for 문과 if 문 사이에 프린트 문을 넣어 봤습니다.

 

 

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

첫번째 루프에서는 배열의 첫번째 값인 3과 입력값인 3이 같기 때문에 if 문이 실행 되지 않습니다.

그렇기 때문에 j와 i는 모두 초기값인 0이 됩니다.

 

두번째 루프에서는 j 가 1이 되고 두번쨰 값인 2와 입력값인 3이 같지 않기 때문에 if 문이 실행이 되어서 i에 1이 더해 집니다.

세번째도 값이 2이니까 if 문에 실행 되어서 i에 1이 더해 집니다. 그래서 i 값은 2가 됩니다.

네번쨰는 값이 3이라서 if 문이 실행 되지 않습니다. If 문이 실행 되지 않아서 i는 여전히 2 입니다.

 

For 루프문이 다 돌았기 때문에 i 값인 2가 반환 됩니다.

 

조금 다르게 접근 할 수도 있습니다.

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        
        while(i < n){ // 배열의 아이템 개수만큼 루프를 돌립니다.
            if(nums[i] == val) { // 해당 값이 Val 과 같으면
                nums[i] = nums[n-1]; // 해당 값은 그 이전 값 배열의 n 번째 숫자 (첫번쨰 루프 라면 맨 마지막 숫자인 3이 됨)
                n--; // n에서 1을 제외 한다. 
            } else {
                i++; // 같지 않으면 i를 1 증가 시킨다.
            }
        System.out.println("i is " + i + " n is " + n);
        }
        return n;
    }
}

 

 

반응형


반응형

오늘의 문제는 정렬된 int 배열에서 겹친 숫자를 제외한 숫자는 몇개 인지 알아내는 문제 입니다.

문제에서 조건은 새로운 배열을 만들어서 풀지 말고 입력된 배열을 그냥 수정해서 답을 구하라는 겁니다.

 

예제를 보면 첫번째 배열 1,1,2 의 경우 2를 리턴 해야 합니다. 왜냐하면 중복된 숫자를 제외한 값은 1과 2 두 개 이기 때문입니다.

두번째 예제는 중복 된 값을 제외하면 남는 숫자들은  0,1,2,3,4 입니다. 정답은 5가 됩니다.

 

그럼 이제 패턴을 생각해 보겠습니다. (두번째 예제의 입력값을 보겠습니다.)

 

입력값은 일단 오름차순으로 정렬 돼 있습니다.

그러니까 첫번째 숫자는 제일 작은 숫자입니다. (0)

두번째 숫자를 첫번째 숫자와 비교해서 같은 숫자 이면 0은 중복된 숫자 입니다.

그러면 세번째 숫자를 비교 합니다. 세번째 숫자 1 과 두번째 숫자 0은 같지 않기 때문에 1을 두번째 자리에 놓습니다.

 

그러면 이제 0,1,1,1,1,2,2,3,3,4 가 됩니다. 처음 입력값은 0,0,1,1,1,2,2,3,3,4 이었습니다.

네번째 숫자 1은 세번째 숫자와 같습니다. 넘어 갑니다. 다섯번째 숫자도 1입니다. 넘어갑니다.

여섯번째 숫자는 2 입니다. 그 전 숫자와 다릅니다. 그러면 이 2를 세번째 자리에 넣습니다.

이제 배열은 0,1,2,1,1,2,2,3,3,4 가 됐습니다.

일곱번째 숫자는 2 입니다. 이전 숫자와 같으니 넘어가고 여덟번째 숫자는 3입니다.

그럼 이 3을 네번째 자리에 넣습니다.

0,1,2,3,1,2,2,3,3,4 이제 배열은 이렇게 됐습니다.

다음은 아홉번째 숫자 차례 3이니까 넘어가고 마지막 열번째 숫자는 4. 그 이전 3과는 다르죠.

이 4를 다섯번째 자리에 넣습니다.

이제 배열의 모든 값을 살펴 봤습니다.

배열은 이렇게 됐습니다.

0,1,2,3,4,   2,2,3,3,4

중복된 숫자를 제외하면 0,1,2,3,4 가 남으니 정답은 5개 입니다.

 

이걸 코딩 하려면 두가지 값을 다루어야 합니다.

우선 입력된 배열 속의 숫자들을 모두 살펴봐야 하니까 그 배열의 아이템 개수를 다루어야 합니다.  Array.length

다음은 새로 나온 숫자를 제자리에 넣을 때 사용할 숫자를 다루어야 합니다. InsertIndex 로 변수 이름을 정하겠습니다.

 

코딩과 결과 값은 아래와 같습니다.

 

 

입력값이 1,1,2 인 경우 1,2 가 중복된 숫자를 제외한 결과 이기 때문에 2를 리턴합니다.

입력값이 0,0,1,1,1,2,2,3,3,4 인 경우 중복된 숫자를 제외한 결과가 0,1,2,3,4 이기 때문에 5가 리턴 됩니다.

 

소스는 아래와 같습니다.

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length; // 배열의 아이템 개수. For 문에서 사용 됨.
        if(n == 0) {
            return 0; // 입력된 배열이 empty이면 0을 반환한다.
        }
        
        int insertIndex = 1; // 새로운 숫자를 찾았을 때 삽입할 위치. 배열의 첫번째 숫자 다음에 입력하면서 시작하기 위해 값은 1이 된다.
        
        for (int i=1; i < n; i++) { // 입력된 배열의 모든 아이템 숫자를 비교하기 위해 length만큼 for문을 돌린다.
            if(nums[i] != nums[i-1]) { // 해당 숫자가 그 이전 숫자와 같지 않으면 if 문 내의 코드를 실행한다.
                nums[insertIndex] = nums[i]; // insertIndex 위치에 해당 숫자를 insert 한다.
                insertIndex++; // insertIndex의 값을 1 증가 시킨다.
            }
        }
        return insertIndex; // insertIndex 값을 리턴한다.
    }

 

이번 문제의 핵심은 새로운 배열을 생성하지 말라는 것과 중복된 숫자를 제외한 숫자들의 개수를 알아내라는 겁니다.

패턴만 잘 파악한다면 코딩하기에는 그렇게 까다롭지만 않은 문제 입니다.

반응형

Leetcode - 20. Valid Parentheses - Easy

2022. 8. 14. 01:16 | Posted by 솔웅


반응형

이번 문제는 여는 괄호와 닫는 괄호의 쌍이 맞는지 안 맞는지 구별해 내는 문제입니다.

 

 

괄호는 () [] {} 이렇게 세 종류 입니다.

우선 로직을 생각하기 위해서 패턴을 생각해 보겠습니다.

 

((())), (){()}[[{()}]]

이렇게 되면 true 입니다. 여는 괄호와 닫는 괄호 다 제대로 짝이 맞으니까요.

 

(], (({[{})]))

이런 식으로 되면 false 입니다. 4번째 [ 의 짝이 ) 으로 돼 있어서 맞지 않습니다.

 

여기서 패턴을 생각해 볼 수 있습니다.

1. 여는 괄호 일 때는 true , false를 생각 할 필요가 없다.

2. 첫번째 닫는 괄호가 나오면서 가장 가까운 여는 괄호와 짝이 맞아야 한다.

3. 두번째 닫는 괄호가 나오면서 가까운 두번째 여는 괄호와 짝이 맞아야 한다.

4, 5, 6 ......

 

1번과 2번 패턴까지는 쉽게 로직이 완성 될 것 같은데 3번 서 부터는 좀 복잡해 집니다.

그러면 2번에서 패턴을 다 만족할 수 있도록 로직을 만들 필요가 있습니다.

 

항상 가장 가까운 여는 괄호와 비교 하도록 만들면 됩니다.

그렇다면 한번 짝이 맞는다고 검증되면 그 여는 괄호를 없애면 다음 닫는 괄호는 다시 가장 가까운 여는 괄호와 비교하면 됩니다.

 

그렇다면 패턴은 아래와 같이 정리 될 수 있다.

1. 여는 괄호 일 때는 true , false를 생각 할 필요가 없다.

2. 첫번째 닫는 괄호가 나오면서 가장 가까운 여는 괄호와 짝이 맞아야 한다.

3. 2번에서 짝이 맞으면 해당 여는 괄호를 없애고 1번과 2번을 반복한다.

4. 2번에서 짝이 안 맞으면 false를 반환한다.

5. 모든 짝이 맞으면 true를 반환한다.

 

이제 이 패턴을 만족시키는 로직을 만들 차례다.

우선 어떤 API 메소드를 사용할 지 생각해 보자.

여는 괄호를 쌓다가 짝이 맞으면 하나씩 없앨 것이다.

 

그렇다면 Stack을 사용해서 push()와 pop()메소드들을 사용하면 된다.

IsEmpty()를 사용해서 마지막에 체크를 하면 된다.

 

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

 

Stack (Java Platform SE 7 )

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item o

docs.oracle.com

 

 

그 다음에는 여는 괄호와 닫는 괄호의 맞는 쌍을 비교해야 되니까 Map을 사용하면 좋을 것 같다.

 

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

 

Map (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

 

이것을 통해서 만든 코드와 output은 아래와 같다.

 

어떻게 작동하는 지 보기 위해 여기저기 로그를 프린트 하도록 했다.

입력값은 "(()){}[{())]" 이다.

그리고 stdout 을 보면 아래와 같다.0 c is (
1 c is (
2 c is )
2 open is (
*** 2 open is (, c is )
3 c is )
3 open is (
*** 3 open is (, c is )
4 c is {
5 c is }
5 open is {
*** 5 open is {, c is }
6 c is [
7 c is {
8 c is (
9 c is )
9 open is (
*** 9 open is (, c is )
10 c is )
10 open is {
*** 10 open is {, c is )

 

처음 두 열린 괄호는 stack에 넣는다. 처음으로 닫힌 괄호 )가 나왔다.바로 직전 열린 괄호를 보니 ( 여서 짝이 맞는다. 그러면 통과하고 해당 (는 stack에서 제외한다.그 다음도 닫힌 괄호 ) 있고 직전 열린 괄호는 ( 이니 통과하고 해당 (는 stack에서 제외 한다.(()) 부분은 검증이 다 끝났고 현재 Stack에는 아무 것도 없다. 그 다음 { 는 스택에 넣고 그 다음을 보니 } 이므로 짝이 맞으니까 통과하고 {는 스택에서 제외.{}도 검증 됐고 Stack에는 아무것도 없는 상태 

 

입력값 중에서 [{())] 를 검증해야 한다.[ 는 열린 괄호이니 스택으로, 그리고 { 도  스택으로 그리고 ( 도...이제 스택에는 [{( 가 있다.다음은 닫힌 괄호 ) 이다. 보니까 가장 가까운 열린 괄호는 ( 이니까 짝이 맞다. 그러면 통과 하고 (는 스택에서 제외.이제 스택에는 [{ 가 있다.다음을 보니까 닫힌 괄호 ) 이다. 스택에는 { 이 있다.짝이 맞지 않으니까 여기서 이 입력값은 invalid 판정이 나게 된다.그래서 결과는 false.

 

전체 코드를 보면 아래와 같다.

class Solution {

    private static final Map<Character, Character> map 

        = Map.of('(', ')',

                 '{','}',

                 '[',']');

    

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();

        for(char c : s.toCharArray()) {

            if(map.containsKey(c)) {

                stack.push(c);

            } else {

                if(stack.isEmpty()) {

                    return false;

                }

                char open = stack.pop();

                if(map.get(open) != c) {

                    return false;

                }

            }

        }

        return stack.isEmpty();

    }

}

 

우선 (),[],{} 쌍을 Map에 넣는다.

그리고 isValid 안에서 Stack을 만든다.

입력된 스트링의 아이템 갯수 만큼 for 문을 돌린다.

 

해당 아이템이 Map의 key 이면, 즉 열린 괄호이던 stack 에 push 한다.

Key 가 아니면 stack에 있는 key와 짝이 맞는지 비교한다. Stack이 비어 있거나 짝이 맞지 않으면 false를 반환한다.

 

For 문을 다 돌고 나서 stack에 아무 값도 없으면 모든 짝이 다 맞는 것이니까 입력값은 Valid하고 true를 리턴한다.

 

 

반응형
이전 1 2 다음