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

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

카테고리

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를 리턴한다.

 

 

반응형

Leetcode - 14. Longest Common Prefix - Easy

2022. 8. 11. 03:05 | Posted by 솔웅


반응형

오늘의 문제는 스트링 배열 들이 공통으로 가지고 있는 prefix 를 찾는 문제 입니다.

이 문제를 다루려면 우선 String API 중 indexOf() 와 substring() 메소드를 알아야 합니다.

IndexOf()는 원하는 글자가 어떤 스트링 에 몇번째에 있는지 알 수 있는 메소드 입니다. 그 글자가 없으면 -1이 반환됩니다.

Substring()은 해당 스트링의 일부 문자만 가져오고 싶을 때 사용합니다.

 

이 두 메소드를 활용해서 만든  코드는 아래와 같습니다.

 

로직은 우선 첫번째 String과 두번째 String의 prefix부터 먼저 구하고 나머지를 순차적으로 구하는 겁니다.

알아보기 쉽게 하기 위해서 여러곳에 System.out.println()을 넣었습니다.

우선 루프 이전을 살펴보면...

 

class Solution { // 클래스 이름은 Solution

    public String longestCommonPrefix(String[] strs) { // 메소드 이름은 longestCommonPrefix 이고 입력값으로 스트링 배열인 strs를 받고 출력값은 String 이 됩니다.

        String returnValue = ""; // 일단 출력할 String 변수를 생성했습니다. 초기값은 "" 로 했습니다.

        

        if(strs.length == 0) return returnValue; // 입력값이 없으면 "" 를 반환합니다.

        String prefix = strs[0]; // prefix에 입력값의 첫번째 스트링을 넣습니다.

 

일단 입력값은 ["flower","flow","flight", "flown"] 로 가정하겠습니다.

여기서 prefix 는 첫번째 스트링인 flower가 됩니다.

 

이제 루프문을 보겠습니다.

 

for(int i=1; i < strs.length; i++) { // 루프는 입력값의 스트링 숫자만큼 돕니다. 이 경우에는 4번 돕니다.

            System.out.println(i + " prefix is " + prefix); // 위에 설정했듯이 첫번째 루프에서 prefix는 flower 입니다.

            System.out.println(i + " strs is " + strs[i]); // 첫번쨰 루프에서는 strs[1]이니까 두번쨰 스프링인 flow가 그 값이 됩니다.

            while(strs[i]. indexOf(prefix) !=0) { // 이걸 풀면 flow.indexOf(flower)가 되고 flow안에는 flower가 없으니까 -1이 되서 while문을 안으로 들어가게 됩니다.

                prefix = prefix.substring(0, prefix.length() - 1); // prefix가 없으니까 prefix에서 맨 마지막 글자를 뺍니다. 그러면 flower에서 r이 빠져서 prefix는 이제 flowe가 됩니다.

                System.out.println(i + " in while prefix is " + prefix); // prefix가 flowe가 됐으니까 stout에 flow가 출력 됐습니다.

                

                if(prefix.isEmpty()) return returnValue; //prefix가 empty 일 경우 return 하는데 이 경우에는 실행 되지 않습니다.

            }

        }

 

이제 prefix가 flowe가 된 상태에서 다시 시작 합니다.

While 문을 보면 flow.indexOf(flowe)가 되기 때문에 여전히 -1 입니다.

그러면 prefix는 flowe에서 e가 빠진 flow가 됩니다.

그러면 다시 while문을 돌게 되죠.

 

이번에는 flow.indexOf(flow)가 되기 때문에 while문은 0 이 되기 때문에 이 while문을 빠져 나와서 for문을 다시 돌게 됩니다.

 

이제 i 는 ++ 가 되서 2가 됩니다.

그러면 이제 flight을 비교 하게 됩니다.

첫번째 while 문에서는 flow.indexOf(flight) 가 되서 -1 이므로 while 문 안으로 들어가게 됩니다.

그러면 flow에서 w가 빠져서 flo가 됩니다.

While문이 다시 돌게 되고 flo.indexOf(flight)는 -1이므로 prefix는 다시 fl로 바뀝니다.

다음 while문에서는 fl.indexOf(flight)이 0이 되므로 while문을 빠져 나와서 다시 for 문으로 갑니다.

 

이제 i 는 3이 되고 strs[3] 이마로 flown을 비교하게 됩니다.

prefix는 이제 fl입니다.

 

이제 while문에서 fl.indexOf(flight)이 되므로 while문은 그냥 빠져 나오게 됩니다.

그럼 다시 for 문으로 가는데 i 는 4가 되서 strs.length와 같게 되기 때문에 for 문도 빠져 나오게 됩니다.

 

For 문을 빠져 나오면서 아래 코드를 만나게 됩니다.

 

returnValue = prefix; // prefix 가 fl이 됐기 때문에 returnValue에는 이 값이 할당 됩니다.

        return returnValue; // 그 값을 return 합니다.

    }

}

 

