배열 중복제거 알고리즘 - baeyeol jungbogjegeo algolijeum

Question

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다.
이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다.
단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.
ex)
목차 Show

접근 포인트
풀이 과정 정리
최종 코드

arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        int[] answer = {};

        return answer;
    }
}

처음에 문제 이해를 잘못 해서

배열 전체의 중복을 없애라는 줄 알았는데 그게 아니었다!

연속해서 같은 수가 나올 때만 없애라는 거였고,

반환할 배열 전체적으로 봤을 땐 중복이 존재 가능하다. (첫번째 예시 참고)

접근 포인트

1. 용량 제한 없이 자유롭게 넣었다 뺄 수 있는 ArrayList를 활용하자!

자바의 배열(Array)과 ArrayList

- 공통점

여러 데이터를 그룹으로 관리한다
인덱스로 식별한다

- 차이점

배열은 크기가 고정되어 있고, ArrayList는 크기가 가변적이다
배열은 제네릭을 사용할 수 없고, ArrayList는 제네릭을 사용할 수 있다
배열은 length 변수로 크기를 알아내고, ArrayList는 size() 메소드로 크기를 알아낸다

2. 인덱스 0의 값은 중복 제거 대상이 아님을 잊지 말자!

(첫 값은 비교 대상이 없다. 두 번째 값부터 비교 들어가야 함)

풀이 과정 정리

배열은 총 세 개가 등장할 예정이다.

1) int [] arr : 파라미터로 받음

2) ArrayList<Integer> temp_arr : 위 1)의 arr에서 연속된 숫자를 제거해서 넣음

3) int [] answer : 위 2)의 temp_arr에 있는 값을 담아서 리턴

ArrayList<Integer> temp_arr = new ArrayList<Integer>();


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

    if (i == 0) {
        temp_arr.add(arr[i]);
        
    } else {
        if (바로 앞의 값과 중복이 아닐 때) {
            temp_arr.add(arr[i]);
        }
    }
    

}

ArrayList 자료구조는 배열과 달리 길이가 가변적이기 때문에,

길이를 몰라도 선언할 수 있다!

temp_arr 라는 이름으로 선언해 놓는다.

(int만 담을 거니까 제네릭도 써 주기)

어차피 배열 arr의 첫 값은 비교 대상이 없으므로

if else 문을 활용해서

index가 0일 때는 배열 arr의 인덱스가 i인 값을 그냥 넣고,

그렇지 않을 때(else)는 바로 앞 값과 중복을 체크한 후 넣기로 했다.

바로 앞 값이랑만 겹치지 않으면 담아주면 된다.

중복 체크는 어떻게 할까?

주어진 배열 arr에는 중복이 있을 수 있고,

중복을 없애야 하는 것은 ArrayList temp_arr 이기 때문에

temp_arr 기준으로 로직을 짠다.

위 그림에서 arr의 2번째 값부터, 즉 for문의 i = 1일 때부터 생각해 보자.

(arr의 1번째 값, 즉 for문의 i = 0 일 때는 위 if문에 따라

ArrayList temp_arr에 이미 값이 들어가 있는 상태이다!)

이 상태에서, ArrayList temp_arr의 길이는 1이다.

숫자가 하나하나 들어갈 때마다 값은 가변적으로 변하겠지.

길이가 1일 때는 ArrayList에 값이 1개 있으니까

>> temp_arr의 0번 인덱스 값(위 그림에선 =1)과 arr[i](위 그림에선 =1)의 중복을 비교해주면 된다.

>> 중복이다.

길이가 2일 때는 아마 i=2에서 arr[2](위 그림에선 =3)이

temp_arr의 1번 인덱스에 추가된 후이니까, i=3인 시점일 거고

ArrayList에 값이 이미 2개 있으니까

>> temp_arr의 1번 인덱스 값(위 그림에선 =3)과 arr[i](위 그림에선 =3)의 중복을 비교해주면 된다.

>> 중복이다.

ArrayList의 가장 마지막 값을 가져오기 위해서

temp_arr.get(temp_arr.size() - 1))

이런 코드를 짰다.

* 나중에 다른 사람의 풀이를 보다 보니, ArrayList가 아닌

LinkedList를 사용했다면 getLast() 메소드로

더 쉽게 가져올 수 있더라.

정리하면, 이런 코드가 된다.

ArrayList<Integer> temp_arr = new ArrayList<Integer>();

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

    if (i == 0) {
        temp_arr.add(arr[i]);
        
    } else {
        if (arr[i] != temp_arr.get(temp_arr.size() - 1)) {
            temp_arr.add(arr[i]);
        }
        
    }

}

이로서 temp_arr라는 ArrayList에 모든 원하는 값이 순서대로 담겼다.

문제에서는 int [] 타입의 배열에 넣어 리턴하길 원했으니

temp_arr의 값을 꺼내서 answer에 그대로 담아주자.

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

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

배열은 ArrayList와 달리 크기가 고정되어 있으므로

처음부터 temp_arr의 크기와 맞추어 answer 배열 선언을 한다.

get메소드를 써서, 순서에 맞게 인덱스 값을 맞추어

answer 배열에 담는다.

그리고 리턴해주면 끝!

최종 코드

import java.util.*;

public class Solution {
	public int[] solution(int[] arr) {

		ArrayList<Integer> temp_arr = new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			if (i == 0) {
				temp_arr.add(arr[i]);
			} else {
				if (arr[i] != temp_arr.get(temp_arr.size() - 1)) {
					temp_arr.add(arr[i]);
				}
			}

		}

		int[] answer = new int[temp_arr.size()];
		for (int i = 0; i < temp_arr.size(); i++) {
			answer[i] = temp_arr.get(i);
		}

		return answer;
	}

}

자바 중복제거 알고리즘 중복 확인 알고리즘