99클럽 3기 코테 스터디 10일차 TIL /[백준] 11279번 최대힙 자바 풀이

 

 

 

 

 

 

1. 오늘의 학습 문제 

---

문제

---

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

 

최대 힙 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음) (하단 참고)

256 MB

82464

39471

31259

49.427%

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 복사

13
0
1
2
0
0
3
2
1
0
0
0
0
0

예제 출력 1 복사

0
2
1
3
2
1
0
0

 

 

 

 

 

어제 풀었던 문제와 최대힙-최소힙 조건만 다르고 같은 문제였다. 

https://pudingcoding.tistory.com/124

99클럽 3기 코테 스터디 9일차 TIL /[백준] 1927 최소 힙 자바 풀이

 

 

코드

---

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

public class Main{

    public static void main(String[] args) throws IOException{ //(String[] args는 명령줄 인수로, 터미널, cmd등에서 프로그램을 실행할 때 인수를 전달할 수 있는 기능

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //InputStreamReader은 system.in이 읽어들이는바이트 스트림을 문자 스트림으로 바꾸어줌.
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));

        PriorityQueue<Integer> MaxHeap=new PriorityQueue<>(Collections.reverseOrder()); //최대힙선언

        int n=Integer.parseInt(br.readLine());
        //br.read()는 한 문자를 읽어 아스키코드값을 반환하며, readLine()은 문자열을 읽어들임.

        for(int i=0;i<n;i++){
            int x= Integer.parseInt(br.readLine());

            if(x==0){
                bw.write(  MaxHeap.isEmpty()? "0\n" : MaxHeap.poll()+"\n");
            }
            else{
                MaxHeap.add(x);
            }

        }

        bw.flush();
        bw.close();
        br.close();


    }
}

 

 

코드를 작성하며 복습했고, 몇가지 개념을 정리했다. 

1. main함수에 (String[] args)는 명령줄 인수로, 터미널이나 프롬프트 등에서 실행될 때 인수를 전달받을 수 있게하는 기능이다. 

2. system.in은 바이트 스트림을 읽어들이고, 이를 InputStreamReader가 문자 스트림으로 변환한다.

3. BufferedReader의 메서드에서 read()는 한 문자를 읽어들여 아스키코드값을 읽으며, readLine()은 문자열을 읽어들인다. readLine()으로 읽어서 형변환을 할 수 있다. 

4. 20번째 라인에서 ? 물음표를 통해 삼항 연산자로 코드를 단순화했다. 

 

2. 오늘의 회고

---

 

• 유사한 문제를 연달아푸니 개념이 잘 정리된다. 
• 다음에 힙을 사용하게 될때, 힙 구조를 직접 구현해보자

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL