백준 7662번
https://www.acmicpc.net/problem/7662

문제

---

생각하기

---

• 자료구조를 활용한다.

  • tree를 통해서 자동정렬을 활용한다.

    • 가장 큰 값은 뒤에서 빼내기, 가장 작은 값은 앞에서 빼내기

  • Map을 활용하면 값의 개수도 파악할 수 있다.

  • 결론은 TreeMap을 활용하자

동작

		if(treeMap.isEmpty()) return;
		else if(num == 1) { // 최댓값 삭제
			int maxNum = treeMap.lastKey();
			int defaultNum = treeMap.get(maxNum);
			if(defaultNum == 1) treeMap.remove(maxNum); // default수가 1이면 해당 key삭제
			else treeMap.put(maxNum, defaultNum-1); // 1이상이면 해당 key의 value를 value-1로 갱신
	
		}
		else if(num == -1) { // 최솟값 삭제
			int minNum = treeMap.firstKey();
			int defaultNum = treeMap.get(minNum);
			if(defaultNum == 1) treeMap.remove(minNum); // default수가 1이면 해당 key삭제
			else treeMap.put(minNum, defaultNum-1); // 1이상이면 해당 key의 value를 value-1로 갱신
		}

핵심 로직은 삭제이다. 삽인은 그냥 넣기만 하면 되니까 pass

treeMap이 비었으면 그대로 return

num이 1일 경우 최댓값을 가지고 오므로 treeMap에서 lastKey 메소드를 활용해서 key에 해당하는 값을 하나 제거한다. 제거는 value를 -1하는 방식으로하는데, 만약 value가 1일 경우, 그대로 해당 key값을 삭제한다.

최솟값은 firstKey메소드를 활용해서 가장 앞에서 가져온다. 최댓값과 로직은 동일하다.

코드

---

Java

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

public class Main {
	static TreeMap<Integer, Integer> treeMap = new TreeMap<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t=0; t<T; t++) {
			int Q = Integer.parseInt(br.readLine());
			
			while(Q-->0) {
				st = new StringTokenizer(br.readLine());
				String func = st.nextToken();
				int num = Integer.parseInt(st.nextToken());
				
				if(func.equals("I")) input(num); 
				else delete(num); 
			}
            
			if(treeMap.isEmpty()) sb.append("EMPTY").append('\n');
			else sb.append(treeMap.lastKey()).append(' ').append(treeMap.firstKey()).append('\n');
			
			treeMap.clear();
		}

		bw.write(sb.toString()); bw.flush(); bw.close();
	} // End of main
	
	private static void input(int num) {
		treeMap.put(num, treeMap.getOrDefault(num, 0)+1);
	} // End of input
	
	private static void delete(int num) {
		
		if(treeMap.isEmpty()) return;
		else if(num == 1) { // 최댓값 삭제
			int maxNum = treeMap.lastKey();
			int defaultNum = treeMap.get(maxNum);
			if(defaultNum == 1) treeMap.remove(maxNum); // default수가 1이면 해당 key삭제
			else treeMap.put(maxNum, defaultNum-1); // 1이상이면 해당 key의 value를 value-1로 갱신
	
		}
		else if(num == -1) { // 최솟값 삭제
			int minNum = treeMap.firstKey();
			int defaultNum = treeMap.get(minNum);
			if(defaultNum == 1) treeMap.remove(minNum); // default수가 1이면 해당 key삭제
			else treeMap.put(minNum, defaultNum-1); // 1이상이면 해당 key의 value를 value-1로 갱신
		}
		
	} // End of delete
} // End of Main class

Kotlin

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

private val treeMap = TreeMap<Int, Int>()
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()
    var st : StringTokenizer

    var T = br.readLine().toInt()
    while(T-->0) {
        var Q = br.readLine().toInt()

        while(Q-->0) {
            st = StringTokenizer(br.readLine())
            val func = st.nextToken()
            val num = st.nextToken().toInt()

            if(func.equals("I")) input(num)
            else delete(num)
        }

        if(treeMap.isEmpty()) sb.append("EMPTY").append('\n')
        else sb.append(treeMap.lastKey()).append(' ').append(treeMap.firstKey()).append('\n')
        treeMap.clear()
    }

    bw.write(sb.toString()); bw.close()
} // End of main

private fun input(num : Int) {
    treeMap.put(num, treeMap.getOrDefault(num, 0)+1)
} // End of input

private fun delete(num : Int) {
    if(treeMap.isEmpty()) return
    else if(num == 1) {
        val maxNum = treeMap.lastKey()
        val defaultNum = treeMap[maxNum]
        if(defaultNum == 1) treeMap.remove(maxNum)
        else if (defaultNum != null) {
            treeMap.put(maxNum, defaultNum-1)
        }
    }
    else {
        val minNum = treeMap.firstKey()
        val defaultNum = treeMap[minNum]
        if(defaultNum == 1) treeMap.remove(minNum)
        else if (defaultNum != null) {
            treeMap.put(minNum, defaultNum-1)
        }
    }
} // End of delete