[algo] 같은 숫자는 싫어

유현영·2020년 2월 1일
0

algo

목록 보기
4/8

1. 풀이

배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있음
배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거해야함
[1,1,2,3,4,4,1,1] -> [1,2,3,4,1] 이 되어야함

import java.util.*;

public class Solution {
	public int[] solution(int []arr) {
        
		LinkedList answerList = new LinkedList();
		answerList.add(arr[0]);
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] != (int)answerList.getLast()) {
				answerList.add(arr[i]);
			}
		}
		int[] newArr = new int[answerList.size()];
		for (int i = 0; i < newArr.length; i++) {
			newArr[i] = (int) answerList.get(i);
		}
        return newArr;
	}
}

이렇게 풀었더니.. 효율성 테스트를 통과하지 못함 아마 ArrayList -> Array로 바꾸는 과정이 잘못 되었나 라는 생각.. 그래서 다시 품

public static int[] hateSameNUm(int []arr) {
        ArrayList<Integer> arrtemp = new ArrayList<Integer>();
        int temp = -1;
        for(int i : arr) {
            if (i != temp) {
                arrtemp.add(i);
                System.out.println(i);
                temp = i;
            }
        }
        int[] answer = new int[arrtemp.size()];
        int size=0;
        for(int t : arrtemp){
            answer[size++] = t;
        }
        return answer;
    }

2. 공부해볼것

🔍 Linkedlist 와 ArrayList차이

ArrayList
ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 아래와 같이 임시 배열을 생성해 데이터를 복사 하는 방법을 사용 하고 있음. 대량의 자료를 추가/삭제 하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있지만 반면 각 데이터는 인덱스를 가지고 있기 때문에 한번에 참조가 가능해 데이터의 검색에는 유리한 구현체

image.png

LinkedList
LinkedList는 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면되기에 추가 삭제가 ArrayList보다 빠르고 용이함. 삽입삭제가 빈번하게 발생되면 Linked List을 사용해 시스템 구현이 바람직함.
하지만 전체 검색시에 데이터와 포인터도 가지고 있어야 하기 때문에 메모리를 많이 잡음

🔍 ArrayList or List <-> 배열(Array)로 변환

  1. 배열(Array)
    배열의 크기는 한번 정하면, 크기를 변경을 할 수 없음
    배열 초기화시 메모리에 할당되어 ArrayList보다 속도가 빠름
  2. ArrayList
    ArrayList는 크기가 변할 수 있음
    저장하는 데이터 수에 따라서 크기가 변경됨
    데이터 추가는 add( ), 삭제는 remover( )를 사용
    데이터 추가 삭제시 메모리를 재할당하기 때문에 속도가 배열보다 느림

image.png

=> 가장 큰 차이는 초기 크기의 설정 여부와 추가 삭제 방식

3. 다른사람 풀이

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(arr[0]);

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

            if (arr[i] != arr[i - 1])
                list.add(arr[i]);
        }

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

        for (int i = 0; i < list.size(); i++)
            answer[i] = list.get(i);

        return answer;
    }
}

profile
오늘보다 더 나은 내일

0개의 댓글