스택 및 큐와 같은 자료구조

스택

해결하는 것에 난이도가 있어서 메모할 문제

문제 링크

간단한 설명

위의 문제는 현재의 위치에서 좌우로 자신이 볼 수 있는 탑들의 숫자를 확인하는 문제이다.
볼 수 있는 탑의 기준은 현재 높이보다 더 큰 빌딩의 높이만 볼 수 있다.

해결 과정

처음에 접근할 때에는 인덱스를 반복 조회해서 확인을 하려고 하였으나 주어지는 배열의 크기가 100,000이기 때문에 이와 같이 해결을 할 경우 시간초과가 발생할 것이라고 판단되어서 다른 좋은 방법을 고안하였다.
하지만 스택을 생각하지 못했었고 아래와 같은 접근 알고리즘을 검색을 통해서 알게 되었다.

주요 로직

• 자신의 인덱스 이전의 값들을 비교 하면서 현재와 높이를 비교한다
• 이러한 로직으로 인덱스와 인덱스 사이에 있는 높이가 낮은 빌딩들을 제거해 주는 역할을 한다.
• 여기서 스택이 비어있지 않은 경우 자신 위치를 기준으로 높아지는 빌딩들이 스택에 저장된다.

// 초기에 스택을 넣어준다.
stack.add(new Node(0, buildings[0]));  
  
// 왼쪽 부터 순차적으로 빌딩 크기를 비교하면서 만약 중간에 낮은 빌딩들은 없앤다.  
for (int i = 1; i < buildings.length; i++) {  
	while (!stack.isEmpty()) {  
		// 반복문을 돌면서 현재 위치에서 높이가 낮은 건물들을 빼놓는다.  
		if (stack.peek().height <= buildings[i]) {  
			// system.out.println(i + " : " + stack.pop());  
			stack.pop();
		} else {  
			break;  
		}  
	}  
 
	// 만약 스택이 비어 있지 않으면 현재 중에서 가장 가까운 인덱스를 저장해 준다.  
	if (!stack.isEmpty()) {  
		answer[i].nearIndex = stack.peek().index + 1;  
	}  
 
	answer[i].watchSum += stack.size();  
	stack.add(new Node(i, buildings[i]));  
}