이 로직은 이렇게 됩니다.

전체 코드를 다시 보면 이렇습니다.

class Solution {

    public String longestCommonPrefix(String[] strs) {

        String returnValue = "";

        if(strs.length == 0) return returnValue;

        String prefix = strs[0];

        

        for(int i=1; i < strs.length; i++) {

            while(strs[i]. indexOf(prefix) !=0) {

                prefix = prefix.substring(0, prefix.length() - 1);

                if(prefix.isEmpty()) return returnValue;

            }

        }

        

        returnValue = prefix;

        return returnValue;

    }

}

 

이 외에 다른 접근 법으로는 아래와 같은 것들이 있습니다.

 

Approach 2: Vertical scanning

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length() ; i++){
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}

 

Strs[0] 은 flower가 됩니다.

for문은 이 flower의 글자 수(6) 만큼 돌리게 됩니다.

우선 char c에는 f가 담기게 되죠. 

두번째 for 문은 입력된 String 갯수 만큼 돕니다.

입력값이  ["flower","flow","flight", "flown"] 이면 두번째 for 문은 4번 돌겠다.

 

If 문에서는 두번째 스트링이 empty거나 empty가 아니더라도 첫번째 글자가 f가 아니면 empty를 반환합니다.

If에 걸리지 않으면 계속 두번째 for 문을 돕니다. 

모든 스트링이 if 문에 걸리지 않았다면 모두 f는 공통으로 가지고 있다는 것이 됩니다.

 

그러면 다시 첫번째 for 문으로 가서 i 가 1이 되고 char c 는 fl이 됩니다.

두번째 for 문이 돌게 되는데 모든 스트링이 다 fl을 가지고 있으므로 두번째 for 문을 빠져 나와서 첫번째 for 문을 다시 돌게 됩니다.

 

이제 i는 2가 되고 char c 는 flo가 됩니다.

이제는 두번째 for 문 안에 있는 if 문에 걸리게 됩니다.

그러면 그 if 문 안에 있는 strs[0].substring(0,i); 이 실행 되게 되고 i는 2 이기 때문에 fl 이 리턴되게 됩니다.

 

다른 방법도 있습니다.

 

Approach 3: Divide and conquer

 

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

 

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

 

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs)
        minLen = Math.min(minLen, str.length());
    int low = 1;
    int high = minLen;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (isCommonPrefix(strs, middle))
            low = middle + 1;
        else
            high = middle - 1;
    }
    return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len){
    String str1 = strs[0].substring(0,len);
    for (int i = 1; i < strs.length; i++)
        if (!strs[i].startsWith(str1))
            return false;
    return true;
}

 

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

public String longestCommonPrefix(String q, String[] strs) {

    if (strs == null || strs.length == 0)

         return "";  

    if (strs.length == 1)

         return strs[0];

    Trie trie = new Trie();      

    for (int i = 1; i < strs.length ; i++) {

        trie.insert(strs[i]);

    }

    return trie.searchLongestPrefix(q);

}

 

 

class TrieNode {

 

    // R links to node children

    private TrieNode[] links;

 

    private final int R = 26;

 

    private boolean isEnd;

 

    // number of children non null links

    private int size;    

    public void put(char ch, TrieNode node) {

        links[ch -'a'] = node;

        size++;

    }

 

    public int getLinks() {

        return size;

    }

    //assume methods containsKey, isEnd, get, put are implemented as it is described

   //in  https://leetcode.com/articles/implement-trie-prefix-tree/)

}

 

public class Trie {

 

    private TrieNode root;

 

    public Trie() {

        root = new TrieNode();

    }

 

//assume methods insert, search, searchPrefix are implemented as it is described

//in  https://leetcode.com/articles/implement-trie-prefix-tree/)

    private String searchLongestPrefix(String word) {

        TrieNode node = root;

        StringBuilder prefix = new StringBuilder();

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

            char curLetter = word.charAt(i);

            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {

                prefix.append(curLetter);

                node = node.get(curLetter);

            }

            else

                return prefix.toString();

 

         }

         return prefix.toString();

    }

}

 

 

 

 

 

 

반응형

Leetcode - 13. Roman to Integer - Easy

