Today I Learned

오늘할일
1. LeetCode

오늘한일
1. LeetCode

• 443. String Compression은 char[]배열을 압축하는 문제이다. 제약조건으로 별도의 배열을 리턴하는 것이 아닌, 매개변수로 입력된 char[] 변수에 결과를 저장해야했다.

문제를 간소화하기 위해 새로운 문자가 존재하는(문자 연속이 끊기는) 인덱스를 리스트로 반환하는 indexes_per_char함수와 1자리수 이상의 숫자를 문자로 변환하는 number_to_char_array함수를 사용했다.

class Solution {
    public int compress(char[] chars) {
        List<Integer> index_for_split=indexes_per_char(chars);
        int prev_index=0, index_saved=0;
        for(int index_change : index_for_split){
            chars[index_saved++]=chars[prev_index];
            if(prev_index+1!=index_change){
                int count=index_change-prev_index;
                for(char ch: number_to_char_array(count))
                    chars[index_saved++]=ch;
            }
            prev_index=index_change;
        }
        return index_saved;
    }

    private char[] number_to_char_array(int number){
        return Integer.toString(number).toCharArray();
    }

    private List<Integer> indexes_per_char(char[] chars){
        List<Integer> indexes=new ArrayList<>();
        for(int i=0; i< chars.length-1; i++){
            if(chars[i]!=chars[i+1])
                indexes.add(i+1);
        }
        indexes.add(chars.length);
        return indexes;
    }
}

바로 통과할 수 있었다. 이 문제를 쉽게 풀 수 있었던 이유는 자바의 여러 api를 잘 활용했기 때문으로 본다. 숫자를 문자배열로 변환할 때, 문제의 조건으로 배열의 길이가 최대 2000이라는 점을 이용해서 for문을 돌려야할지, 재귀를 사용해야할지 고민을 했었다. 이때 자바에서 숫자를 문자배열로 반환하는 것은 생각나지 않았지만 숫자를 문자로 바꾸는 String.valueOf()같은 함수가 생각났고, String타입에서 toCharArray()함수를 지원해준다는 점을 생각해냈다.

• 283. Move Zeros는 int배열에서 0을 뒤로 옮기고 앞은 일반숫자만 모아놓으며, 정렬을 유지해야하는 문제이다. 다음은 초기 코드이다.

public void moveZeros(int[] nums) {
        int tail=nums.length-1;
        for(int head=0; head<nums.length && head<tail; head++){
            if(nums[head]==0){//0발견
                for(; nums[tail]==0 && tail>0; tail--);//tail이 이미 0이라면 이동
                swap(nums,head,tail);
                tail--;
            }
        }
        return;
    }

    private void swap(int[] nums, int index1, int index2){
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }

하지만 test코드에서 fail이 떠서 테스트 케이스를 확인해보니 일반 숫자가 정렬되어있는 것을 확인할 수 있었다. 문제에서는 다음과 같이 maintaining the relative order of the non-zero elements. 상대적인 위치를 유지한다고 명시되어있는데.. 자세히 보니 내 코드의 결과가 상대적인 위치를 유지하지 않고 있었다. 0과 끝을 swap시키기에 그 사이의 순서가 얶힌 것이다.

고로 새로운 알고리즘을 생각해보기로 했다.
1. 숫자를 발견하면 two pointer로 앞에서부터 저장
2. 순회가 끝나면 two pointer의 위치로 몇개의 0이 발견되었는지를 계산
3. 0이 발견된 크기만큼 오른쪽부터 0채워넣기

	public void moveZeros(int[] nums) {
        int head=0;
        for(int index=0; index<nums.length; index++){
            if(nums[index]!=0){//0이 아닌 수의 경우 저장
                nums[head++]=nums[index];
            }
        }
        for(int index=nums.length-1; index>=head; index--)
            nums[index]=0;
    }

덮어쓰기를 이용하면 보다 효율적으로 코딩이 가능한 것 같다. 기존의 swap방식은 사라지는 값 없이 작업을 처리하는데, 그 과정에서 temp변수가 필요하여 불필요한 메모리를 사용하게 된다. 다만 새로 작성한 코드는 two pointer를 사용하여 불필요한 메모리 사용 없이, 필요없은 index에 덮어쓰기를 수행하여 보다 효율적이다.