remove-element

gistfile1.txt

https://oj.leetcode.com/problems/remove-element/

/*
이런 단순한 문제 일수록 문제의 의도를 정확하게 파악하기 위해 인터뷰어와 코딩 전 충분한 사전 토의가 필요.
단순히 주어진 element를 모두 지우고 새로운 length를 리턴하라는 것인지, remove후 정렬절차가 어떻게 될것인지 질문하기.
"The order of elements can be changed. It doesn't matter what you leave beyond the new length" -> element를 remove하고 left shift 해야함을 암시.

조심할 점: 주어진 n으로 보통 for i=[0,n) loop를 돌릴텐데, elem를 remove 할때마다 n이 점점 짧아지므로 loop가 자칫 의도대로 동작하지 않을 수 있음.

test case:
[1,2,3], 1
[1,2,2,2,3] 2
[1,1,1,1,1] , 1
[1,1,1,1,2] , 1

suedo-code:
jumpCnt = 0
for i=[0,n)
    jumpCnt = 0;
    while(i+jumpCnt < n && A[i+jumpCnt] == ele) jumpCnt++;
    if(jumpCnt >= n) break;
    A[i] = A[i+jumpCnt];
    n-= jumpCnt;
    
    return n;
*/

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        if(n <= 0) {
            return n;
        }
        
        int jumpCnt = 0;
        
        for(int i=0; i<n ; ++i) {
            while(i+jumpCnt < n && A[i+jumpCnt] == elem) {
                ++jumpCnt;
            }
            
            A[i] = A[i+jumpCnt];
        }
        
        return n-jumpCnt;
    }
};