<stdio.han>

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();

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

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

[정답 코드]

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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        BigInteger[] dist = new BigInteger[N - 1]; // 거리 배열
        BigInteger[] cost = new BigInteger[N]; // 비용 배열

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            dist[i] = new BigInteger(st.nextToken()); // 거리 배열 입력
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            cost[i] = new BigInteger(st.nextToken()); // 비용 배열 입력
        }

        BigInteger total = BigInteger.ZERO; // 총 주유 비용
        BigInteger min = cost[0]; // 가장 싼 기름 값
        for (int i = 0; i < N-1; i++) {
            if (min.compareTo(cost[i]) > 0) { // 왼쪽값이 오른쪽 값보다 크면 1, 같으면 0, 작으면 -1
                min = cost[i]; // 현재 가장 싼 기름 값 보다 더 싼 곳이 있을경우 갱신
            }
            total = total.add(min.multiply(dist[i])); // 가야할 거리 * 현재 가장 싼 기름값
        }
        System.out.println(total); // 출력
    }
}

[설명]

이 문제는 그리디 알고리즘 문제이다. 처음 문제를 봤을때는 쉬워 보이지만 아이디어가 잘 생각나지 않아 구글링을해 다른사람들의 아이디어를 참고했다. 

기본적인 아이디어는 현재 알고있는 기름값 보다 더 싼 비용의 기름값을 만날때 까지 충전해 길을 가는것이다.

예를들면 노드가 8 9 9 5 6 2 4 4 5 1 1 이런식으로 되어있다면 시작지점에서 가장 싼 기름값은 1리터당 8원이다. 그다음 노드의 비용응 9이므로 그다음 싼 기름값인 지점인 5노드까지 8원 인 노드에서 한번에 충전해서 가는것이다. 그 다음 더 싼 비용의 노드를 만나면 그때 가장 싼 기름값을 갱신시켜 그보다 싼 비용의 노드를 만날때 까지 가는것이다. 

쉽게 보자면 8 9 9 5 6 2 4 4 5 1 1 이 아닌 8 8 8 5 5 2 2 2 2 1 1 이렇게 볼 수 있다. 코드에 주석이 달려 있으니 확인해보면 좋다.

중요한 점이 하나 더 있다. 바로 BigInteger를 사용하는 것이다. 이 문제는 매우 큰 수를 사용하기 때문에 int로는 정답을 도출해 낼 수 없다.

BigInteger total 에 0이 담겨야한다. 이 때 total = 0이 아닌 BigInteger.ZERO 로 0을 담을 수 있다.

BigInteger 끼리의 대수 비교를 할 때 단순 부등호를 활용해 비교하는것이 아닌. BigInteger1.compareTo(BigInteger2) 를 활용해야 한다. 이때 왼쪽에 적은 BigInteger1이 오른쪽에 적은 BigInteger보다 크다면 1, 같으면 0, 작다면 -1이 출력된다.

그래서 현재 알고있는 가장 싼 기름값 보다 새로 알게된 기름값이 더 싸다면 1이 출력되 if문이 true가 되어 가장 싼 기름값을 갱신해준다.

마지막에 가야할거리*기름값을 계산할때 total = total + ( min * dist[i] )가 아닌 BigInteger.add(BigInteger.multiply(BigInteger) 형식으로 계산을 해주어야 한다.

결론적으로 이 문제는 그리디 + BigInteger의 활용하는 문제였다.

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

[정답 코드]

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 T = Integer.parseInt(st.nextToken()); // T개의 테스트 케이스
        int[] answer = new int[T]; // 한번에 출력하기 위한 answer 배열
        for (int i = 0; i < T; i++) { // T번의 반복
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int[] ranks = new int[N]; // N등까지 존재함
            Map<Integer, Integer> countMap = new HashMap<>();
            st = new StringTokenizer(br.readLine(), " ");
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < N; j++) {
                int data = Integer.parseInt(st.nextToken());
                countMap.put(data, countMap.getOrDefault(data, 0) + 1); // 해당팀의 인원이 6명되는지 체크
                ranks[j] = data; // 각 등수의 팀
                max = Math.max(max, data); // 가장 큰 번호의 팀
            }

            int[] fifthPlayer = new int[max + 1]; // 해당 팀의 5번째 선수
            Map<Integer, Integer> scoreMap = new HashMap<>();
            Map<Integer, Integer> tmpMap = new HashMap<>();
            int score = 1;

            for (int rank : ranks) {
                if (countMap.get(rank) == 6) { // 팀원이 6명 모두 통과한 팀만
                    tmpMap.put(rank, tmpMap.getOrDefault(rank, 0) + 1);

                    if (tmpMap.get(rank) <= 4) { // 해당팀의 4등까지만 점수를 기록함
                        scoreMap.put(rank, scoreMap.getOrDefault(rank, 0) + score);
                    }

                    if (tmpMap.get(rank) == 5) { // 해당 팀의 5번째 선수의 점수
                        fifthPlayer[rank] = score;
                    }

                    score++;

                }
            }
            int result = Integer.MAX_VALUE;
            int fifthScore = Integer.MAX_VALUE;
            for (Integer key : scoreMap.keySet()) {
                int tmp = scoreMap.get(key);
                if (tmp < result) { // 점수가 가장 낮은팀이 우승
                    result = tmp;
                    fifthScore = fifthPlayer[key];
                    answer[i] = key;
                } else if (tmp == result) { // 점수가 동점일 경우 5번째 선수의 점수가 낮을 경우 우승
                    if (fifthScore > fifthPlayer[key]) {
                        answer[i] = key;
                    }
                }
            }
        }
        for (int i : answer) {
            System.out.println(i); // 출력
        }
    }
}

