문제 해석
•
처음 문제를 봤을때 핵심은 중복제거로 보였다.
◦
중복을 허용하지 않는 자료구조를 사용하면 쉽게 해결될 것 같았다.
◦
중복을 허용하지 않는 자료구조는 Set이 있으며 HashSet 또는 TreeSet으로 구현된다.
◦
하지만 모든 중복을 제거해버리는 문제가 발생했다.
public class Solution {
public int[] Solution(int[] arr){
HashSet<Integer> arrSet = new HashSet<>();
for(int i=0;i<arr.length;i++) {
arrSet.add(arr[i]);
}
return arrSet;
public static void main(String[] args){
Solution sol = new Solution();
int[] arr = {1,1,3,3,0,1,1};
System.out.println(Arrays.toString(sol.Solution(arr)));
}
}
Java
복사
•
하지만 HashSet은 모든 중복을 제거해버린다. 내가원하는 결과와 달랐다.
> Task :Solution.main()
[0, 1, 3]
Java
복사
•
문제의 의도에서는
◦
{1,1,3,3,0,1,1}에서 결과가 {1,3,0,1}이 유지되어야 한다.
◦
이는 곧 연속된 중복만 제거되어야 한다.
◦
•
따라서 해당 문제는 스택(Stack) 자료구조를 활용하고 조건문을 통해서 중복되는 것을 흘려 보낸다면 풀이가 될 것으로 판단되었다
문제 풀이
배열의 요소들을 스택 객체에 복사하는 시점에, 중복값이 있는 경우 continue를 통해 다음 요소로 넘어가도록 설정했다.
하지만 정답을 추출할때는 스택의 pop은 FILO인 것을 고려해야 한다. 역순으로 추출(pop)되기 때문에 그 역순을 다시 역순으로 바꿔서 추출하면 원하는 답을 얻을 수 있었다.
public class Solution {
public int[] Solution(int[] arr){
Stack<Integer> arrStack = new Stack<>();
for(int i=0;i<arr.length;i++){
//스택에 들어간 맨위 숫자가 중복된다면, 다음 반복문으로 진입(중복을 건너뜀)
if (!arrStack.isEmpty() && arrStack.peek() == arr[i]) {
continue;
}
arrStack.push(arr[i]);
}
int[] answer = new int[arrStack.size()];
for (int i= answer.length -1 ;i >=0;i--){
answer[i] = arrStack.pop();
}
return answer;
}
public static void main(String[] args){
Solution sol = new Solution();
int[] arr = {1,1,3,3,0,1,1};
System.out.println(Arrays.toString(sol.Solution(arr)));
}
}
Java
복사