같은 숫자는 싫어 - Java [코딩테스트 연습]

 

❤️ Problem

• 문제
  배열 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 함수를 완성해 주세요.

 

• 제한 사항
  • return 값은 이진수를 의미하는 문자열입니다.
  • 1 ≤ bin1, bin2의 길이 ≤ 10
  • bin1과 bin2는 0과 1로만 이루어져 있습니다.
  • bin1과 bin2는 "0"을 제외하고 0으로 시작하지 않습니다.

 

• 입출력 예 & 설명

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

1. 문제의 예시와 같습니다.
2. 문제의 예시와 같습니다.

 

---

 

💛 Solution

풀이 1

import java.util.*;

public class Solution {
    public int[] solution(int[] arr) {
        Stack<Integer> trans = new Stack<>();
        trans.push(arr[0]);
        for(int i=1; i<arr.length; i++) {
            Integer tmp = arr[i];
            Integer compare = trans.peek();
            if(compare == tmp) {
                continue;
            } else {
                trans.push(tmp);
            }
        }

        int[] answer = new int[trans.size()];
        int index = answer.length-1;
        while (!trans.isEmpty()) {
            answer[index] = trans.pop();
            index--;
        }
        return answer;
    }
}

 

더 빠르게 처리할 수 없을까?

---

 

풀이2

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        tmp.add(arr[0]);
        for(int i=1; i<arr.length; i++) {
            if(arr[i-1] != arr[i]){
                tmp.add(arr[i]);                
            }
        }       
        int[] answer = new int[tmp.size()];
        for(int i=0; i<answer.length; i++) {
            answer[i] = tmp.get(i).intValue();
        }
        return answer;
    }
}

 

효율성 2배 증가!

 

---

 

💜 Comment

연속적으로 나타나는 숫자를 비교하기위해서 먼저 풀이 1처럼 Stack을 사용해서 코드를 작성했다. 그 이유는 Stack이 후입선출(Last In First Out)이 가능하기 때문이다.

Stack에 먼저 arr[0]의 값을 넣은 뒤 반복문을 1부터 시작하여 arr[i]의 값이 Stack.peek()의 값과 일치하는 경우에는 push() 없이 넘어가도록 구현하여 중복되는 숫자를 넣지 않았다. 그런 뒤 Stack에 들어있는 값을 배열에 담아 반환하였다.

문제를 다 풀고 나니 Stack 없이도 충분히 구현할 수 있다는 생각이 들어서 ArrayList를 사용하여 동일한 방식으로 구현했다. 그 결과 효율성이 2배 증가했다.

알고 있는 지식을 활용하는 것도 좋지만 반드시 꼭 필요한 자료구조인지를 먼저 고려해야겠다.

 

 

10149위다