같은 숫자는 싫어

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

 

자... 이런 문제를 봤는데 말입니다.

문제를 읽고는 스택으로 풀어야 한다고 생각을 했고,

그렇게 풀었는데...

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        if (arr.length == 0) return new int[0];  

        Stack<Integer> stk = new Stack<>();
        stk.push(arr[0]); 

        for (int i = 1; i < arr.length; i++) {  
            if (stk.peek() != arr[i]) {  
                stk.push(arr[i]);
            }
        }

        int[] answer = new int[stk.size()];
        for (int i = answer.length - 1; i >= 0; i--) {
            answer[i] = stk.pop();  
        }
        return answer;
    }
}

 

나의 이런 접근 방식이 맞는지 궁금하더라고.

 

1. GPT야, 이런 문제를 스택으로 푸는 게 맞니? 큐로 푸는 건 좀 아닌 것 같았어. 넌 어떻게 생각해?

 

이 문제는 스택을 사용해서 풀 수도 있지만, 실제로는 더 간단하고 직관적인 방법으로 풀 수 있습니다. 문제는 연속적으로 나타나는 숫자를 제거하고 남은 수들을 배열로 반환하는 것인데, 이를 위해 단순히 이전 값과 현재 값을 비교하는 방식을 사용할 수 있습니다. 이러한 접근 방식은 스택이나 큐를 사용할 필요가 없이, 단순 배열 또는 리스트를 이용해 해결할 수 있으며, 공간적 효율성과 성능 모두에서 이점을 가집니다.

 

하아.. 역시 G옹은 보법부터 다르군요... 그래... 코드를 좀 봅세다.

해결 방법

1. 리스트 사용: 연속된 값들을 제거하고 남은 값을 저장하기 위해 리스트를 사용할 수 있습니다. 리스트의 마지막 요소와 현재 순회 중인 요소를 비교하여 연속되지 않으면 리스트에 추가합니다.
2. 최초 요소 추가: 리스트가 비어 있을 때는 첫 번째 요소를 무조건 추가합니다.
3. 이후 요소 추가: 리스트의 마지막 요소와 현재 요소를 비교하고, 다를 경우에만 리스트에 추가합니다.

public class Solution {
    public int[] solution(int[] arr) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(arr[0]);  // 첫 번째 요소는 무조건 추가

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {  // 이전 요소와 현재 요소가 다르면
                list.add(arr[i]);  // 리스트에 추가
            }
        }

        // ArrayList를 배열로 변환
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

 

엥... 내 코드랑 무슨 차이임...

 

1. 내가 스택 쓴 거랑 얘랑 차이가 없는 거 같은데? 너는 진짜 이게 최선이라 생각해?

2. 이거 큐로도 풀 수 있는 거 맞아?

1. 스택 사용 vs. 직접 비교

스택을 사용하여 문제를 해결하는 것과 직접 비교를 사용하는 방법 사이에는 몇 가지 차이점이 있습니다:

• 복잡성: 스택을 사용하는 방법은 연속된 요소를 처리할 때 매번 스택의 top과 비교하고, 조건에 따라 push 또는 pop 연산을 수행합니다. 반면, 직접 비교 방법은 이전 요소와만 비교하고 조건에 맞는 경우 리스트에 추가하는 것으로 더 단순합니다. <- 뭐라카노...
• 공간 사용: 스택 사용 방법에서는 스택에 데이터를 추가하고 제거하는 과정에서 불필요한 push/pop 작업이 수반될 수 있습니다. 직접 비교 방법에서는 최초에 필요한 요소만 저장하므로 조금 더 효율적일 수 있습니다. <- 헛소리 ㄴㄴ...
• 가독성: 스택을 사용하면 코드의 의도가 명확해지지만, 이 문제와 같이 간단한 연속성 검사에는 스택의 사용이 과할 수 있습니다. 직접 비교 방법은 코드의 길이가 짧고 읽기 쉬워 유지 보수가 용이합니다. <- 지금 두 코드 거의 똑같다고...

개인적으로 이 문제의 경우 직접 비교 방법이 최선이라고 생각합니다. 문제의 복잡성을 고려할 때 추가적인 자료 구조를 도입하는 것보다는 간단하고 직관적인 로직을 사용하는 것이 더 적합합니다.

2. 큐로도 풀 수 있는가?

네, 이 문제를 큐로 해결할 수도 있습니다. 큐를 사용하는 방법은 스택과 매우 유사하며, 주로 FIFO(First-In-First-Out)의 특성을 활용하여 문제를 해결합니다. 그러나 이 경우, 큐의 사용이 스택이나 직접 비교 방법에 비해 별다른 이점을 제공하지는 않습니다. 큐를 사용할 경우, 다음과 같이 구현할 수 있습니다:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int[] solution(int[] arr) {
        Queue<Integer> queue = new LinkedList<>();
        int previous = -1; // 배열의 값은 0에서 9까지 이므로 -1은 초기 비교값으로 적절
        for (int num : arr) {
            if (num != previous) {
                queue.offer(num);
                previous = num;
            }
        }
        
        int[] answer = new int[queue.size()];
        int idx = 0;
        while (!queue.isEmpty()) {
            answer[idx++] = queue.poll();
        }
        return answer;
    }
}

 

흠... ㅇㅋ.

 

이 문제에서는 처음으로 효율성까지 나오던데 처음 내 코드(스택)에서는

채점 결과

정확성: 71.9

효율성: 28.1

합계: 100.0 / 100.0

이 점수를 받았다.

다른 건 어떨까?

 

두 번째 코드(어레이리스트):

채점 결과

정확성: 71.9

효율성: 28.1

합계: 100.0 / 100.0

차이가 없는디...

 

세 번째 코드(큐):

채점 결과

정확성: 71.9

효율성: 28.1

합계: 100.0 / 100.0

...

 

다만! 스택(내 코드)에서 효율성이 가장 떨어졌다.

테스트 1 〉

통과 (46.70ms, 117MB)

 

어레이리스트를 했을 때 효율성이 가장 좋았다.

테스트 1 〉

통과 (23.17ms, 110MB)

 

큐는 어레이리스트보다 약간 더 느렸다.

 

이제 효율성도 생각해 가면서 코테 쳐야 하는 때가 되었다.

 

+ 근데 좀 열받네.;

이거 분명 스택/큐 문젠데 <- 스택 or 큐로 풀라고 또는 푸는 게 좋다고 프로그래머스에서 큐레이션한 거 아님?

다른 사람의 풀이 보니까 다들 어레이리스트로 풂...

가이드를 이렇게 하면 안 되지...