★백준 1874번 스택 수열 C#으로 문제 풀어보기★

안녕하세요 박민성입니다.

 

오늘은 백준 1874번 스택 수열을 풀어 보겠습니다.

문제를 보면

입력은 첫 줄에는 1보다 크거나 같고 100,000이 작거나 같은 n이 주어집니다. 둘째 줄부터 1 이상 n이하의 정수가 하나씩 순서대로 주어집니다. 정수가 두 번 나오는 경우는 없습니다.

 

출력은 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력합니다. push연산은 +로, pop 연산은 -로 표현합니다. 불가능한 경우 NO를 출력합니다.

 

저는 문제를 보고 많이 헷갈렸습니다. 어떻게 구동? 작동되는지 이해가 안 되었거든요. 처음부터 보니 저에게는 이미 1부터 n까지의 수들을 가지고 있고 stack을 사용하여 입력된 수들을 차례대로 뽑을 수 있는지와 뽑을 수 있으면 그 방법을 +와 -로 한 줄씩 출력하면 됩니다. 

 

예제 입력 2를 보면 5는 1부터 n까지의 수고 만들어야 하는 수는 두 번째 줄부터

1 2 5 3 4가 들어오는데 제가 가진 1 2 3 4 5로 스택에 넣고 빼면서 1 2 5 3 4를 만들어야 합니다.

1을 + 해주고

1을 - 를 해주어 1를 완성시켜줍니다.

2를 + 해주고

2를 - 를 해주어 1 2를 완성시켜줍니다.

3을 + 해주고

4를 + 해주고 

5를 + 해주고 

5를 - 를 해주어 1 2 5를 완성시켜줍니다.

하지만 저에게 남아 있는 수가 없고( 이제 +를 해줄 수 없음 )

스택에서 pop(-)를 해주면 늦게 들어온 4가 나오니 (자료형 스택)

1 2 5 4가 됩니다 그럼 1 2 5 3 4를 만들 수 없으니 NO라고 출력해야 합니다.

 

같은 방법으로 예제 입력 1을 해보면 +, -를 해줄 텐데 

그걸 한 줄씩 출력해 주면 됩니다.

일단 스트링빌더는 +와 -를 한 줄씩 출력하기 때문에 시간초과가 뜰까봐 해주었습니다.

그리고 Stack을 생성시키고 n을 a에 입력받아줍니다.

index는 내가 가진 수들을 스택에 넣고 비교를 위하여 선언해 주었습니다.

마지막으로 스택 수열을 만들 수 없을 때 체크를 하기 위해 can이라는 불리언 변수도 선언해 주었습니다.

그리고 a만큼 스택 수열을 입력받기 위해서 for문을 돌려주고 안에는 스택 수열을 받아주었습니다.

그리고 for문 안에다가 while문을 적어서 입력된 수랑 스택에 있는 수와 같으면 빼주고 sb에 -를 추가해 줍니다.

같지 않는다면 +해주고 스택에 index를 넣어주고 index++해줍니다. 그러면 스택에는 1이 들어갑니다.

처음에는 이것만 썼지만 그러고 보니 스택이 0일 때 Peek로 비교조차도 안되어서 if문으로 스택에 들어 있는 수가 1 이상이면 검사하는 if문을 추가해 주었습니다. 없으면 똑같이 +해주고 index를 스택에 넣어주고 index를 ++해줍니다.

 

여기서 저희는 추가해야 하는 것이 있습니다. 아직 스택 수열을 만들 수 없을 때 NO를 출력해 줄 수 있는 코드가 없습니다.

처음에 예제 입력 2를 보고 어떨 때 수열을 만들 수가 없을까?라고 생각 해보았는데 그냥 index가 a보다 커지면 되지 않을까? 생각했습니다. 왜냐하면 계속 +해주고 -해주다가 해도 해도 안 되는 수(수열을 만들 수 없을 때) 그럼 if문으로 인하여 index가 계속해서 늘어날 테니 그렇게 해주면 된다고 생각했습니다. 실제로 예제 입력 2번을 적용했을 때 제대로 NO라고 떴습니다.

하지만 이 방법은 반례가 있었습니다. 첫 줄부터 2 1 2이나 2 2 1이 입력이 들어오면 수열을 만들 수 있어야 하지만 NO라고 떴습니다.

그래서 저는 방법을 생각해 보다가 다시 한번 예제를 보고 방법이 떠올랐습니다. 입력된 수가 지금 스택에 들어있는 수보다 작으면 NO가 뜬다고 생각했습니다.

그렇게 해서

처음에 선언하였던 can을 사용하여 입력을 반은 순간에 stack에 들어 있는 수가 b보다 크면 can을 false로 하고 break 해주었습니다. if ( stack.Count >= 1)를 해주어야 오류가 안 뜹니다. 스택에 들어 있는 수가 0이면 Peek로 비교할 수 없기 때문입니다.

마지막으로 for문이 끝났을 때 can이면 sb(+,-)를 출력해 주고 아니면 NO를 출력해 줍니다.

 

이것이 전체 코드입니다. 

 

이렇게 백준에 제출하였더니

정답이었습니다.