[Java] 같은 숫자는 싫어 (programmers)

0120

---

문제 설명

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

arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr	answer
[1,1,3,3,0,1,1]	[1,3,0,1]
[4,4,4,3,3]	[4,3]

입출력 예 설명

입출력 예 #1,2
문제의 예시와 같습니다.

소스코드

Stack 자료구조를 사용하지 않고 푼 소스코드

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        
        // 중복 개수 확인
        int cnt = 0;
        for (int i = 1; i < arr.length; i++) {
            if ( arr[i-1] == arr[i]) cnt++;
        }
        
        int[] answer = new int[arr.length-cnt];// 중복된 개수만큼 arr.length에서 뺀 길이의 answer 생성
        int aIdx = 0;// answer 인덱스값
        answer[0] = arr[0];// 비교값
        for (int i = 1; i < arr.length; i++) {
            if ( answer[aIdx] == arr[i]) continue;// 같다면 
            answer[++aIdx] = arr[i];
        }

        return answer;
    }
}

Stack 자료구조를 사용하고 푼 소스코드

import java.util.*;// import java.util.Stack;

public class Solution {
    public int[] solution(int []arr) {
        
        Stack<Integer> stack = new Stack<>();// int형 스택 선언
        stack.add(arr[0]);
        for (int i = 1; i < arr.length; i++) {            
            if (stack.peek() != arr[i]) {// stack 최상단에 있는 값이 arr[i]가 아니면
                stack.push(arr[i]);
            }
        }

        int[] answer = new int[stack.size()];// stack의 크기만큼 answer 크기 세팅
        for (int i = answer.length-1; i >= 0; i--) {
            answer[i] = stack.pop();
        }
        
        return answer;
    }
}

소스 풀이

Stack 자료구조를 사용하지 않고 푼 소스코드 풀이

    public int[] solution(int []arr) {
        
        // 중복 개수 확인
        int cnt = 0;
        for (int i = 1; i < arr.length; i++) {
            if ( arr[i-1] == arr[i]) cnt++;
        }
        
        int[] answer = new int[arr.length-cnt];// 중복된 개수만큼 arr.length에서 뺀 길이의 answer 생성

arr안의 중복된 값이 연속으로 있는 수를 세어 cnt를 증가시킨다.
단순 중복된 값이 아닌 연속되어 있어야 하기 때문에 arr[i-1]와 arr[i]를 비교하여 같다면 cnt를 증가시킨다.

중복된 값의 개수만큼 arr의 길이에서 뺀만큼의 길이를 가진 answer배열을 생성한다.
null값이 들어가거나 overflow에러가 발생하지 않도록 하기 위함이다.

        int aIdx = 0;// answer 인덱스값
        answer[0] = arr[0];// 비교값
        for (int i = 1; i < arr.length; i++) {
            if ( answer[aIdx] == arr[i]) continue;// 같다면 
            answer[++aIdx] = arr[i];
        }
        
        return answer;

answer의 인덱스를 나타내는 aIdx를 0으로 초기화시킨다. 개별적으로 둠으로써 arr의 중복값을 제거한 arr의 값들을 answer에 완전히 넣을 수 있도록 한다.

answer의 [0]번째 방에 arr의 [0]번째 방의 값을 저장한다. 미리 비교할 값을 저장하는 것이다.

이미 answer의 [0]째 방에는 값이 있으므로 i는 1부터 시작한다.
만약 answer에 들어있는 값이 arr에 들어있는 값과 같다면 continue를 이용해 answer에 중복값이 저장되는 것을 막는다.

이렇게 중복값이 제거된 answer을 return시킨다.

Stack 자료구조를 사용해서 푼 소스코드 풀이

import java.util.*;// import java.util.Stack;

util클래스의 모든 것(*)을 import한다. 그 중에는 Stack도 포함된다.

        Stack<Integer> stack = new Stack<>();// int형 스택 선언
        stack.add(arr[0]);

Stack 자료구조를 선언한 뒤 stack에 arr의 첫 번째 값을 add하여 초기값을 만든다.

        for (int i = 1; i < arr.length; i++) {            
            if (stack.peek() != arr[i]) {// stack 최상단에 있는 값이 arr[i]가 아니면
                stack.push(arr[i]);
            }
        }

peek()는 최상단, 즉 맨 나중에 저장된 값을 보여준다. stack.peek()가 arr의 값과 다르다면 push()를 이용해 stack에 arr[i]를 넣는다. 그럼 다시 stack.peek()가 arr[i]가 된다.
이렇게 중복된 값은 넣지 않고 중복되지 않은 값만 stack에 저장하게 된다.

        int[] answer = new int[stack.size()];// stack의 크기만큼 answer 크기 세팅
        for (int i = answer.length-1; i >= 0; i--) {
            answer[i] = stack.pop();
        }
        
        return answer;

연속되며 중복되지 않은 값만을 저장할 answer 배열을 stack의 크기만큼 생성한다.
맨 마지막에 저장한 값이 맨 위에 있는 stack 자료구조의 특징을 살려 for문의 i는 answer인덱스의 맨 마지막에서 0까지 감소하도록 한다.

answer의 맨 마지막 방부터 stack.pop()을 이용해 stack의 맨 위의 값을 꺼내 answer에 저장한다.

저장된 answer 값을 return한다.

실행 결과

---