백준 C# - 1874(+) 문제 설명 및 풀이)

1874 문제를 읽는데 무슨 내용인지 이해가 하나도 안갔다. 그래서 여러 블로그들을 찾아보면서 내용 설명과 코드를 봐도 이해가 안가서 문제 이해하는데에 제일 시간을 많이 소모했다... 

---

문제 설명

2가지만 알면된다.

1.n이 stack에 있는가? 2. stack.Peek()==n인가? 

---

위의 그림을 이용해서 예시를 풀어보자

예시 01

3
2
1
3

---

예시 02

2번째 1에서 stack.Peek()이 1이 아니므로 결과가 0이 나온다.

3
3
1
2

 

---

코드

01 변수 설정

int num = int.Parse(Console.ReadLine());
            
Stack<int> stack = new Stack<int>();
StringBuilder sb = new StringBuilder();

bool isNO = false;
int count = 1; // 현재 stack에 push된 가장 큰 수

---

02 n입력 받기

for (int i = 0; i < num; i++)
{
    int n = int.Parse(Console.ReadLine());  
    
    if(!stack.Contains(n))
    {
        // 밑에서 설명       
    }
    if (stack.Contains(n) && stack.Peek() == n)
    {
        // 밑에서 설명      
    }
    else
    {
        // 밑에서 설명                    
    }
}

---

03 n이 stack에 있는가?

stack에 있는지 여부는 Contains 메서드를 사용해서 확인하였다. stack에 Push가 끝난 후 count를 갱신한다.

왜 count가 n + 1인가요?

우리가 처음에 n = 3이여서 1,2,3을 Push했다고 가정해보자

count를 n+1값이아닌 n값인 3이면 다음 n = 5을 입력받았을때 push가 4,5만 해야하는데 3,4,5를 push한다. 그러므로 3이 또 들어오게 된다. 이를 방지하기 위해 n+1을 사용해야 한다.

if(!stack.Contains(n))
{
    for (int j = count; j <= n; j++)
    {
        if (count < n+1)
        {
            stack.Push(j);
            sb.AppendLine("+");
        }
    }
    count = n+1;
}

---

04 stack.Peek()==n 이 참인 경우

if (stack.Contains(n) && stack.Peek() == n)
{
    stack.Pop();
    sb.AppendLine("-");
}

---

05 stack.Peek()==n 거짓인 경우

else
{
    isNO = true;
}

---

06 결과 출력

if (isNO)
    Console.WriteLine("NO");
else
    Console.Write(sb.ToString());

 

 

 

 

 

 

 

 

 

반례모음을 해주신 게시글이 있어서 공유합니다!

1874 반례 모음

글 읽기 - 반례 모음