c언어 25956번 목차세기 (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	
	int v[n]; //ex) v[1]은 제목 1 아래의 제목 2의 개수를 의미합니다. 즉 하위제목의 개수를 저장하는 배열입니다.
	int ans[n]; //답 (대입을 이용하니 초기화 하지 않아도 됩니다)
	int stack[n][2]; //스택 (대입을 이용하니 초기화 하지 않아도 됩니다)
	int cnt = 0; //스택의 position indicator
	int before = 0;
	
	for(int i=0; i<n; i++) { //n개 입력
        v[i] = 0; //이건 초기화 해주어야 합니다.
		int tmp;
		scanf("%d", &tmp); //입력
		
		if(!cnt || stack[cnt-1][0] <= tmp) { //스택이 비어있거나, 스택에서 가장 최근 것 보다 값이 같거나 더 클 때
			if(before+1 < tmp) { //입력이 잘못되었는지를 검사
				printf("-1");
				return 0;
			} 
			before = tmp; //갱신
            
            //스택에 집어넣기
			stack[cnt][0] = tmp;
			stack[cnt++][1] = i;
            
            //tmp은 tmp-1의 하위 제목입니다.
			v[tmp-1]++;
            
		} else { //스택에 요소가 있고, 스택에서 가장 최근 것보다 값이 작을 때
			before = tmp; //갱신
            
			while(cnt>0 && tmp <= stack[cnt-1][0]) { //스택보다 tmp의 값이 클 때까지 계속 스택의 요소들을 꺼냅니다.
				--cnt;
                int tmp2 = stack[cnt][0]; //스택에서 꺼낸 값의 값(제목)
				ans[stack[cnt][1]] = v[tmp2]; //답을 출력하는 배열에 스택에서 꺼낸 값의 값(제목)의 바로 아래 하위제목의 개수를 대입
				v[tmp2] = 0; //그런 다음 바로 아래 하위제목의 개수를 0으로 바꿈
			}
            
            //스택에 집어넣기
			stack[cnt][0] = tmp;
			stack[cnt++][1] = i;
            
            //tmp은 tmp-1의 하위 제목입니다.
			v[tmp-1]++;
		}
	}
	
	while(cnt--) { //스택에 남은 값 꺼내기
        int tmp2 = stack[cnt][0]; //스택에서 꺼낸 값의 값(제목)
		ans[stack[cnt][1]] = v[tmp2]; //답을 출력하는 배열에 스택에서 꺼낸 값의 값(제목)의 바로 아래 하위제목의 개수를 대입
		v[tmp2] = 0; //그런 다음 바로 아래 하위제목의 개수를 0으로 바꿈
	}
	for(int i=0; i<n; i++) printf("%d\n", ans[i]); //입력받은대로 출력
}

 

풀이 : 스택

 

1. 스택이 비어있거나, 스택에 가장 최근에 들어 온 값보다 같거나 더 크다면 스택에 집어 넣습니다

단 스택이 비어있을 때, 2이상의 값이 주어지거나, 스택의 최근 값보다 2이상 큰 경우 잘못된 입력이므로 -1을 출력한뒤 프로그램을 종료합니다.

 

2. 1.의 경우의 반대는 스택의 요소를 빼줍니다, 빼다가 이번에 입력된 값보다 작은 경우 중단 한 다음, 이번에 입력된 값을 스택에 넣어줍니다. 스택에서 뺀 경우 언제 입력됬는지를 이용하여 정답을 출력할때 이용할 ans에 하위 레벨의 개수를 저장합니다. 그런다음 하위레벨을 저장하고 있는 v의 값을 0으로 바꾸어 줍니다 (특정 레벨의 하위 레벨의 개수를 나타내는 값만)

 

3. 입력을 다 받았으나, 스택에 요소들이 남아있는 경우, 전부 pop 해줍니다. 이 과정엑서 2.에서 했던 것 처럼 입력된 순서에 맞는 위치의 ans에 옮겨주고 그 레벨의  v을 0으로 바꾸어 줍니다.

 

4. ans에 있는 요소들을 순서대로 출력합니다.

 

 

https://www.acmicpc.net/problem/25956

25956번: 목차 세기