2022. 8. 8. 04:39 | Posted by 솔웅


반응형

오늘의 문제는 로마 숫자를 아라비아 숫자로 바꾸는 로직을 만드는 것이다.

 

우선 로마자의 규칙 부터 알아야 한다.

 

위 그림에서 나왔듯이 M은 1000 이고 ... I 는 1 이다.

그러면 순서대로 MDCLXVI 이렇게 쓰면 이건 아라비아 숫자로 무엇일까?

일단 M은 1000이고 D는 500 이다. 그러면 여기 끼지는 두 숫자를 더해서 1500이 된다.

그런데 다음은 C이고 100을 의미한다. 그러면 1500에서 100을 더해서 1600이 된다.

이렇게 숫자들을 더하면 된다. 

그러면 1600 + 50 (L) + 10 (X) + 5 (V) + 1 (I) = 1666.

이렇게 MDCLXVI는 1666을 의미한다.

 

1. 여기서 알아낸 첫번째 규칙은 각각의 로마자에 대입되는 숫자들을 더하는데 기본 규칙이라는 것을 알 수 있다.

 

그러면 MCM는 어떻게 될까?

첫번째 M은 1000이다. 두번째 C는 100이다. 그리고 세번째 다시 M 즉 1000 이다.

단순히 이 세계를 더하는데 답일까? (1000 + 100 + 1000 = 2100 ???)

아니다. 여기서 한가지 더 알아야 한다.

900을 표시하기 위해서 C를 아홉 번 쓴다던가 D를 한번 쓰고 C를 4번 써서 900을 표시하지 않는다.

1000 쪽에 100을 쓰면 이건 빼라는 얘기다.

즉 CM 이렇게 쓰면 1000 (M) - 100 (C) = 900이 된다.

 

2. 여기서 두번째 규칙이 나온다. 현재 숫자보다 다음 숫자가 더 클 경우는 다음 숫자에서 현재 숫자를 뺀다이다.

 

MCMXCIV는 어떨까?

1000 + 900 (M-C) + 90 (C - X) + 4 (V-I) = 1994 가 정답이 된다.

 

이 두가지 규칙을 로직화 한게 아래 코드 이다.

 

class Solution { // 클래스 이름은 Solution 이다.

    

    static Map<String, Integer> values = new HashMap<>(); // 로마자와 아라비아 숫자를 키 밸류 쌍으로 다루기 위해 해쉬맵을 선언했다.

    

    static { // 로마숫자와 아라비아 숫자 쌍을 key - value 형식으로 HashMap에 put 한다.

        values.put("M", 1000);

        values.put("D", 500);

        values.put("C", 100);

        values.put("L", 50);

        values.put("X", 10);

        values.put("V", 5);

        values.put("I", 1);

    }

    

    public int romanToInt(String s) {

        int sum = 0; // return 할 int 변수를 선언 한다.

        int i = 0; // 루프에서 사용될 int 변수를 선언한다. 

        while(i<s.length()) { // 입력값의 글자 숫자 만큼 반복한다.

            String currentSymbol = s.substring(i, i + 1); // 입력값의 맨 i 번째 문자를 currentSymbol에 담는다.

            int currentValue = values.get(currentSymbol); // currentSymbol에 해당하는 아라비아 숫자를 currentValue에 담는다.

            int nextValue = 0; // 다름 숫자를 담을 int 변수를 선언한다. 

            if(i + 1 < s.length()) { // 입력값의 맨 마지막 글자까지 가지 않았다면 이 if 문을 실행한다.

                String nextSymbol = s.substring(i + 1, i+2); // currentSymbol 다음 글자를 nextSymbol에 담는다.

                nextValue = values.get(nextSymbol); // nextSymbol에 해당하는 아라비아 숫자를 nextValue에 담는다.

            }

            

            if(currentValue < nextValue) { // 현재 값이 다음 값보다 작을 경우 아래를 실행한다.

                sum += (nextValue - currentValue); // sum은 sum + (nextValue-currentValue) 가 된다.

                i += 2; // 입력값의 두 문자에 대해 실행 했기 때문에 두칸을 건너 뛰기 위해 i 에 2를 더한다.

            } else { // 현재 값이 다음 값보다 같거나 클 경우 아래를 실행한다.

                sum += currentValue; // 그냥 sum에다가 currentValue를 더한다.

                i +=1; // 한 글자에 대해서만 처리했으므로 i에 1을 더한다.

            }

        }

        return sum; // sum 값을 return 한다.

    }

}

 

이것과 같은 Python 스크립트는 아래와 같다.

 

values = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}

