<stdio.han>

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        Stack<int[]> stack = new Stack<>();
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) { // 탑은 0번부터가 아닌 1번부터 시작
            int top = Integer.parseInt(st.nextToken()); // 현재 확인중인 탑
            while (!stack.isEmpty()) {
                if (stack.peek()[1] >= top) {
                    bw.write(stack.peek()[0] + " ");
                    break;
                }
                stack.pop();
            }
            if (stack.isEmpty()) {
                bw.write("0 ");
            }
            stack.push(new int[]{i, top});
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[설명]

제일 왼쪽 탑부터 스택에 담긴 값들과 비교해가면 로직을 반복한다.

스택에는 높이가 작은 순서부터 큰순으로 오름차순으로값이 담기게 된다.

높은 6탑은 첫번째 탑이기 때문에 비교할 스택들이 없어 0을 bw.write 한 후 {탑의 위치, 탑의 높이}를 스택에 담는다.

높이 9탑은 스택에 담긴 6보다 높이가 높다. 그 뜻은 앞으로 확인할 탑들은 모두 높이 9 탑 때문에 스택에 담겼던 높이 6 탑을 만날 수 없다. 그러므로 높이 6 스택은 pop해준다. 높이 9 탑을 스택에 담는다.

높이 5탑과 스택에 담긴 높이9 탑과 비교해준다. 높이9 탑에 신호가 닿기 때문에 높이9의 위치를 출력해준 후 스택에 높이 5 스택을 담아준다.

높이 7탑과 스택에 담긴값과 비교해준다. 스택의 가장 위의 값인 높이 5와 비교를 해본다. 스택에 담겼던 스택 5탑은 현재 확인중인 높이 7탑 때문에 앞으로 모든신호를 못받게된다. 그러므로 스택에서 pop 해준다. 그 다음 스택에 담긴 값 높이 9랑 비교 하면 신호가 9에 닿는다. 9의 위치를 출력후 높이7 탑을 스택에 담는다.

높이 4탑과 스택에 담긴 값을 비교해본다. 스택의 top에 있는값 높이 7인탑과 비교해보니 바로 신호가 닿는다. 높이 7탑의 위치를 출력해준다.

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

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String word = br.readLine();
            if (word.length() >= M) { // 길이 M 이상만 저장
                map.put(word, map.getOrDefault(word, 0) + 1); // 같은 단어가 등록될경우 value를 하나씩 증가
            }
        }
        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                if (cmp == 0) {
                    int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
                    return lengthCompare == 0 ? o1.getKey().compareTo(o2.getKey()) : lengthCompare; // key의 길이가 같을경우(lengthCompare == 0일경우) 길이가 같은것은 사전순으로 정렬
                }
                return cmp;
            }
        });
        for (Map.Entry<String, Integer> entry : entryList) {
            bw.write(entry.getKey());
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[설명]

이 문제는 맵을 활용한 키와 밸류의 정렬, Comparator를 잘 활용해야하는 문제이다.

먼저 단어를 입력받을때 단어의 길이가 M 이상인 경우만 Map에 저장해준다. 같은 단어가 나올때 해당 단어의 갯수를 map으로 카운팅 해준다.

입력이 끝났다면 map의 Value를 기준으로 내림차순 정렬을 해준다. 그렇다면 

        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                return cmp;
            }
        });

이런식으로 정렬을 해주면 된다.

하지만 문제에서 value 가 같을 경우에는 길이가 긴순으로 재 정렬을 해줘야한다고 되어있다. 그래서 약간 변형해

        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                if (cmp == 0) {
                    int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
                    return lengthCompare; 
                }
                return cmp;
            }
        });

 cmp 가 같을 경우에 조건문을 걸어 길이가 긴순으로 내림차순을 해준다.

하지만 문제에 또다른 조건이 있다. 길이마저 같을 경우에는 사전순으로 정렬을 해준다고 되어있다.

        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                if (cmp == 0) {
                    int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
                    return lengthCompare == 0 ? o1.getKey().compareTo(o2.getKey()) : lengthCompare; // key의 길이가 같을경우(lengthCompare == 0일경우) 길이가 같은것은 사전순으로 정렬
                }
                return cmp;
            }
        });

3항연산자를 사용해 lengthComapre가 같을경우에는 o1.getKey().compareTo(o2.getKey()) 로 비교해사전순으로 정렬해준다. 

그리고 마지막 출력을 할 때

        for (Map.Entry<String, Integer> entry : entryList) {
        	System.out.println(entry.getKey());
        }

이런식으로 출력을 할 경우 시간초과가 발생한다. 문제설명 맨 마지막에 설명을 보듯 BufferedWriter를 사용해주어야 시간초과가 발생하지 않는다.

BufferedWriter를 사용해 다시 코드를 작성한다면

        for (Map.Entry<String, Integer> entry : entryList) {
            bw.write(entry.getKey());
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();

이런식으로 출력해 주어야 한다.