[설명]

이 문제는 구현 문제이다. 그런데 문제가 어려워서 그런건지 백준의 질문게시판에도 질문도 없고 답변도 없고 구글링에도 자료가 많이 부족하다. 그래서 푸는데 많이 어려움을 겪었다. map.getOrDefault()를 사용해 맵에 값이 없을 경우 default 값을 넣어주는 함수를 활용한게 코드를 많이 줄일수있었다.

백준 2468번: 안전 영역[JAVA]

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

[정답 코드]

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

public class Main {
    static int N,result, count, nx, ny;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1}; // 상하좌우 4방탐색
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<Integer> list = new ArrayList<>();
    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(), " ");


        // graph 초기화
        N = Integer.parseInt(st.nextToken());
        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());

                // 건물의 높이들이 담긴 리스트
                if (!list.contains(graph[i][j])) { // 중복체크
                    list.add(graph[i][j]);
                }
            }
        }

        result = 1;
        for (Integer height : list) { // 0부터 끝까지 탐색하는것은 비효율적이기 때문에 리스트 활용
            count = 0;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && graph[i][j] >= height) {
                        count++;
                        dfs(height, i, j);
                    }
                }
            }
            result = Math.max(result, count); // 새로탐색한결과 중에 더 큰값 저장
        }
        System.out.println(result);
    }

    static void dfs(int height, int x, int y) {
        visited[x][y] = true;
        // 4방탐색
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) { // 그래프 범위 안에 있을 경우
                if (!visited[nx][ny]) { // 방문하지 않은 건물인 경우
                    if (graph[nx][ny] >= height) { // 그 건물이 물의 높이보다 높을 경우
                        dfs(height, nx, ny);  // 상하좌우 인접한 건물을 찾는다
                    }
                }
            }
        }
    }

}

[설명]

이 문제는 완전탐색 알고리즘이다. 그중 dfs 알고리즘을 활용해 문제를 해결했다. dx/dy 기법을 활용한 4방 탐색도 활용했다. 먼저 2차원 배열을 선언해준다. 이 때 중요한점이 입력값들을 중복값을 체크하며 리스트에 담아놔야한다. 그렇지 않을 경우는 비의 양을 0부터 끝까지 중복탐색해야해서 메모리 초과가 나거나 비효율적이다. 

dfs 로직은 4방탐색을 하며 그 범위가 방문하지않은 건물이며 그 건물이 물의 높이 보다 높을경우 dfs를 다시 실행한다. 

그 후 결과값을 비교해 최대값을 출력한다.

백준 1182번: 부분수열의 합[JAVA]

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

[정답 코드]

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

public class Main {
    static int N, S, result = 0;
    static int[] subsequence;

    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(), " ");

        N = Integer.parseInt(st.nextToken()); // 정수의 개수
        S = Integer.parseInt(st.nextToken()); // 타깃 넘버
        subsequence = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            subsequence[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);


        if (S == 0) { // S가 0일 때 result--
            result--;
        }
        System.out.println(result);


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

    public static void dfs(int depth, int sum) {
        if (depth == N) { // depth 가 마지막까지 갔을 경우
            if (sum == S) { // 그 중에 sum 이 타깃 넘버일 경우
                result++;
            }
            return;
        }
        dfs(depth + 1, sum + subsequence[depth]); // 원소를 선택했을 경우의 수열의 합
        dfs(depth + 1, sum); // 원소를 선택하지 않았을 경우의 수열의 합
    }
}

[설명]

이 문제는 브루트 포스 알고리즘 그중에 dfs알고리즘을 이용해 풀수있는 문제이다. 문제 설명을 하자면 숫자가 주어지면 그 수를가지고 만들 수 있는 모든 부분수열을들중 부분수열들의 합이 S 인 경우의 수를 출력하는 문제이다.

예를 들면 숫자가 1, 2, 3 이 주어졌다면 가능한 부분수열은 {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, {3} 이다. 수열들의 모습을 보면 브루트포스 알고리즘을 활용했을때의 결과 같이 생겼다.

코드로 구현했을 경우 한 가지 문제가 있다. S가 0일경우이다.  dfs 로직을 실행할 때 부분수열들의 합이 담기는 변수 sum 이 처음에 0을 초기화가 되어있기 때문에 원소를 아무것도 선택하지 않는다면 부분수열의 합이 0이라고 계산되기 때문이다. 그렇기 때문에 S가 0일경우 마지막에 결과값에 1을 빼주어야한다.