class Solution:
    def romanToInt(self, s: str) -> int:
        total = 0
        i = 0
        while i < len(s):
            # If this is the subtractive case.
            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                total += values[s[i + 1]] - values[s[i]]
                i += 2
            # Else this is NOT the subtractive case.
            else:
                total += values[s[i]]
                i += 1
        return total

 

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

 

아예 로마숫자와 아라비아 숫자 매칭을 아래와 같이 할 수 있다.

 

class Solution {
    
    static Map<String, Integer> values = new HashMap<>();

    static {
        values.put("I", 1);
        values.put("V", 5);
        values.put("X", 10);
        values.put("L", 50);
        values.put("C", 100);
        values.put("D", 500);
        values.put("M", 1000);
        values.put("IV", 4);
        values.put("IX", 9);
        values.put("XL", 40);
        values.put("XC", 90);
        values.put("CD", 400);
        values.put("CM", 900);
    }

 

이렇게 매칭을 만들면 로직은 아래와 같이 바꾸면 된다.


    public int romanToInt(String s) {
        
        int sum = 0;
        int i = 0;
        while (i < s.length()) {
            if (i < s.length() - 1) {
                String doubleSymbol = s.substring(i, i + 2); // 아예 처음부터 입력값의 글자 두 개를 불러 온다.
                // Check if this is the length-2 symbol case.
                if (values.containsKey(doubleSymbol)) { // 그 키 값이 위 매핑에 있다면 
                    sum += values.get(doubleSymbol); // 해당 값을 가져오고
                    i += 2; // 문자 두 개를 처리 했으니 i에 2를 더한다.
                    continue;
                }
            }
            // Otherwise, it must be the length-1 symbol case. 두 글자가 매핑에 없다면 
            String singleSymbol = s.substring(i, i + 1); // 한 글자만 불러와서 
            sum += values.get(singleSymbol); // sum 에 더해 준다.
            i += 1; // 한 글자만 처리했으니 i 에 1을 더해 준다.
        }
        return sum; // 결과 값을 리턴한다.
    }
}

 

여기에 해당하는 Python 코딩은 아래와 같다.

values = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
    "IV": 4,
    "IX": 9,
    "XL": 40, 
    "XC": 90,
    "CD": 400,
    "CM": 900
}

class Solution:
    def romanToInt(self, s: str) -> int:
        total = 0
        i = 0
        while i < len(s):
            # This is the subtractive case.
            if i < len(s) - 1 and s[i:i+2] in values:
                total += values[s[i:i+2]] 
                i += 2
            else:
                total += values[s[i]]
                i += 1
        return total

 

위 두 개는 입력값 을 왼쪽에서 오른쪽으로 보면서 계산한 것이다.

입력값을 오른쪽에서 부터 계산하는 방법도 생각해 볼 수 있다.

 

class Solution {
    
    static Map<String, Integer> values = new HashMap<>();
    
    static {
        values.put("M", 1000);
        values.put("D", 500);
        values.put("C", 100);
        values.put("L", 50);
        values.put("X", 10);
        values.put("V", 5);
        values.put("I", 1);
    }

    public int romanToInt(String s) {
        
        String lastSymbol = s.substring(s.length() - 1); // 맨 마지막 - 오른쪽 - 글자를 가져온다.
        int lastValue = values.get(lastSymbol); // 오른쪽 로마자에 해당하는 아라비아 숫자를 가져온다.
        int total = lastValue; // 리턴할  int 변수를 생성했다. 값은 lastValue를 넣었다.

        for (int i = s.length() - 2; i >= 0; i--) { // 입력값 -1 만큼 for 문을 돌린다. i 는 맨 마지막 글자 이전 부터 시작할 수 있도록 한다.
            String currentSymbol = s.substring(i, i + 1); // 현재값을 구한다. (첫번째 루프실행의 경우 맨 오른쪽에서 두번째 글자)
            int currentValue = values.get(currentSymbol); // 현재 값에 해당하는 아라비아 숫자를 구한다.
            if (currentValue < lastValue) { // 현재 값이 lastValue보다 작다면 
                total -= currentValue; // total = total - currentValue를 한다. 첫번쨰 루프에서 total은 lastValue가 된다.
            } else { // 현재 값이 lastValue보다 크거나 같다면
                total += currentValue; // total = total + currentValue를 한다. 
            }
            lastValue = currentValue; // lastValue에 currentValue를 입력한다.
        }
        return total; // for 문을 다 돌린 후 total 값을 리턴한다.
    }
}

 

여기에 해당하는 Python 스크립트는 아래와 같다.

 

values = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}

class Solution:
    def romanToInt(self, s: str) -> int:
        total = values.get(s[-1])
        for i in reversed(range(len(s) - 1)):
            if values[s[i]] < values[s[i + 1]]:
                total -= values[s[i]]
            else:
                total += values[s[i]]
        return total

 

 

반응형

Leetcode - 9. Palindrome Number - Easy

2022. 8. 6. 18:41 | Posted by 솔웅


반응형

오늘의 문제는 9. Palindrome Number 입니다.
앞으로 해도 뒤로 해도 똑같은 우병우 가 아니라
앞으로 해도 뒤로 해도 똑같은 숫자를 구별하라는 문제 입니다.


제가 만든 스크립트는 아래와 같습니다.

class Solution {
public boolean isPalindrome(int x) {
boolean returnValue = true; // 일단 리턴 값을 담을 변수를 만들고 초기값은 true로 설정한다.
String temp = Integer.toString(x); // 나중에 charAt을 사용할 예정이므로 int 입력값 을 스프링으로 변환한다.

int left = 0; // left는 0
int right = temp.length()-1; // right는 입력값 길이 -1

while(left < right) { // left 가 right 보다 작을 때까지 while 문 실행
if(temp.charAt(left++) != temp.charAt(right--)){ // 입력값의 왼쪽 값과 오른쪽 값이 다를 경우 if 문 실행
returnValue = false; // 다를 경우 리턴값은 false 가 된다.
}
}

return returnValue; // 리턴값을 리턴한다.
}
}

다른 사람이 만든 스크립트를 보자.

class Solution {
    public boolean isPalindrome(int x) {
        String s1 = Integer.toString(x);
        //passing x in the below statement won't work(idk why)
        StringBuilder s2 = new StringBuilder(s1).reverse();
        return s2.toString().equals(s1);
        //s2.toString() == s1 -> compares string references --> hence use .equals()
    }
}

내꺼 보다 훨씬 간단하다.
이 사람은 StringBuilder의 reverse 함수를 사용했다.
원래 입력값과 reverse한 값이 같으면 true 다르면 false를 리턴한다.

Python 으로는 아래와 같이 할 수 있다.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        return s == s[::-1]

마지막 줄이 좀 이해가 안기는데......

list[<start>:<stop>:<step>]
  • start (optional)- Starting index value where the slicing of the object starts. Default to 0 if not provided.
  • stop – Index value until which the slicing takes place.
  • step (optional) – Index value steps between each index for slicing. Defaults to 1 if not provided.

 

문법은 이렇다. 그리고 이렇게 작동한다.

 

>>> a = '1234'
>>> a[::-1]
'4321'

Step이 -1 이면 reverse를 하기된다.

 

a = '1234'
print a[::2]
13

스텝이 2 이면 한 개 건너 뛴 값이 선택 된다.

 

a = '1234'
print a[3:0:-1]
432

이렇게 되면 세번째 까지만 리버스 된다.

 

a = [1, 2, 3, 4, 5, 6, 7, 8] print(a[:5]) ==> output 1,2,3,4,5

 

 

a = [1, 2, 3, 4, 5, 6, 7, 8]
print(a[3:])

Output: [4, 5, 6, 7, 8]

 

a = [1, 2, 3, 4, 5, 6, 7, 8]
print(a[3:5])

Output: [4, 5]

 

a = [1, 2, 3, 4, 5, 6, 7, 8]
print(a[3:7:2])

Output: [4, 6]

 

a = [1, 2, 3, 4, 5, 6, 7, 8]
print(a[:5])    # prints [1, 2, 3, 4, 5]
print(a[2:])    # prints [3, 4, 5, 6, 7, 8]
print(a[2:5])    # prints [3, 4, 5]
print(a[2:7:2])    # prints [3, 5, 7]

You can index the last index of a sequence by using  -1 :

a = [1, 2, 3, 4, 5, 6]
print(a[-1])    # prints 6
print(a[2:-1])    # prints [3, 4, 5]

You can flip a sequence by using the  [::-1] slice notation:

a = [1, 2, 3, 4, 5, 6]
print(a[::-1])    # prints [6, 5, 4, 3, 2, 1]

 

 

 

반응형


반응형

지금 in between jobs 상태라서 취업 면접을 보고 있다.

어제 한 회사의 테크니컬 인터뷰를 봤다.

 

한 문제가 나왔는데 아래가 그 문제다.

 

 

String input을 reverse 하는데 letter 별로 하는게 아니라 단어별로 하라는 거다.

그래서 결과는 output과 같아야 한다는 것이다.

 

