백준 (자바) 17608번 막대기

팀원: 효권, 유진, 이삭
문제출처: http://https://www.acmicpc.net/problem/17608
언어: java
Level: 브론즈
알고리즘 유형: stack

 

 

 

 

 

 

🚩Goal

• Stack을 활용한 기초 문제를 통해 스택의 기본 함수를 익히고, Stack문제의 접근방식을 파악하기!
• Stack과 관련된 메소드 POP(), push(), peek(), isEmpty()를 통해 가장 먼저 나와야 하는 데이터를 순차적으로 잘 꺼내는 코드를 작성해야함.

Why?

• 선입후출(First in Last out)의 개념을 익혀 데이터의 입출력 방식에 대한 이해와 활용도를 높이기 위함.
• 공간능력을 발휘해 이미지 트레이닝을 통한 컴퓨팅 사고력을 기를 수 있는 문제라고 생각해 선정.

 

 

---

 

Main

---

선행지식

Stack이란

• “쌓다” 또는 “더미”라는 의미를 가지며 접시를 쌓은 것을 말함
• 상자 안에 물건을 쌓는 것처럼 데이터를 쌓아 올리는 자료구조
• LIFO(Last In First Out): 마지막에 저장된 데이터를 먼저 꺼내는 구조
• Stack 메모리 영역 예시로는 지역변수를 저장하고 내버리는 식으로 사용되기도 함 

 

 

<백준 17608 막대기 문제>

 

<문제 이해하기>

<전체코드>

import java.util.*;
import java.io.*;

public class JavaTestStack {

	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 시스템입력 받는 생성자 객체
		Stack<Integer> stack = new Stack<>(); // 값을 담은 Stack 객체
		int N = Integer.parseInt(br.readLine()); // Stack 객체에 들어가는 막대기의 총 갯수
		
		int max = 0; // 가장 높은 높이의 막대기
		
		// N개 막대기를 Stack에 하나씩 추가한다.
		for(int i = 0; i < N; i++) {
			stack.push(Integer.parseInt(br.readLine()));// 입력된 막대기 값을 추가시켜준다.
			
			// 만약, stack의 가장 최근에 들어온 막대기의 높이가 가장 높은 막대기보다 클때
			if(max < stack.peek()) { 
				max = stack.peek(); // max를 가장 높은 막대기로 변경해준다.
			}
					
		}
		
		int h = 0;
		int result = 0;
		
		for(int i = 0; i<N; i++) {
			int p = stack.pop(); // 가장 최근에 들어온 값이 p 객체
			if(h < p) {
				h=p;
				result++;
			}
			if (p == max) break; // 가장 높은 막대기를 만나면 for문을 탈출한다.
		}
		
		// 보이는 막대기의 총 개수를 출력
		System.out.println(result);
	}

}

<슈도코드>

슈도코드란❔

“의사코드”라고도 하며, 컴퓨터 프로그램의 동작이나 알고리즘을 인간이 사용하는 언어로 작성한 것.

<참고>https://icedhotchoco.tistory.com/entry/pseudo-code

pseudo code(슈도코드, 의사코드)란?

 

stack(ㄷㅔ이터를 저장하는 메모리 공간 <- 정수값만 입력가능)		
N(막대기 전체 갯수)
max(최대 높이의 막대기)
	 	
for(N만큼 반복){
	stack에 들어올 막대기의 높이 값을 반복 추가
	
	
	if(가장 높은 막대의 높이 < 가장 나중에 들어온 막대기 높이){
		/* 
		가장 높은 높이의 막대기 값이 새로 들어오게 되면,
		이전의 최대 높이의 막대기 값을 방금 들어온 
		막대기의 값으로 바꿔주기	   	
		*/
		현재 최대 높이의 막대기 값(max) = 새로 들어와 반환한 최대 높이의 막대기 값
	}
	
	h(막대기의 높이)
	result(보는 방향으로 보이는 막대기 총 갯수)

	for(N만큼 반복){
		p(가장 나중에 들어온 막대 높이 값 제거 후 반환하는 객체)
		if(막대의 높이값 < 가장 나중에 들어온 높이값){
			막대의 높이값 = 현재의 막대 높이값을 제거하는 객체
			result를 +1 추가해주기
		}
	}

	if(가장 나중의 막대기 높이 > 가장 높은 막대기 높이){
		모든 조건에 만족하여 for반복문 탈출
	}
	
	result 결과값 출력(보는 방향에서 보이는 막대기 총 갯수 출력)
}

---

<테스트 실행결과>

• 결과로 메모리와 시간을 중점적으로 먼저 봄.
• 메모리의 경우 효율적인 제출 코드와 비교 시 약 2~10배까지 차이가 나타남.
• stack과 같이 데이터 값을 담는 객체는 메모리의 효율을 잘 파악하여 낭비되는 메모가 없는지 고려해야 하지 않을까 생각함.
• 반복문과 같은 구문은 실행 시간에 어느 정도의 영향이 있을 수 있기 때문에 주의해서 사용해야함.

Reference

• 백준 문제 17608

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

 

• 스택 문제풀이 예시

[백준] 10828번 : 스택 - JAVA [자바]

[백준] 10828번 : 스택 - JAVA [자바]

 

• 스택의 원리 및 예시

🧱 자바 Stack 구조 & 사용법 정리

🧱 자바 Stack 구조 & 사용법 정리

 

• 스택의 원리2

자바 [JAVA] - Stack (스택) 구현하기

자바 [JAVA] - Stack (스택) 구현하기

 

• 스택 메서드 정리

[Java] 자바 스택(Stack) 클래스 메서드 정리 및 활용

[Java] 자바 스택(Stack) 클래스 메서드 정리 및 활용

 

• 스택의 원리

[자료구조] | 스택(Stack)

[자료구조] | 스택(Stack)

 

• 상세한 문제풀이 방법

백준 17608번: 막대기 [JAVA]

백준 17608번: 막대기 [JAVA]

 

• 자바 코딩테스트를 위한 입출력 정리

자바 코딩테스트를 위한 정리 - 입출력

자바 코딩테스트를 위한 정리 - 입출력

 

• 백준 17608문제 참고 코드

백준 17608번: 막대기 [JAVA]

백준 17608번: 막대기 [JAVA]

 

• 슈도코드

pseudo code(슈도코드, 의사코드)란?

pseudo code(슈도코드, 의사코드)란?