리트코드 27.Remove Element JAVA

문제

문제 해석

간단하게 val 과 같은 Array의 인자를 제거하고 뒤로 배치시킨다.
이 후 length를 반환해주면 검증 단계에서 nums에 해당 length 만큼을 가져와서 맞는지 검증한다.
문제에서 힌트를 줬는데 in-place 즉 내부 정렬을 이용해서 풀어보라는 힌트를 줬었다.

문제 시행착오

1. 영어 문제 해석을 하기싫어서 반환형만 보고 Stream으로 Filter를 걸어서 length만 반환했더니 틀렸다고 나왔었다. 이후 문제를 조금 더 열심히 확인하고자 노력하는 중이다.
2. in-place로 문제를 해결할 때는 loop를 다 돌아야되는데 뭔가 시간을 더 줄일 수 있을 것이라고 판단했다. 그래서 내 나름 변수를 추가했다.

해답 1 같지 않다 활용

수도코드

    count 변수
    for int i = 0; i < num.length ; i++ 
        if(배열이 val과 같지 않다면)
            count 번지에 데이터를 넣고 count 증가 시켜라
    count를 반환해라

왜 같은 것을 찾지 않고 같지 않은 것을 찾았는가?

왜 같지 않다 사용했는가?

첫번째 예제 케이스 3,2,2,3 val = 3일 때 를 확인하면 쉽게 알 수 있다.

1번 루프
0번지가 3이다. -> 마지막 번지와 바꾸고 i를 증가 시킨다. -> i는 1이 되엇기 떄문에 다시 0번지를검사할 수 없다 하지만 0번지에는 마지막 번지에서 교환한 3이 남아 있다. -> 문제가 비효율적

마지막 번지를 가리키는 변수가 추가적으로 필요하다.

코드

        int count = 0;
        for(int i = 0 ;  i<nums.length; i++){
            if(nums[i] != val){
                nums[count++] = nums[i];
            }
        }
        return count;

코드로 보면 조금 더 심플하다.

이렇게 하면 모든 루프를 다 돌아야한다는 것이 고민이었다.
일단 해당 방식으로 문제를 풀면 O(n) 의 시간 복잡도를 가지게 된다.
뭔가 이것 저것 탈출 조건을 추가해서 시간 복잡도를 줄여보고자 다시 한번 코드를 변경했다.

해답 2. 같다 활용