그 자리에서 나름대로 스크립팅를 해서 만들게 아래 코드다.

 

다행히도 원하는 결과물의 만들었다.

그래서 테크니컬 인터뷰는 통과 했다.

 

로직은 이전에 했던 String 의 letter들을 reverse 하는 것과 같다. 다면 단어를 reverse 해야 하는데 이건 letter 별이 아니라 단어별로 끊어서 배열에 넣으면 된다고 생각했다.

 

class HelloWorld { // 클래스 이름. 그냥 신경 안 쓰고 HelloWorld로 했다.
    public static void main(String[] args) { // 메인 함수
        String input = "Reverse words in a sentence."; // 입력값
        String output = "sentence. a in words Reverse"; // 원하는 출력 값
        
       System.out.println(reverseWords(input)); // reverseWords라는 메소드에 입력값을 보내고 그 결과를 프린트 한다.
    }
    
    public static String reverseWords(String input) { // reverseWords 메소드 입력값은 input 스트링 return은 스트링 타입이다.
        String returnValue; // return 할 스트링 변수를 만든다.
        
        String[] tempInput = input.split(" "); // input 을 단어별로 나눠서 스트링 배열에 담는다.
        int left = 0; 
        int right = tempInput.length -1;
        
        while(left < right) { // left가 right 보다 작을 때까지 while문을 돌린다.
            String temp = tempInput[left]; // 스프링에 배열 맨 왼쪽 값을 넣는다.
            tempInput[left++] = tempInput[right]; // 맨 왼쪽에 맨 오른쪽 단어를 넣는다.
            tempInput[right--] = temp; // 오른쪽에 맨 왼쪽 값을 넣는다.
        }
        
       returnValue = tempInput[0]; // returnValue에 배열의 맨 첫번째 값을 담는다.
        
        for(int i=1; i < tempInput.length; i++) { // 배열의 갯수보다 1 작은 만큼 for 문을 돌린다.
            returnValue = returnValue + " " + tempInput[i]; // 각 배열의 값들을 하나의 스트링 으로 만든다.
        }
        
        return returnValue; // 만든 스트링 을 리턴한다.
    }
}

 

결과 값은 오른쪽 Output 패널에 보이는 대로 원하는 값을 얻을 수 있었다.

다행히 문제를 제대로 풀 수 있어서 통과 했다.

반응형

Iterator basic

2022. 7. 31. 07:47 | Posted by 솔웅


반응형

Import java.until.*;

 

class IteratorBasic {

  Public static void main(String[] arts) {

    ArrayList list = new ArrayList();

    List.add("1");

    List.add("2");

 

    Iterator it = list.iterator();

 

   while(it.hasNext()) {

      Object obj = it.next();

      System.out.println(obj);

  } 

 

  for(int i=0; i<list.size(); i++) {

    Object obj = list.get(i); // HashSet에는 get() 메소드가 없다. 그래서 컬렉션을 사용할 때는 Iterator를 사용하면 좋다.

    System.out.println(obj);

  } 

  }

}

 

Map map = new HashMap();

...

Iterator it = map.entrySet().iterator();

 

 

반응형

Leetcode - 242. Valid Anagram : Easy

2022. 7. 31. 07:15 | Posted by 솔웅


반응형

오늘의 문제는 이것입니다.

2개의 Strings가 input이고 그 두개의 문자열이 같은 문자들을 포함하고 있으면 (순서는 바뀌어도 됨) true 이고 아니면 false 입니다.

먼저 Pattern을 찾아 보겠습니다.

 

1. 두개의 입력값의 문자 개수가 같아야 한다. (Length of input strings should be same)

2. 입력값 1에 입력값 2에 없는 문자가 있으면 안된다. 그 반대도 안된다. (If input 1 has different letter than input 2 then false. Vibe versa)

3. 2개의 input에 문자열이 중복된 문자가 있으면 그 개수가 같아야 한다. (If the inputs have a letter multiple times then the count of the letter should be same)

 

그럼 우선 pattern 1 을 만족하는 로직을 만들어 보았다.

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        boolean outPut = true;
        
        if(first.length != second.length) {
                outPut = false;
         }
        return outPut;
    }
}

 

이건 아주 간단한 로직이다.

두 input Strings를 charArray type으로 change 하고 그 배열의 개수를 비교해서 같으면 true이고 다르면 false 있다.

 

