[코딩테스트] Programmers - 같은 숫자는 싫어 (실패)

 

https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=java

프로그래머스

 

 

풀이

스택을 이용해서 문제를 풀면 된다. 

(6/9 복습 중) -> 스택으로 풀면된다 해놓고 밑에서는 큐로 풀고 있다. 

 

 

코드1 - 오답

public int[] solution(int[] arr)
{
    Queue<int> queue = new Queue<int>();
    for (int i = 0; i < arr.Length; i++)
    {
        if (queue.Count > 0 && queue.Last() == arr[i])
        {
            continue;
        }
        else if (queue.Count > 0 && queue.Last() != arr[i])
        {
            queue.Enqueue(arr[i]);
        }

        if(queue.Count == 0)
        {
            queue.Enqueue(arr[i]);
        }
    }

    int[] answer = queue.ToArray();

    return answer;
}

 

이 문제는 c#을 지원하지 않아 llm으로 물어보며 내 코드가 정답인지 확인해봤다. 

오답이라고 한다. 효율성 테스트에서 오답이 나올 수 있다고 한다. 

어떤 부분에서 시간이 오래 걸리는지 봤는데, queue.Last()가 Linq 메서드라고 한다. Last()는 큐의 처음부터 끝까지 모든 요소를 다 검사한다고 한다. 그렇다면 arr[i]와 큐와 비교하는 연산을 계산해보면 시간복잡도는 O(N^2)이 나온다. 

문제에서 N은 최대 1,000,000이다. 1,000,000 * 1,000,000은 1,000,000,000,000이다. 1초에 컴퓨터는 3억~5억번 연산을 한다. 1,000,000,000,000이면.. 1초보다 훨씬 오래 걸린다. 

따라서 위 코드대로 하면 효율성 테스트에서 오답이 나온다. 

 

 

코드2 - 정답

public int[] solution(int[] arr)
{
    Queue<int> queue = new Queue<int>();
    int lastNumber = -1; 
    for (int i = 0; i < arr.Length; i++)
    {
        if (queue.Count > 0 && lastNumber == arr[i])
        {
            continue;
        }
        else if (queue.Count > 0 && lastNumber != arr[i])
        {
            queue.Enqueue(arr[i]);
            lastNumber = arr[i];
        }

        if(queue.Count == 0)
        {
            queue.Enqueue(arr[i]);
            lastNumber = arr[i];
        }
    }

    int[] answer = queue.ToArray();

    return answer;
}

 

마지막으로 넣은 숫자가 필요한 것이므로, 큐에 숫자를 넣을 때 그 숫자를 마지막 숫자로 저장해두고 이 마지막 숫자를 조건문에서 사용하면 된다. 

 

 

복습 1 풀이 (6/9)

[문제]

배열 arr 각 원소는 0 ~ 9까지 이루어져 있다.
배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고, 나머지는 제거한다.
(단, 제거된 후 arr 원소들의 순서는 유지한다.)

[입력]
배열 arr 

[출력]
arr에서 연속적으로 나타나는 숫자는 제거하고 남은 숫자들을 return 

[제한사항]
- 0 <= arr 크기 <= 1,000,000
- 0 <= arr 원소 크기 <= 9

[풀이]
중복되는 숫자는 하나만 남기고 없애고, 중복되지 않는 숫자는 그대로 두고
그걸 순서를 유지한채로 반환해주면 된다. 
해시 문제다. 처음 보는 숫자는 넣고, 중복되는 숫자는 넘어가기. 
딕셔너리에 있는 키값들을 answer 배열에 넣기. 
answer배열 반환 

딕셔너리에 arr배열 값들 넣기 > O(N)
딕셔너리 키값들 출력 > O(N) 
O(N + N) = O(N) 
N은 최대 1,000,000 > O(1,000,000) = 1초 안 넘어간다. 
이 풀이로 가자. 

 

 

코드 1 - 오답

public int[] solution(int[] arr)
{
    Dictionary<int, int> dict = new Dictionary<int, int>();
    foreach(int num in arr)
    {
        if(!dict.ContainsKey(num))
            dict.Add(num, 1);
        else
            continue;
    }

    int[] answer = new int[dict.Count];
    int answerIndex = 0; 
    foreach(int key in dict.Keys)
        answer[answerIndex++] = dict[key];

    return answer;
}

 

연속되는 숫자는 출력하지 말고 첫번째 숫자만을 출력해야 한다. 

이렇게 딕셔너리를 사용하면 같은 숫자는 하나만 남게 되므로, 잘못된 결과가 나오게 된다. 

 

 

코드 2 - 정답

public int[] solution(int[] arr)
{
    List<int> list = new List<int>();
    for(int i = 0; i < arr.Length; i++)
    {
        if(i == 0) 
            list.Add(arr[i]);
        else
        {
            if(arr[i-1] == arr[i])
                continue;
            list.Add(arr[i]);
        }
    }    

    return list.ToArray();
}

연속되는 숫자는 넘어가고, 연속되지 않은 숫자만 넣어주면 된다. 

이걸 그대로 코드로 옮기면 된다. 

 

문제 유형이 스택/큐다. 그런데 굳이 스택/큐로 풀지 않아도 충분히 풀 수 있는 문제였다. 

 

 

코드 3 - 오답 

public int[] solution(int[] arr)
    {
        Stack<int> stack = new Stack<int>();

        for(int i = 0; i < arr.Length; i++)
        {
            if(i == 0) 
                stack.Push(arr[i]);
            else
            {
                if(stack.Peek() == arr[i])
                    continue;
                stack.Push(arr[i]);
            }
        } 

        return stack.ToArray();
    }

스택/큐 문제이니, 스택으로 풀어봤다. 

ToAarray()로 스택을 배열로 바꾸면, 스택의 최상단에 있는 원소가 0번째 인덱스로 하여 차례대로 들어간 배열이 만들어진다. 

그래서 오답이 나온다. 

 

 

코드 4 - 정답

public int[] solution(int[] arr)
{
    Stack<int> stack = new Stack<int>();

    for(int i = 0; i < arr.Length; i++)
    {
        if(i == 0) 
            stack.Push(arr[i]);
        else
        {
            if(stack.Peek() == arr[i])
                continue;
            stack.Push(arr[i]);
        }
    } 

    int[] result = stack.ToArray();
    Array.Reverse(result);
    return result;
}

 

ToArray()로 만든 배열을 Array.Reverse를 이용해서 배열을 역순으로 만들어주니 통과한다. 

 

 

코드 5 - 정답

public int[] solution(int[] arr)
{
    Queue<int> queue = new Queue<int>();

    int lastNumber = 0; 

    for(int i = 0; i < arr.Length; i++)
    {
        if(i == 0)
        {
            queue.Enqueue(arr[i]);
            lastNumber = arr[i];
        }
        else
        {
            if(lastNumber == arr[i])
                continue;

            queue.Enqueue(arr[i]);
            lastNumber = arr[i];
        }
    }

    return queue.ToArray();
}

 

큐로도 풀어봤다.