Easy 문제 풀기 Day1(79/610)

27. Remove Element

주어진 배열 과 값이 나오고 배열 내에서 해당 값을 지워서 리턴해주면 되는 간단한 문제이다. 

다만 문제의 조건상 에 추가적인 메모리 가 없기 떄문에 배열 자체를 수정해서 리턴 해야한다. 

class Solution {
    public int removeElement(int[] nums, int val) {
        int left =0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] != val){
                int tmp = nums[left];
                nums[left++] = nums[i];
                nums[i] = tmp;
            }
        }
        return left;
    }
}

left 값 하나 를 선정해서 투포인터 느낌으로 스왑 해가면서 풀었다.  for loop 자동으로 증가하는 값을 right 로 생각하면 보다 쉽게 풀듯하다.

leetcode post 

 

58. Length of Last Word

문자 가 주어지면 그 스트링 내에서 가장 마지막에 있는 문자 의 개수를 반환하는 문제이다.

class Solution {
    public int lengthOfLastWord(String s) {
        int len = s.length()-1;
        int cnt =0;
        for(int i =len;i>=0;i--){
            if(!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' '){
                cnt++;
            }
            if(cnt != 0 && s.charAt(i) == ' '){
                return cnt;
            }
        }
        return cnt;
    }
}

 

 

뒷방향 부터 탐색해 나가면서 카운트 가 시작되어있는 상태에서 공백을 만나면 반환을 하는 함수를 작성했다. 

사실 트림을 이용해서 하면 아래 추가적인 if 문 없이 작성할수 있으나 trim 내부적으로 ' ' 이걸 만나지 않을때 까지 와일 문을 앞뒤로 돌린다. 그게 싫어서 저렇게 작성했다.

leetcode post

66. Plus One

나름 난감했던 문제 였다. Stack 을 이용하지 않고 구현을 해보려고 노력하다 보니 그런거 같다.

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length-1;
        StringBuilder answer = new StringBuilder();
        int willAdd = 1;

        for (int i = len; i >=0 ; i--) {
          int next = digits[i] + willAdd;
          answer.append(next%10);
          if(next > 9) willAdd = 1;
          else willAdd = 0;
        }
        if(willAdd == 1) answer.append(1);

        int[] ans = new int[answer.length()];
        for (int i = 0; i < ans.length; i++) {
          ans[i] = answer.charAt(ans.length-1-i)-'0';
        }

        return ans;
    }
}

1ms 가 나왔다 스택을 이용해서 속도적인 차이가 궁금해서 바로 구현해 봤다.

class Solution {
    public int[] plusOne(int[] digits) {
        Stack<Integer> stack = new Stack<>();
        int len = digits.length-1;
        int willAdd = 1;

        for (int i = len; i >= 0; i--) {
            int val = digits[i]+willAdd;
            stack.push(val%10);

            if(val > 9) willAdd = 1;
            else willAdd = 0;
        }

        if(willAdd == 1) stack.push(1);

        int[] answer = new int[stack.size()];

        for (int i = 0; i < answer.length; i++) {
            answer[i] = stack.pop();
        }
        
        return answer;
    }
}

2ms 가 나온다 더 느리다 .
스택은 백터 를 상속받아서 구현 된 클래스다. 따라서 스레드 세이프 하다는 의미이다. 대부분의 함수에 syncronize 가 걸려있다.

동기화가 제거된 버전인 Deque 를 사용해보자 보통 queue , stack 에서 deque 를 사용하면 성능적인 측면에서 좋은 효과가 있다 왜 ?

스레드 세이프 하지 않으니깐. 1ms 가 나온다. 

 

다른 사람의 풀이를 한번 확인해보자.

class Solution {
    public int[] plusOne(int[] digits) {
        
    int n = digits.length;
    for(int i=n-1; i>=0; i--) {
        if(digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        
        digits[i] = 0;
    }
    
    int[] newNumber = new int [n+1];
    newNumber[0] = 1;
    
    return newNumber;
}
}

와.... 생각지도 못했던 부분이다. 물론 9 이하인경우 +1 해서 리턴 생각을 했지만 구현의 구체적인 방향성이 떠오르지 않아 위와같이 작성했는데.... 0ms 나온다. 저 9이하 리턴 부분이 최적화 가 완성된 부분이기떄문에 2배이상 빠른것 같다.

leetcode post

 

갑자기 내 첫번쨰 로직에 포함된 StringBuilder 와 StringBuffer 의 차이가 궁금해졌다.

라이브 코딩을 하게 되면 인터뷰어를 설득해야한다.

저런 클래스에 사용에 있어 명확한 이유가 있어야 한다. 이번기회 에 한번 찾아보고자 한다.

 

기본적으로 String 은 불변객체이다.

스트링은 + 연산자가 되던데 ?  라고 생각하면 착각이다. 새로운 메모리가 할당되어 포인팅 된다.

즉 기존에 가지고 있던 포인터 부분은 가비지컬렉터 제거 대상이 되어진다. 이렇게 되면 메모리 어뷰징이 발생되고 빈번한 문자 변경에 성능상 이슈가 야기될수 있기 때문에

자바에서 StringBuffer 를 처음 만들게 된다.(Java 1.0 에서 등장한다.)

최초 만들때 즉 가변성 있는 객체를 만들고자 buffer 를 만들고 쓰레드 세이프 한 방식으로 구현되어진다.

(실제 클래스 내부에 들어가보면 대부분의 함수들이 syncronize 가 달려있다)

스택 과 동일하게 동기화 함수가 걸려있다면 성능적으로 느려진다.

대부분의 스트링을 이용한 케이스를 고려해본다면 멀티쓰레드 환경에서 사용되어 지지 않는다. 이부분을 고려해 java 1.5 에서 StringBuilder 가 등장하게 된다. 당연히 동기화 함수 는 제거된 상태로 구현되어 있다. 

 

StringBuffer,Builder 두종류 모두 comparable 을 구현한다. 따라서 priorityQueue 에 넣어서 사용할수 있는데 String 의 정렬과 동일한 방식으로 된다. 즉 사전시으로 정렬된다.

  public static void main(String[] args) {
    PriorityQueue<StringBuilder> a = new PriorityQueue<>();
    a.add(new StringBuilder("c"));
    a.add(new StringBuilder("a"));
    a.add(new StringBuilder("b"));
    a.add(new StringBuilder("132"));
  }

이렇게 넣게되면 ? [132, a, b, c] 이런식의 정렬된 값이 들어가게 된다.

 

이지 문제였지만 나름 혼자 이것저것 고민해보면서 재밌는 시간을 보낸거 같다.