그럼 여기에 패턴 2를 만족 시키는 로직을 추가해 보았다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        boolean outPut = true;
        
        char charLetter;
        String strLetter;
        char charLetter2;
        String strLetter2;

        if(first.length != second.length) {
                outPut = false;
         } else {
            for(int i=0; first.length > i; i++) {
                charLetter = first[i];
                strLetter = String.valueOf(charLetter);
                charLetter2 = second[i];
                strLetter2 = String.valueOf(charLetter2);
            
                if (t.contains(strLetter) && s.contains(strLetter2)){
                } else {
                    outPut = false;
                    break;
                }
            }
        } 
        return outPut;
    }
}

 

내가 만든 로직은 배열에 있는 글자 하나 하나 씩 불어와서 String으로 만든 후 그 글자가 서로 상대 입력 값에 있는지 여부를 체크 하도록 했다. 만약에 없다면 false 가 return 된다.

 

여기까지 하면 웬만한 건 다 체크 할 수 있다. 

하지만 두 입력 값이 같은 문자 들만 가지고 있는데 그 중 어떤 문자의 중복된 개수가 다를 경우 조건을 만족하지 못하게 된다.

 

 

이런 경우까지 만족 하려면 아래 로직을 추가 해야 한다.

 

        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]) {
                outPut = false;
            }
        }

 

여기에서는 ASCHII 코드에 대해 알아야 한다.

 

sCounter[s.charAt(i) - 'a']++; 를 한번 살펴 보자.

 

여기서 s = 'cac; 라고 가정하자.

 

c 의 ascii 코드 값은 99 다. a 는 97. 그러니까 s.charAt(I) - 'a' 는 99 - 97 이니까 2가 된다.

그럼 sCounter[2] 는 ++ 되서 1이 된다.

두번째 a 는 97-97이니까 sCount[0] 은 1이된다.

세번째 c는 다시 sCounter[2] 가 ++ 되서 2가 된다.

 

즉 각 문자가 몇번 증가 됐는지 파악 할 수 있다.

 

처음에 배열 개수를 26개로 정의 한 이유도 알파벳 개수는 26개 이기 때문이다.

 

전체 코드는 아래와 같다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        boolean outPut = true;
        
        char charLetter;
        String strLetter;
        char charLetter2;
        String strLetter2;

        if(first.length != second.length) {
                outPut = false;
         } else {
            for(int i=0; first.length > i; i++) {
                charLetter = first[i];
                strLetter = String.valueOf(charLetter);
                charLetter2 = second[i];
                strLetter2 = String.valueOf(charLetter2);
            
                if (t.contains(strLetter) && s.contains(strLetter2)){
                } else {
                    outPut = false;
                    break;
                }
            }
        }
        
        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]) {
                outPut = false;
            }
        }
        
        return outPut;
    }
}

 

이렇게 만들고 보니까 맨 마지막 로직 으로  두번째 pattern 이 cover 되는 것 같다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        boolean outPut = true;      

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

           outPut = false;

           Return outPut;

       } 
        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]) {
                outPut = false;
            }
        }
        
        return outPut;
    }
}

 

과감하게 두번째 로직은 버리고 이렇게 하면 훨씬 짧은 코딩으로 결과를 만족 시킬 수 있다.

 

아래는 비슷한 접근 법인데 약간 다른 스크립트이다.

 

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        table[t.charAt(i) - 'a']--;
        if (table[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

 

일단 처리 속도를 생각해서 먼저 두 입력값 의 length를 비교해서 다르면 false를 return 해 버린다.

만약 같으면 그 아래를 실행 하게 되는데 ascii값을 이용해서 입력값 s의 문자들과 중복된 count를 table[]에 담는다.

 

그리고 for 문을 돌려 table에서 입력값 t에 있는 문자를 하나씩 가져와서 -1을 한다.

만약 그 값이 0보다 작으면 즉 마이너스가 되면 다른 문자이거나 같은 문자라도 그 숫자가 다르다는 것이기 때문에 false를 return 한다.

 

그리고 마지막으로 더 간단한 로직이 있다.

 

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

 

배열의 sort()메소드와 equals() 메소드를 사용하는 것이다.

요구조건을 잘 보면 두 입력값이 같은 문자들을 가지고 있는데 순서만 다르다는 거다.

즉 순서를 sorting 하면 두 입력 값은 정확히 일치하게 된다는 거다.

CharArray에는 equals()라는 메소드가 있으므로 이걸 사용해서 return 하면 깔끔하게 해결 된다.

 

따로 로직을 만들 필요 없이 배열의 sort() 와 equals()를 사용해서 해결 하면 된다.

 

또 한가지가 있다.

 

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] counter = new int[26];
    for (int i = 0; i < s.length(); i++) {
        counter[s.charAt(i) - 'a']++;
        counter[t.charAt(i) - 'a']--;
    }
    for (int count : counter) {
        if (count != 0) {
            return false;
        }
    }
    return true;
}

 