수도코드

    int count = 0;
    int last = 마지막 값;
    for(int i = 0; i < nums.length ; i++){
        if(배열의 원소가 -1인지 검증)
        if val과 같은지 검증 진행
           같을 경우 자리 교환 로직 필요
           자리 교환 이후 삭제하는 로직이 필요한가? -> 문제의 조건을 충족 시키기 위해 -1을 삽입
           count 증가

    배열 길이 - count 반환

문제를 확인해 보면 인자로 가질 수 있는 값이 0부터다 그렇기 때문에 -1로 넣어준다면 나중에 배열의 원소가 -1일 경우에 바로 탈출 할 수 있을 것이라고 생각했다.

코드

         int count = 0;
        int last = nums.length - 1;
        for(int i = 0 ; i < nums.length;){
            if(nums[i] == -1)
                break;
            if (nums[i] == val) {
                nums[i] = nums[last];
                nums[last--] = -1;
                count++;
            } else {
                i++;
            }
        }
        return nums.length - count;

이 코드를 짜고 고민을 많이 했다.
모든 for문에서 최소 2번의 실행을 해야되고, if문에서도 추가적인 로직이 필요하다.
구현을 하고 보니 시간 복잡도에서의 개선은 없을 것이라고 판단되고, 공간복잡도는 last 변수를사용했기 때문에 증가하게 되었다.

비교

뭔가 하나의 문제를 풀 때 이렇게도 해보고 싶고 저렇게도 해보고 싶은 생각에 이것 저것 테스트를 많이 진행한다.
머리 속에서는 2번의 코드가 더 빠를 것이라 확신하고 문제를 풀었는데 그렇게 다이나믹하게 빨라지는 것 같지는 않은 느낌이다.

In -Place 알고리즘

내부 정렬 알고리즘이라고도 하며 간단하게 해당 Array만을 이용해서 정렬을 진행하는 알고리즘이다;.

컴퓨터 과학에서 제자리(in-place) 알고리즘은 자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘이다. 그러나 보통 추가적인 변수를 위해 약간의 추가 저장 공간은 허용된다. 일반적으로 알고리즘이 실행되면서 입력 값이 출력 값으로 덮어써지는데 입력 요소를 출력 요소로 교체하거나 요소의 위치를 바꾸는 방식으로 업데이트한다.

제자리라는 말은 조금씩 다른 의미를 가질 수 있는데, 가장 엄격하게는 함수 호출 및 포인터까지 포함하여 고정된 양의 추가 공간만 가지는 것을 의미한다. 그러나 단순히 길이 n 인 배열에 대한 인덱스를 갖는 데만도 O(log n) 비트가 필요하기 때문에 이 의미는 매우 제한적으로 사용된다. 좀 더 넓은 의미로는, 입력을 조작하기 위한 추가 공간을 사용하지 않지만 일부 계산을 위해 고정되지 않은 작은 추가 공간이 필요할 수 있음을 의미한다. 일반적으로 이 공간은 O(log n)이지만 때로는 O(n)까지도 허용된다.

-위키피디아-

https://ko.wikipedia.org/wiki/%EC%A0%9C%EC%9E%90%EB%A6%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[제자리 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 제자리(in-place) 알고리즘은 자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘이다. 그러나 보통 추가적인 변수를 위해 약간의 추

ko.wikipedia.org](https://ko.wikipedia.org/wiki/%EC%A0%9C%EC%9E%90%EB%A6%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

다른 답과 비교하기

CASE ONE

class Solution {
    public int removeElement(int[] nums, int val) {
   int flag = 0;
        for (int num : nums) {
            if (num != val) {
                nums[flag] = num;
                flag = flag + 1;
            }
        }
        return flag;
    }
}

향상된 For문을 사용했다.
이를 통해 변수 i를 따로 선언하지 않았는데 향상된 for문의 내부 로직을 이해하면 시간복잡도의 차이를 서로 비교할 수 있을 것 같다.

좋은 링크가 하나 있어 공유하고자한다.

https://sorjfkrh5078.tistory.com/98

[[Java] 향상된 for 문 : for-each

Java5에서부터 향상된 for문이라고 부르는 for-each문이 도입되었다. 일반적인 for문과 거의 비슷하지만 내부적으로 조금 다르게 순회하는 방법이다. ​for-each문의 형태는 다음과 같다. for (type var: ite

sorjfkrh5078.tistory.com](https://sorjfkrh5078.tistory.com/98)

자료구조에 따라 시간 복잡도가 차이가 나게 되는데 배열에서는 향상된 for문보다 그냥 for문이 조금 더 빠른 것을 확인할수 있다.

이것은 인덱싱을 하는 것보다 객체를 만드는 것에 대한 시간의 차이가 발생하기 때문인데 이것은 배제할 수 있을 정도의 미비한 차이라고한다.

그렇다면 공간 복잡도는?

큰 차이가 없다.

성능 차이가 거의 미비하다면 for문 대신 향상된 for문을 사용하는 것도 좋아보인다.

CASE TWO

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

이 코드는 temp를 따로 선언해줘서 만들고 지워지고 만들고 지워지고를 하는 코드인 것 같다.

회고

찾아본 코드들이 대부분 같다를 중심으로 보는 것이 아닌 같지 않다를 중심으로 체크하는 것 같다.
같다를 이용할 경우 내 2번과 같이 코드가 지저분해지는 것을 알 수 있다. 불필요한 변수도 생성해야되고, 코드에도 if문이 늘어난다.
개인적으로 코드에 if문을 계속 쓰는 것을 선호하지 않는다. 과거 if에 if에 if에 if를 쓴 코드를 내가 구현하고 다시 확인했을 때 정말 지옥을 경험해서 그런가 가급적이면 if문을 최소화 시키고 싶다.