[C#] 2346번: 풍선 터뜨리기

목차

---

백준 단계별로 풀어보기

25.11.24

16단계: 스택, 큐, 덱 1

2346번: 풍선 터뜨리기

문제 링크 : https://www.acmicpc.net/problem/2346

 

문제를 풀기 위해 알아야 할 개념

>> LinkedList

: 아래 글에 정리해두었다.

 

자료구조

 

>> 튜플 (Tuple)

: 여러 데이터 요소를 그룹화하는 간결한 구문이다.

 

- 사용법

// 일반적인 사용법
(float, int) attack = (3.5f, 8);
life -= attack.Item1 * attack.Item2;

// 또 다른 사용법
(float Power, int Count) attack = (3.5f, 8);
life -= attack.Power * attack.Count;

var (power, count) = (3.5f, 8);
life -= power * count;

// 스왑도 간단하게 표현 가능
(a, b) = (b, a)

 

※ 공식 문서 - 튜플 형식

튜플 형식 - C# reference

 

>> ?? 연산자 (null 병합 연산자)

: null 병합 연산자는 왼쪽 피연산자의 값이 null이 아닌 경우 해당 값을 반환하고, 그렇지 않으면 오른쪽 피연사자를 평가하여 그 결과를 반환한다. 즉, null이라면 ?? 연산자의 오른쪽 값을 반환한다.

 

※ 공식 문서 - null 병합 연산자

?? 그리고?? = 연산자 - null 병합 연산자 - C# reference

 

문제 풀이

: N개의 풍선은 1번부터 N번까지 번호가 있고, 그 풍선 속에는 정수가 적혀있는 종이가 하나 있다. 따라서 튜플 형식을 활용하여 풍선의 번호와 정수를 담는다. 그리고 이 풍선은 원형으로 놓여있는데, 종이에 적힌 정수가 양수일 경우 오른쪽으로, 음수일 경우 왼쪽으로 이동해야 하기 때문에 Deque 자료구조를 활용하는 것이 적합하나, C# 에서 Deque 를 지원하지 않으므로 LinkedList를 활용하여 구현한다. 

1. StreamReader로 입력값을 받아 int값으로 변환하여 풍선의 개수를 담을 변수 n 에 담고, (int, int) 튜플형 LinkedList list 를 초기화하고, 각 풍선 안의 종이에 적힌 수를 입력받아 string형 배열 input 에 담는다.
2. for 반복문을 통해 LinkedList의 index 에는 풍선의 번호를, num 에는 풍선 안의 종이에 적힌 수를 int값으로 변환하여 list 의 뒤에 넣는다.
3. 제일 처음에는 1번 풍선을 터뜨리기에, 현재 LinkedListNode를 담을 변수 current 에 list 의 첫 번째 노드를 담는다.
4. while 반복문을 통해 아래 과정을 반복하여 터진 풍선의 번호를 차례로 나열한다.
   •     현재 LinkedListNode의 index 값과 num 값을 변수로 담고, index 값은 StringBuilder에 담는다.
   •     다음 노드를 담을 변수 nextNode 를 current 의 다음 노드로 지정하되, ?? 연산자를 통해 current 가 null 이라면 list 의 첫 번째 노드를 지정하고, current 는 list 에서 제거한다. 이때, list 에 더 이상 노드가 없다면 while 반복문을 break 한다.
   •     제거한 풍선 안의 종이에 적힌 수가 양수라면, 오른쪽으로 이동하므로 for 반복문을 통해 nextNode 를 다음 노드로 옮기되, ?? 연산자를 통해 nextNode 의 다음 노드가 null 이라면 list 의 첫 번째 노드를 지정한다. 이때, 처음 nextNode 를 초기화 할 때 이미 현재 노드에서 오른쪽으로 1칸 움직였으므로, for 반복문의 반복 횟수는 num - 1 이 된다.
   •     제거한 풍선 안의 종이에 적힌 수가 음수라면, 왼쪽으로 이동하므로 for 반복문을 통해 nextNode 를 이전 노드로 옮기되, ?? 연산자를 통해 nextNode 의 이전 노드가 null 이라면 list 의 마지막 노드를 지정한다.
   • 다음으로 터뜨릴 풍선의 노드를 찾았으므로, current 에 노드를 담는다.
5. while 반복문을 빠져나왔다면 StreamWriter로 StringBuilder에 담은 값을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        int n = int.Parse(sr.ReadLine());
        
        LinkedList<(int index, int num)> list = new LinkedList<(int, int)>();
        
        string[] input = sr.ReadLine().Split();

        for (int i = 0; i < n; i++)
        {
            list.AddLast((i + 1, int.Parse(input[i])));
        }

        LinkedListNode<(int index, int num)> current = list.First;

        while (true)
        {
            int index = current.Value.index;
            int num = current.Value.num;
            sb.Append(index).Append(" ");
            
            LinkedListNode<(int index, int num)> nextNode = current.Next ?? list.First;
            list.Remove(current);

            if (list.Count == 0) break;
            
            if (num > 0)
            {
                for (int i = 1; i < num; i++)
                {
                    nextNode = nextNode.Next ?? list.First;
                }
            }
            else
            {
                for (int i = 0; i < Math.Abs(num); i++)
                {
                    nextNode = nextNode.Previous ?? list.Last;
                }
            }
            
            current = nextNode;
        }

        sw.Write(sb.ToString());
    }
}

 

※ LinkedListNode를 사용하지 않고, Deque 처럼 푼 코드

: 사실 이 방식으로 먼저 풀었었다.

<hide/>
using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        int n = int.Parse(sr.ReadLine());
        
        LinkedList<(int index, int num)> list = new LinkedList<(int, int)>();
        
        string[] input = sr.ReadLine().Split();

        for (int i = 0; i < n; i++)
        {
            list.AddLast((i + 1, int.Parse(input[i])));
        }
        
        int index = list.First.Value.index;
        int num = list.First.Value.num;
        list.RemoveFirst();
        sb.Append(index).Append(" ");

        while (list.Count > 0)
        {
            if (num > 0)
            {
                for (int i = 0; i < num - 1; i++)
                {
                    int tempIndex = list.First.Value.index;
                    int tempNum = list.First.Value.num;
                    list.RemoveFirst();
                    list.AddLast((tempIndex, tempNum));
                }
                index = list.First.Value.index;
                num = list.First.Value.num;
                list.RemoveFirst();
            }
            else
            {
                for (int i = 0; i < Math.Abs(num) - 1; i++)
                {
                    int tempIndex = list.Last.Value.index;
                    int tempNum = list.Last.Value.num;
                    list.RemoveLast();
                    list.AddFirst((tempIndex, tempNum));
                }
                index = list.Last.Value.index;
                num = list.Last.Value.num;
                list.RemoveLast();
            }
            sb.Append(index).Append(" ");
        }

        sw.Write(sb.ToString());
    }
}