첫번째 for loop에서는 입력값 s에 있는 문자들을 체크해서 counter에 ++ 하고

두번째 에서는 t 에 있는 문자들을 체크해서 counter에 -- 한다.

 

그러면 둘이 똑 같으면 counter 내에 있는 모든 값이 0이 되어야 하고 다르면 0 이외의 값이 될 것이다.

 

 

반응형

Leetcode - 442. Find All Duplicates in an Array

2022. 7. 26. 08:41 | Posted by 솔웅


반응형


이번에는 배열 안에 중복된 숫자를 찾아 내는 로직입니다.
숫자는 중복 안된 숫자들과 한번만 중복된 숫자들이 있습니다. (두번 이상 중복된 숫자는 없습니다.)

총 4가지 방법이 있는데 그 중 첫번째는 아래 스크립트 입니다.

 

한 줄 한 줄 살펴보면 아래와 같습니다.

 

class Solution { // 클래스 이름은 Solution 입니다.

    public List<Integer> findDuplicates(int[] nums) { // 메소드 이름은 findDuplicates이고 입력값은 nums 라는 integer 배열이고 리턴값은 Integer 타입 리스트 입니다.

        List<Integer> ans = new ArrayList<>(); // 리턴 할 리스트를 ArrayList 로 선언합니다. 변수 이름은 ans 

        for(int i = 0; i < nums.length; i++) { //일단 입력된 배열 내의 값의 개수 만큼 for 문을 돌립니다.

            for(int j = i+1; j < nums.length; j++) { // 첫번째 값과 그 나머지 값을 비교해야 하니까 총 개수 - 1 만큼 for문을 다시 돌려 줍니다.

                if(nums[j] == nums[i]) { // 만약에 같은 숫자가 나오면서 이 if 문을 실행 합니다.

                    ans.add(nums[i]); // ans에 해당 숫자를 넣습니다.

                    break; // 나머지는 비교하지 않고 그냥 나가서 I++이 적용 되서 그 다음 숫자를 가지고 비교 합니다.

                }

            }

        } // 이렇게 되면 중복된 숫자들만 ans에 들어가게 됩니다.

        

        return ans; // 구해진 값을 리턴 합니다.

    }

}

 

이 예제는 아주 베이식한 방법인 것 같습니다.

다른 방법은 어떤 것이 있을 까요?

 

class Solution {

    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        

        Arrays.sort(nums); // 입력 값을 정렬 합니다. 

        

        for(int i = 1; i < nums.length; i++) {

            if(nums[i] == nums[i - 1]) { // 정렬이 돼 있고 중복이 안 됐거나 한번만 중복이 된 경우만 존재 하므로 바로 이전 숫자와 비교해서 같으면 이 if 문을 실행 합니다.

                ans.add(nums[i]);

                i++;

            }

        }

        return ans;

    }

}

 

이 코드는 이 배열의 값들이 중복이 안 됐거나 한번만 중복 된 값만 있는 정수 들이기 때문에 가능합니다.

순서대로 정렬해서 바로 이전 숫자와 비교만 하면 됩니다.

 

그 다음 방법으로는 

 

이것은 HashSet을 사용한 예제 입니다.

HashSet은 중복을 허용하지 않습니다. 

그래서 이 HashSet의 contains라는 메소드 를 사용해서 해당 값이 있으면 ans에 넣고 없으면 seen이라는 HashSet에 넣어서 나중에 ans만 리턴 하는 로직 입니다.

 

class Solution {

    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        Set <Integer> seen = new HashSet<>();

        

        for(int num : nums) {

            if(seen.contains(num)) { // HashSet 내에 이미 같은 숫자가 있으면 if 문을 실행합니다.

                ans.add(num);

            }else{ // HashSet내에 같은 숫자가 없으면 이 else 문을 실행합니다.

                seen.add(num);

            }

        }

        return ans;

    }

}

 

 

마지막 예제는 잘 이해가 안 되네요.  

나중에 시간 날 때 분석해 봐야 겠습니다.

 

class Solution {

    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        

        for(int num : nums) {

            nums[Math.abs(num) - 1] *= -1;

        }

        

        for(int num : nums) {

            if (nums[Math.abs(num) - 1] > 0) {

                ans.add(Math.abs(num));

                nums[Math.abs(num) - 1] *= -1;

            }

        }

        return ans;

    }

}

 

 

반응형