백준 17608번: 막대기 [JAVA]

2023. 3. 15. 00:57·개발/코딩테스트

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

 

17608번: 막대기

아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로

www.acmicpc.net

  • 풀이

마지막 막대기부터 세야하기 때문에 스택을 사용한다. 오른쪽부터 보이는 막대기를 세는데, 보였던 막대기보다 큰 막대기가 나올 때마다 카운트를 증가시키고, 막대기의 최대값이 나오면 종료한다.

  • 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		// 막대기 개수 N 입력
		int N = Integer.parseInt(bf.readLine());
		Stack <Integer> stack = new Stack <Integer>();
		
		int max = 0; // 가장 높은 블럭 높이
		
		// 각 막대기 높이 h 입력
		for (int i=0; i<N; i++) {
			stack.push(Integer.parseInt(bf.readLine()));
			if(max<stack.peek()) max=stack.peek();
		}
		
		int s = 0; // 보이는 블럭 높이
		int result = 0; // 결과값

		for (int i=0; i<N; i++) {
			int p = stack.pop();
			if(s<p) { // 보이는 블럭 높이보다 블럭이 크면 결과값++, 보이는 블럭 높이 변경
				s=p;
				result++;
			}
			if (p == max) break; // 최대 블럭 높이 만나면 break
		}
		
		// 결과 출력
		System.out.println(result);
	}

}

  • 다른 풀이 참고

왼쪽에 있는 막대기부터 입력을 할 때, 더 큰 막대기가 들어오면 기존 막대기는 의미가 없어진다. 따라서 더 큰 막대기가 들어올 때마다 기존 값 pop() 시키고 더 작은 막대기일 때만 계속 push()한다. 결과적으로는 보이는 막대기만 스택에 쌓이게 되므로 size()를 출력하면 된다.

  • 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		// 막대기 개수 N 입력
		int N = Integer.parseInt(bf.readLine());
		Stack <Integer> stack = new Stack <Integer>();
		
		for (int i = 0; i<N; i++) {
				int h = Integer.parseInt(bf.readLine());
				while (!stack.isEmpty()&&h>=stack.peek()) stack.pop(); // 현재 값보다 작은 peek() 값 pop()
				stack.push(h);
			}
		
		// 출력
		System.out.println(stack.size());
	}
}

시간 복잡도

N * O(while) = O(N)

'개발/코딩테스트' 카테고리의 다른 글
  • 백준 2960번: 도영이가 만든 맛있는 음식 [JAVA]
  • 백준 1759번: 암호만들기 [JAVA]
  • 백준 2164번: 카드2 [JAVA]
  • 백준 1158번: 요세푸스 문제 [JAVA]
로또
로또
게임 개발자 연습생의 발전 일지
  • 로또
    게임 개발 발전소
    로또
  • 전체
    오늘
    어제
    • 분류 전체보기 N
      • 개발
        • 코딩테스트
        • JAVA
        • DB
        • Unity
      • 강의 N
        • 패스트캠퍼스 0원 챌린지
        • 멋쟁이 사자처럼 유니티 부트캠프 N
      • 게임
        • 리뷰
  • 블로그 메뉴

    • 홈
    • 방명록
    • 글쓰기
  • 링크

    • GitHub
  • 공지사항

  • 인기 글

  • 태그

    패캠인강후기
    패스트캠퍼스
    dfs
    3D웹인터랙티브
    C4D
    오공완
    트리
    환급챌린지
    한번에끝내는프론트엔드개발초격차패키지Online
    자료구조
    패스트캠퍼스후기
    게임개발
    코딩테스트
    패캠챌린지
    BFS
    직장인자기계발
    C#
    그래프
    그리디알고리즘
    Java
    그리디
    수강료0원챌린지
    백준
    2839
    백트래킹
    완전탐색
    멋쟁이사자처럼후기
    분리집합
    직장인인강
    Unity
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
로또
백준 17608번: 막대기 [JAVA]
상단으로

티스토리툴바