[C#][프로그래머스 > 코딩테스트 기초] 배열 만들기 6

프로그래머스 > 코딩테스트 연습 > 코딩 기초 트레이닝 > 배열 만들기6

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

 

📒 문제

0과 1로만 이루어진 정수 배열 arr가 주어집니다. arr를 이용해 새로운 배열 stk을 만드려고 합니다.

i의 초기값을 0으로 설정하고 i가 arr의 길이보다 작으면 다음을 반복합니다.

• 만약 stk이 빈 배열이라면 arr[i]를 stk에 추가하고 i에 1을 더합니다.
• stk에 원소가 있고, stk의 마지막 원소가 arr[i]와 같으면 stk의 마지막 원소를 stk에서 제거하고 i에 1을 더합니다.
• stk에 원소가 있는데 stk의 마지막 원소가 arr[i]와 다르면 stk의 맨 마지막에 arr[i]를 추가하고 i에 1을 더합니다.

위 작업을 마친 후 만들어진 stk을 return 하는 solution 함수를 완성해 주세요.

단, 만약 빈 배열을 return 해야한다면 [-1]을 return 합니다.

제한사항

• 1 ≤ arr의 길이 ≤ 1,000,000
  • arr의 원소는 0 또는 1 입니다.

 

입출력 예

arr	result
[0, 1, 1, 1, 0]	[0, 1, 0]
[0, 1, 0, 1, 0]	[0, 1, 0, 1, 0]
[0, 1, 1, 0]	[-1]

 

입출력 예 설명

 

입출력 예 #1

• 각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.
  

  idx	arr[idx]	stk
  0	0	[]
  1	1	[0]
  2	1	[0,1]
  3	1	[0]
  4	0	[0, 1]
  5	-	[0, 1, 0]

  따라서 [0, 1, 0]을 return 합니다.

입출력 예 #2

• 각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다
  

  idx	arr[idx]	stk
  0	0	[]
  1	1	[0]
  2	0	[0,1]
  3	1	[0, 1, 0]
  4	0	[0, 1, 0, 1]
  5	-	[0, 1, 0, 1, 0]

  따라서 [0, 1, 0, 1, 0]을 return 합니다.

입출력 예 #3

• 각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.
  

  idx	arr[idx]	stk
  0	0	[]
  1	1	[0]
  2	1	[0,1]
  3	0	[0]
  4	-	[]

  마지막에 빈 배열이 되었으므로 [-1]을 return 합니다.

---

💻 소스코드

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] solution(int[] arr) {
         
        List<int> stk = new List<int>();
        for(int i = 0 ; i < arr.Length; i++)
        {
            if(stk.Count == 0) stk.Add(arr[i]);
            else
            {
                if(stk.Last() == arr[i]) stk.RemoveAt(stk.Count-1);
                else stk.Add(arr[i]);
            }
        }
        
        return stk.Count == 0 ? new int[]{-1} : stk.ToArray();
    }
}

 

다른풀이

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] solution(int[] arr) {
        
        Stack<int> stk = new Stack<int>();

        for(int i = 0; i < arr.Length; i++)
        {
            if (stk.Count == 0) stk.Push(arr[i]);
            else
            {
                if (stk.Peek() == arr[i]) stk.Pop();
                else stk.Push(arr[i]);
            }
        }
        
        return stk.Count == 0 ? new int[]{-1} : stk.Reverse().ToArray();
    }
}

 

※ 참고 사이트

Stack : https://code-piggy.tistory.com/entry/C-%EC%8A%A4%ED%83%9DStack

📝 풀이

처음 풀이는 List를 활용해서 해결했다.

문제에서 i가 계속해서 1씩 증가하기 때문에 for문을 사용했고

조건문을 통해 추가해야할 경우는 Add하고, 아닌 경우엔 RemoveAt을 사용해서 마지막 요소를 삭제했다.

마지막엔 3항연산자를 통해 리스트가 비어있는지 확인해서 비어 있다면 -1을 담은 배열을 아니면 List를 그대로 반환했다.

 

다음 풀이는

더 좋은 방법이 있는지 다른 사람들의 풀이를 찾아보다 Stack을 이용해서 풀이 한것을 발견했다.

스택은 마지막에 들어온걸 마지막에 빼는 특징이 있어 해당 문제에 더 적합해보여서 사용해보았다.

List와 흐름은 비슷하고 문법만 바뀐 느낌이다.

하지만 마지막에 Stack은 Array로 바꿔주기 전에 Reverse를 통해 꼭 뒤집어 줘야한다.

List는 뒤에서 부터 채워서 상관없지만, Stack은 앞으로 채우기 때문에 마지막에 뒤집어 줘야한다.

---

관련 포스팅

[C# 문법] List 메서드 모음

[C# 문법] Enumerable 클래스

[자료구조] 스택 (Stack)