Catalan Number

1. 문제

1부터 n 까지의 정수가 차례로 스택에 push 된다.

push 가 이루어지는 중간에, 또는 모든 숫자들이 push된 이 후에 언제든지 임의로 숫자들을

pop 할 수 있다.

이렇게 pop 된 숫자들을 차례로 나열한 수열을 catalan number 라 한다.

​

예를 들어, n이 4 라면 1,2,3,4 가 차례로 push 된다.

1,2,3,4 모두 push 된 뒤, 네 번 pop 하면 4,3,2,1 이라는 수열이 만들어 진다.

반면에 1,2 가 push 된 뒤, 두 번 pop을 하고, 나머지 3,4 가 push 된 뒤 또 두 번 pop을 하면

2,1,4,3 이라는 수열이 만들어 진다.

 

따라서, 앞서 말한 대로 4,3,2,1 과 2,1,4,3 은 둘 다 catalan number 이다.

하지만 이렇게 pop을 해도 3,4,1,2 이라는 수열은 만들어 질 수 없는데,

따라서 이는 catalan number가 아니다. 

 

n 그리고 1부터 n까지의 숫자로 이루어진 수열이 주어질 때,

그 수열이 catalan number 인지 아닌지를 알아내는 프로그램을 작성하시오. 

 

입력 형식

첫 번째 줄에 100 이하의 자연수 n 이 주어진다.

두 번째 줄에는 1부터 n 까지의 수로 이루어진 수열이 주어진다.

​

출력 형식

입력으로 주어진 수열이 catalan number 라면 YES, 아니면 NO를 출력한다.

​

입출력 예

입력

4

2 1 4 3

​

출력

YES 

 

2. 문제 분석

주어진 문제는 탐색을 통해서 해결할 수 있는 문제가 아니다.

다른 방식의 접근법이 필요하다.

 

[가정]

​사용자로부터 임의의 수 2 1 4 3 을 입력받았고, 이 값들을 배열에 저장했다고 가정하자.

( 배열의 이름은 Number라고 두자. )

그리고, 배열의 인덱스 만을 뽑아 보자.

그리고, [0]번째 인덱스에 위치에 j값으로 두고,

 위의 Number 배열의 [0] 공간을 초기 위치로 i값이라 두면 아래와 같은 그림이 된다.

그리고, 자료구조의 스택이 필요한데, 스택까지 표시해보자.

위에서 보다시피, i와 j값은 같은 Number배열의 Index값이다.

다만, 가독성과 가식성을 위해서 일부러 따로 떼어둔 것이다.

​

규칙

1. i가 Number[j] 보다 작으면, i를 하나 증가시키고 스택에 push한다.

2. i가 Number[j] 보다 크거나 같으면, 스택에서 pop을 한다.

​

시작해보자.

㉠. Number[j] 값이 i값보다 크므로, i값을 증가 시키고 스택에 저장한다.

다시, Number[j]와 i값을 비교해본다. 

Number[j] 값이 i값보다 크므로, i값을 증가 시키고 스택에 저장한다.

다시, Number[j]와 i값을 비교해본다.

이 경우에는 i가 Number[j] 보다 크거나 같은 경우이다.

​

㉡. 스택에서 데이터를 pop시킨다. ( 현재 스택은 비어있지 않다.)

pop시킬려는 data가 2값으로 Number[j]의 값과 서로 같다.

이 경우에는 pass하고 j를 하나 증가시킨다.

다시, Number[j]와 i값을 비교해본다. 

이 경우에는 i가 Number[j] 보다 크거나 같은 경우이다.

스택에서 데이터를 pop시킨다. ( 현재 스택은 비어 있지 않으므로, pop할 수 있다.)

스택에서 pop시킨 데이터 값과 Number[j]는 1로 서로 같다.

이 경우는 pass하고 j를 하나 증가시킨다.

다시, Number[j]와 i값을 비교해본다. 

i가 Number[j] 보다 작다.

​

㉢. 아직 i가 배열의 길이를 넘어 서지 않았으며,

      i가 Number[j] 보다 작다. i를 하나 증가시키고 스택에 push한다.

그리고 다시, Number[j]와 i값을 비교해본다.

다시, i가 Number[j] 보다 작다. i를 하나 증가시키고 스택에 push한다.

그리고 다시, Number[j]와 i값을 비교해본다.

i가 Number[j] 보다 크거나 같다.

​

㉣. i가 Number[j] 보다 크거나 같으면, 스택에서 pop을 한다.

스택에서 pop시킨 데이터와 Number[j]값이 같다. 이 경우는 pass하고, j를 하나 증가시킨다.

다시, Number[j]와 i값을 비교해본다.

다시, i가 Number[j] 보다 크거나 같은 경우이다. 스택에서 pop을 한다.

스택에서 pop을 할 데이터와 Number[j]는 3으로 서로 같다.

이 경우 pass하고 j를 하나 증가시킨다.

위의 경우는 규칙의 두 가지 경우를 따져주어야 하는데,

1. i가 Number[j] 보다 크거나 같은 경우로 들어오면 스택이 비어있기 때문에, break를 해준다.

그리고 나서, i가 이미 배열의 길이를 넘어섰으므로, YES를 출력하고 끝낸다.

2.  i가 Number[j] 보다 작은 경우에는 바로

i가 이미 배열의 길이를 넘어섰으므로, YES를 출력하고 끝낸다.

 

3. 구현

프로그램 실행결과1

프로그램 실행결과2

 

4. 헤더 파일 & 소스 파일

common.h

0.00MB

main.c

0.00MB

MyStack.c

0.00MB

MyStack.h

0.00MB