스택활용하기3

스택문제는 참으로 까다롭다. 경험으로 봤을때는 코드로 만들고나서 반드시 Test case를 손으로 똑같이 해봐야 하는 거 같다. 그래야 문제점을 발견할 수 있다. 또한 스택처리 반복안에서 분기를 치거나 첫노드를 먼저 Push하거나 하는 것은 좋지 못하다. 스택처리 반복이 복잡해질 수록 추적하기 어렵기 때문이다.

간단한 스택처리 Test case로 한줄한줄 한손한손 따라가면서 디버깅해보자.

---

문제

높이가 다른 N개의 전봇대가 주어진다.

서로다른 전봇대끼리 전깃줄을 잇는다.

1. 이웃한 두개의 전봇대는 전깃줄을 잇는 것이 무조건 가능하다.

2. 이웃하지 않은 두개의 전봇대 사이에 양측의 두 전봇대보다 높이가 높거나 같다면 전깃줄을 이을 수 없다.

위의 그림의 경우 5가지의 경우가 있다. 1번과 3번 전봇대는 2번 전봇대 때문에 전깃줄을 이을 수 없다.

N(N:1~100000)개의 전봇대와 높이가 각각 주어질때, 전깃줄을 이을 수 있는 경우의 수를 구하라.

 

입력

7

2 4 3 2 2 5 1

 

출력

8

---

접근방법

1. 모든 경우의 수를 구한다.

간단하게 모든 경우의 수를 구할 수 있다. 이중 for문으로 탐색하는 것이다.

그러나 N의 값이 100000이므로 최악의 경우 100000의 제곱이 시간복잡도이므로 Timeout이다.

코드는 아래와 같겠다.

#include <stdio.h>

int N;
int H[110000];
int stack[110000];
int sp=0;

void Input(){
	scanf("%d ",&N);
	for(int i=0; i<N; i++){
		scanf("%d",&H[i]);
	}
}

int Stack(){
	int cnt=0;
	for(int i=0; i<N-1; i++){ //시작점i는 0~N-3
		int h=0;
		for(int j=i+1; j<N; j++){ //j는 비교 인덱스
			if(h<H[j]){
				cnt++;
				h=H[j];
			}
			if(H[i]<=H[j]) break;
		}
	}
	
	return cnt;
}

int main() {
	Input();
	int ans = 0; //N-1 만큼은 무조건 송수신가능 : 서로 인접한 안테나의 수
	
	ans = Stack();
	
	printf("%d", ans);
	
	
	return 0;
}

 

2. 스택을 활용하자

스택활용시 O(N)으로 시간복잡도를 줄일 수 있을 것이다.

스택반복문의 순서는 아래와 같겠다.

a. 스택의 Top보다 탐색노드가 크면 더이상 전깃줄을 이을 수 없으므로 Pop하며 Pop한 수만큼 cnt를 증가시킨다.

b. 스택이 비어있지 않다면 이웃하는 노드끼리 전깃줄을 이을 수 있으므로 cnt를 하나 증가시킨다.

   이때, 탐색노드와 Top이 같은 값이라면 Pop해준다. 같은 값을 계속 Push하면 스택에 유의미한 data가 남지 않기 때문

c. 현재의 노드를 Push한다.

 

코드는 아래와 같다.

스택 역시 Queue와 마찬가지로 Pop, Push, Empty, Top을 나누어주는 것이 깔끔하겠다.

#include <stdio.h>

int N;
int H[110000];
int stack[110000];
int sp=0;

void Input(){
	scanf("%d ",&N);
	for(int i=0; i<N; i++){
		scanf("%d",&H[i]);
	}
}

void Push(int data){
	stack[++sp] = data;
}

int Empty(){
	return sp==0;
}

int Top(){
	return stack[sp]	;
}

void Pop(){
	sp--;
}


int Stack(){
	int cnt=0;
	sp = 0;
	for(int i=0; i<N; i++){
		/*
		while(!Empty() && (Top() < H[i] )) //스택이 더 작으면
		{
			cnt++;
			Pop();
		}
		*/
		for(; sp>0&&stack[sp]<H[i]; sp--)
		{
			cnt++;
		}
		if(!Empty())
		{
			cnt++;
			if(Top()==H[i]) Pop();
		}
			
		Push(H[i]);
	}

	
	return cnt;
}

int main() {
	Input();
	int ans = 0;
	
	ans = Stack();
	
	printf("%d", ans);
	
	
	return 0;
}