Java 코딩테스트

패스트캠퍼스 Java 코딩테스트 강의 4주차

https://github.com/orgs/20-with-Java/repositories

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java

https://flint-guppy-e31.notion.site/6a2385deb9c3406bac68dd814da05ec4

[패스트캠퍼스] 코딩테스트 학습 플래너

강의소개PDF

https://storage.googleapis.com/static.fastcampus.co.kr/prod/uploads/202302/022050-717/[%ED%8C%A8%EC%8A%A4%ED%8A%B8%EC%BA%A0%ED%8D%BC%EC%8A%A4]-%EA%B5%90%EC%9C%A1%EA%B3%BC%EC%A0%95%EC%86%8C%EA%B0%9C%EC%84%9C-%ED%95%B5%EC%8B%AC%EC%9C%A0%ED%98%95-20%EA%B0%9C%EB%A1%9C-%ED%95%9C-%EB%B2%88%EC%97%90-%EB%81%9D%EB%82%B4%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-with-java-%EC%B4%88%EA%B2%A9%EC%B0%A8-%ED%8C%A8%ED%82%A4%EC%A7%80-online..pdf 

 

 

https://fastcampus.co.kr/dev_online_codingtest

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼

 

Chapter04 완전탐색 - 시뮬레이션

완전탐색은 모든 경우의 수를 시도한다.

문제해결의 가장기본적인 방법으로 무식한 힘(Brute Force)으로 별도의 최적화 없이, 효율성을 고려하지 않는 풀이방법( 문제의 크기가 작으면 유용하다 , 부분점수 문제라면 전체를 풀지 못해도 작은 데이터에 대한 점수를 얻을 수 있다 - 선형 완전탐색 , 비선형완전탐색 등)

ex) BOJ 2309 - 일곱난쟁이

문제 : 9명의 난쟁이의 키가 주어지는데, 키의 합이 100이 되는 일곱 난쟁이를 찾아야 한다.

방법 : 9명중 일곱 난쟁이가 아닌 둘을 찾는 풀이법

1) 일곱난쟁이를 찾는다.

2) 일곱난쟁이를 정렬한다.

목표 : 키의 합이 100이 되는 일곱 난쟁이를 찾아야 한다.

상황 :  9명의 난쟁이의 키가 주어지는데

시간복잡도 O(N2)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Baekjoon2309 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //9난쟁이    
        int[] h = new int[9];
        // 9 난쟁이 키합계
        int sum =0;
        // 9난쟁이 키
        for(int i=0; i<9;i++){
            h[i] = Integer.parseInt(br.readLine());
            // 9 난쟁이 키합계
            sum += h[i];
        }
        // 7곱 난쟁이
        int[] ans = new int[7];
        // 난쟁이 9명
        boolean found= false;
        for(int i =0; i<9; i++){
            for(int j=i+1; j< 9; j++){
                if(sum - h[i]- h[j] == 100){
                    System.out.println(found);
                    int ansIndex =0;
                    for(int k=0; k<9; k++){
                        if(k!=i && k!=j){
                            ans[ansIndex++] = h[k];
                        }
                    }
                    found=true;
                    break;
                }
            }
            if(found) break;
        }

        insertionSort(ans);
        for(int i=0; i<7; i++)
            System.out.println(ans[i]);

    }
    
    // 오름차순정렬
    public static void insertionSort(int[] arr){
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<i ; j++){
                if(arr[j] > arr[i]){
                    int cur = arr[i];
                    for(int k=i; k >j; k--){
                        arr[k] = arr[k-1];
                    }
                    arr[j] = cur;
                    break;
                }
            }
        }
    }

}

 

 

시뮬레이션은 문제에서 주어진 상황을 그대로 진행하며 해결하는 기법(요구사항에 알맞은 코드 모델링, 조건을 체계적으로 수행하기 위한 구현력이 필요)

ex) 개미[10158] , 줄세우기[10431]

 

1. [10448] 유레카이론

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

10448번: 유레카 이론

 

문제: 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2   

목표: 자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램

(3개의 삼각수가 모두 달라야 할 필요는 없다.)

상황:  

테스트케이스 개수 입력 첫번째, 테스트케이스 라인별로

 

방법:  모든 삼각수를 구한다

주어진 숫자를 세 개의 삼각수의 합으로 표현할 수 있는지 확인한다.

시간복잡도 : O(K * triangleNumberCount )

import java.util.Scanner;

public class Baekjoon10448 {

    static boolean[] isEurekaNumber = new boolean[1001];

    public static void preprocess(){
        // 1. K보다 작은 삼각수를 모두 구한다.
        int[]triangleNumbers = new int[50];
        int triangleNumberCount =0;
        for(int i=1;  ; i++){
            // 삼각수 공식(가우스의 자연수)
            int triangleNumber = i * (i+1)/2;
            // 1000까지 계산
            if(triangleNumber >= 1000) break;
            // 삼각수를 모두 담는다.
            triangleNumbers[triangleNumberCount++] +=triangleNumber;
        }
        // 2. 구해진 삼각수 세개의 합으로 K를 나타낸 수 있느지 확인하다.
        boolean[] isSumOfTriangleNumber= new boolean[1001];
        for(int i =0; i<triangleNumberCount; i++)
            for(int j=0; j<triangleNumberCount; j++) {
                // 삼각수 두개를 더해서 1000보다 작은 수를 구한다.
                int sum = triangleNumbers[i] + triangleNumbers[j];
                if (sum < 1000) isSumOfTriangleNumber[sum] = true;
            }

        for(int i=1; i<1000; i++) {
            // 1000보다 작은 수 중 삼각수 두개의 합으로 나타낼 수 있는 수를 구한다.
            if (!isSumOfTriangleNumber[i]) continue;
            for (int j = 0; j < triangleNumberCount; j++) {
                // 1000보다 작은 수 중 삼각수 두개의 합으로 나타낼 수 있는 수에 
                // 삼각수 하나를 더해서 1000보다 작은 수를 구한다.
                int sum = i + triangleNumbers[j];
                // 1000보다 작은 수 중 삼각수 세개의 합으로 나타낼 수 있는 수를 구한다.
                if (sum <= 1000) isEurekaNumber[sum] = true;
            }
        }
    }


    public static void main(String[] args) {
        //1. 삼각수를 구한다.
        preprocess();

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int K = sc.nextInt();
            System.out.println(isEurekaNumber[K] ? 1 : 0);
        }
    }
}

 

2. [11005] 진법 변환 2

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

11005번: 진법 변환 2

 

문제: 10진수 N이 주어질 때, 이를 B진법으로 바꿔라( A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35)

목표: 10진수 N이 주어질 때, 이를 B진법으로 바꿔라

상황: 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다.

방법:

 1. N을 B로 나눈 몫을 구한다. B로 나누자
 2. 이 때 가장 마지막 나머지부터 가장 앞자릿값이 된다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baekjoon11005 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N= Integer.parseInt(st.nextToken());
        int B= Integer.parseInt(st.nextToken());

        // 1. N을 B로 나눈 몫을 구한다. B로 나누자
        // 2. 이 때 가장 마지막 나머지부터 가장 앞자릿값이 된다.
        String ans= "";
        while(N >0){
            int D = N % B;
            if(D <10) ans+=D;
            else ans += (char)(D - 10+ 'A');
            N = N/B;
        }

        for(int i=ans.length()-1; i>=0; i--)
            System.out.print(ans.charAt(i));
        System.out.println();
    }
}

 

3. [11068] 회문인 수

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

11068번: 회문인 수

 

문제:  주어진 숫자가 [2, 64] 진법으로 표현했을때 회문이 될수 있는가?

방법: 1. 가능한 모든 진법에 대해 진법을 변환한다.(convertBase)

2. 변환된 수가 회문이 될수 있는지 확인한다.(isPalindrome)

 시간복잡도 O(T*64*logN)

import java.util.Scanner;
public class Baekjoon11068 {

    public static int[] convertBase(int x, int B){
        int len =0, copyX =x;
        while(copyX >0){
            copyX /= B;
            len++;
        }

        int[] digit= new int[len];
        len=0;
        while(x>0){
            digit[len++] = x % B;
            x= x / B;
        }

        return digit;
    }

    public static boolean isPalindrome(int[] digit){
        for(int i=0; i<digit.length/2;i++){
            if(digit[i] != digit[digit.length -i -1])
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
            // 거꾸로 자릿수를 구하는 방법은 길이를 미리 알 수없다.
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int x =sc.nextInt();
            boolean ans=false;
            for(int i=2; i<=64; i++){
                int[] digit = convertBase(x,i);
                if(isPalindrome(digit)){
                    ans = true;
                    break;
                }
            }
            System.out.println(ans ? 1 : 0);
        }

    }
}

4. [3058] 사탕게임

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

3058번: 짝수를 찾아라

 

문제: 색이 다른 사탕이 인접한 두 칸을 골라 사탕을 서로 교환할 때, 같은 색으로 이루어진 가장 긴 연속 부분 행/열의 최댓값

방법:  1. 가능한 모든 쌍의 사탕을 서로 교환한다.

2. 교환한 상태에서 가장 긴 연속 부분 행/열을 차즌다.

3. 교환한 사탕을 원복한다.

시간복잡도: O(N4)

import java.util.Scanner;

public class Baekjoon3085 {

    // 캔디 바꾸기
    public static void swapCandy(char[][] map, int r1, int c1, int r2, int c2) {
        char tmp = map[r1][c1];
        map[r1][c1] = map[r2][c2];
        map[r2][c2] = tmp;
    }


    // 가장 긴 연속 열 (가로)
    public static int findMaxRow(char[][] map) {
        int N = map.length;
        int maxRow = 0;
        for (int r = 0; r < N; r++) {
            int len = 1;
            for (int c = 1; c < N; c++) {
                if (map[r][c] == map[r][c - 1]) len++;
                else {
                    maxRow = Math.max(maxRow, len);
                    len = 1;
                }
            }
            maxRow = Math.max(maxRow, len);
        }
        return maxRow;
    }


    // 가장 긴 연속 행 (세로)
    public static int findMaxColumn(char[][] map) {
        int N = map.length;
        int maxColumn = 0;
        for (int c= 0; c < N; c++) {
            int len = 1;
            for (int r = 1; r < N; r++) {
                if (map[r][c] == map[r - 1][c]) len++;
                else {
                    maxColumn = Math.max(maxColumn, len);
                    len = 1;
                }
            }
            maxColumn = Math.max(maxColumn, len);
        }
        return maxColumn;
    }

    public static void main(String[] args) {
        // 색이 다른 사탕이 인접한 두칸을 골라 사탕을 서로 교환할 때,
        // 같은 색으로 이루어진 가장 긴 연속 부분 행/열의 최댓값

        //  1. 가능한 모든 쌍의 사탕을 서로 교환한다.
        //  2. 교환한 상태에서 가장 긴 연속 부분 행/열을 찾는다.
        //  3. 교환한 사탕을 원복한다.
        // * 교환이 가능한 쌍이 무조건 하나는 있을까?
        // * 교환하지 않은 상태의 답이 더 클 수 있을까?
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[][]map = new char[N][N];
        for(int i=0; i<N; i++){
            map[i] = sc.next().toCharArray();
        }
        int ans=0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j + 1 < N && map[i][j] != map[i][j + 1]) {
                    swapCandy(map, i, j, i, j + 1);
                    ans = Math.max(ans, Math.max(findMaxColumn(map), findMaxRow(map)));
                    swapCandy(map, i, j, i, j + 1);
                }
                if (i + 1 < N && map[i][j] != map[i + 1][j]) {
                    swapCandy(map, i, j, i + 1, j);
                    ans = Math.max(ans, Math.max(findMaxColumn(map), findMaxRow(map)));
                    swapCandy(map, i, j, i + 1, j);
                }

            }
        }
        System.out.println(ans);
    }
}

 

[시뮬레이션 문제]

5. [10250] ACM호텔

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

10250번: ACM 호텔

 

문제: 엘리베이터로부터 가까운 방 먼저, 같다면 아래층부터 배정할때 N번째 손님에게 배정될 방 번호는?

 

import java.util.Scanner;

// ACM호텔
public class Baekjoon10250 {

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);


        // 한번에 계산해보자
        // 한방씩 배치하지 않아도 10명마다 엘리베이터와 한칸씩 멀어진다.
        int T= sc.nextInt();
        // N번째 손님의 호수 :  H로 나눈 몫
        // N번째 손님의 층수 H로나눈 나머지
        // 시간복잡도 0(1)

        while(T-- > 0){
            int H=sc.nextInt();
            int W=sc.nextInt();
            int N=sc.nextInt();
            int distance = (N-1)/ H+1 ; // 엘리베이터와의 거리
            int floor =(N-1)%H +1 ;   // 배정받을 방의 층수
            System.out.printf("%d%02d\n", floor, distance);

        }

    }
}

 

6. [1739] 판화

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

1739번: 도로 정비하기

문제: 로봇 팔의 명령 순서가 주어졌을 때 , 목판위에 패인 조각도의 흔적

 시간복잡도 : O(max(N2승,L))    L :명령어길이

import java.util.Scanner;

// 판화
public class Baekjoon1730 {

    public static void main(String[] args) {
        // 문제: 로봇 팔의 명령 순서가 주어졌을 때, 목판 위에 패인 조각도의 흔적
        // 1. 팔을 명령 순서대로 움직인다.
        // 2. 누적된 흔적을 축력한다.
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String command = sc.hasNext() ? sc.next() : "";

        boolean[][] passVertical = new boolean[N][N];
        boolean[][] passHorizontal = new boolean[N][N];
        int curR = 0, curC = 0;

        for (int i = 0; i < command.length(); i++) {
            char cmd = command.charAt(i);
            if (cmd == 'D') {
                if (curR == N - 1) continue;
                passVertical[curR][curC] = passVertical[curR + 1][curC] = true;
                curR++;
            } else if (cmd == 'U') {
                if (curR == 0) continue;
                passVertical[curR][curC] = passVertical[curR - 1][curC] = true;
                curR--;
            } else if (cmd == 'L') {
                if (curC == 0) continue;
                passHorizontal[curR][curC] = passHorizontal[curR][curC-1] = true;
                curC--;
            } else {
                if (curC == N - 1) continue;
                passHorizontal[curR][curC] = passHorizontal[curR][curC + 1] = true;
                curC++;
            }

        }
        for (int i = 0; i < N; i++) {
            String ans = "";
            for (int j = 0; j < N; j++) {
                if (passVertical[i][j] && passHorizontal[i][j]) ans += "+";
                else if (passVertical[i][j]) ans += "|";
                else if (passHorizontal[i][j]) ans += "-";
                else ans += ".";
            }
            System.out.println(ans);
        }

    }
}

 

 

7. [2840] 행운의 바퀴

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

2840번: 행운의 바퀴

 

문제: 바퀴를 시계방향으로 S칸 돌릴 때마다 화살표가 가리키는 글자가 주어질때 바퀴의 각 칸에 적어놓은 알파벳을 알아내자

 1. 바퀴의 커서 인덱스를 S만큼 움직인다.
 1-0. 커서 인덱스가 배열 범위를 넘어갔다면 조정한다.
 1-1. 도착한 칸이 아직 알아내지 못한 글자라면 기록한다.
 1-2. 도착한 칸의 글자가 적힌 글자와 다르다면 바퀴는 존재하지 않는다.
 1-3. 도착한 칸의 글자가 적힌 글자와 같다면 넘어간다.
 2. 바퀴에 적힌 글자가 모두 다른지 확인한다.
 3. 바퀴에 출력된 글자를 마지막으로 도착한 글자부터 출력한다.

import java.util.Arrays;
import java.util.Scanner;

public class Baekjoon2817 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        char[] wheel = new char[N];
        Arrays.fill(wheel, '?');
        int curIndex = 0;
        while(K-- > 0){
            int step = sc.nextInt();
            char nextAlphabet = sc.next().charAt(0);
            int nextIndex = ((curIndex - step) % N + N) % N;
            if(wheel[nextIndex] == '?') wheel[nextIndex] = nextAlphabet;
            else if(wheel[nextIndex] != nextAlphabet){
                System.out.println("!");
                return ;
            }
            curIndex = nextIndex;
        }

        boolean[] isUsed = new boolean[26];
        for(int i=0; i<N; i++){
            if(wheel[i] == '?') continue;
            if(isUsed[wheel[i] - 'A']) {
                System.out.println("!");
                return ;
            }
            isUsed[wheel[i] - 'A'] = true;
        }

        for(int i=0; i<N;i++)
            System.out.print(wheel[(curIndex +i)%N]);
        System.out.println();

      


    }
}

 

8. [2817] ALPS식 투표

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

2817번: ALPS식 투표

 

import java.util.Scanner;

// ALPS식 투표
public class Baekjoon2817 {

    static class Score{
        Score(int staffIndex,double scr){
            this.staffIndex= staffIndex;
            this.scr = scr;
        }
        int staffIndex;
        double scr;
    }

    public static void sortScoresDescendingOrder(Score[] arr){
       for(int i=0; i<arr.length;i++){
           for(int j =0; j<i ;j++){
                if(arr[i].scr > arr[j].scr){
                     Score temp = arr[i];
                     for(int k =i ; k>j ; k--){
                         arr[k] = arr[k-1];
                     }
                     arr[j] = temp;
                }
           }
       }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        // 참가자들의 수
        int X = sc.nextInt();
        // 스태프의 수
        int N = sc.nextInt();

        // 1. 전체 득표수의 5프로 미만의 스태프를 후보에서 제외한다.
        double validCut = X* 0.05;
        boolean[] validCandidate = new boolean[26];
        int[] staffVote = new int[26];
        int candidateCount =0;
        for(int i=0; i<N; i++){
            // 스태프 이름
            String name =sc.next();
            // 스태프가 받은 칩의 개수
            int vote = sc.nextInt();
            if(vote >= validCut){
                //  A~Z : 65~90
                //  A~Z - 'A' : 0~25
                int index = name.charAt(0) -'A';
                validCandidate[index] = true;
                staffVote[index]= vote;
                candidateCount++;
            }
        }

        // 2. 남은 스태프마다 받은 득표수를 1~14로 나눈 점수를 구한다.
        Score[] scores = new Score[candidateCount * 14];
        int scoreIndex =0;
        for(int i=0; i< 26; i++){
            if(validCandidate[i]) {
                for(int j=1; j<=14; j++){
                    scores[scoreIndex++] = new Score(i, (double)staffVote[i]/j);
                }
            }
        }

        // 3. 전체 점수 집합에서 점수가 큰 1~14번째 스태프에게 칩을 1개씩 지급한다.
        sortScoresDescendingOrder(scores);

        int[] ans = new int[26];
        for(int i=0; i< 14;i++){
            ans[scores[i].staffIndex]++;
        }

        // 4. 스태프 이름에 대해 사전순으로 후보 스태프와 받은 칩의 수를 출력한다.
        for(int i=0;i<26;i++){
            if(validCandidate[i]){
                System.out.println((char)(i+'A') + " " + ans[i]);
            }
        }

    }
}

 

Chapter05 - 정렬

 

1. Arrays.sort

유명한 N2승 정렬 알고리즘

  - Bubble Sort, Selection Sort, insertion Sort

유명한 NlogN 정렬 알고리즘

 -  Quick Sort, Merge Sort, Heap Sort

그 외

 - Counting Sort, Radix Sort, Bucket Sort ...

배열을 정렬하는 sort 함수가 존재한다.

 

Primitive[] sort

-알고리즘 : Dual-Pivot Quick Sort

-평균 시간 복잡도 : O(NlogN)

-최악 시간 복잡도 : O(N2승)

- stable이 보장되지 않음

 

Object[] sort
- 알고리즘 : Tim Sort

- 평균 시간 복잡도 : O(NlogN)

- 최악 시간 복잡도  : O(NlogN)

- stable이 보장됨

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class ArraysSort {

    public static void main(String[] args) throws IOException {
        BufferedReader bwr = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bwr.readLine());
        int[] arr = new int[N];
        for(int i =0; i<N; i++){
            arr[i] = Integer.parseInt(bwr.readLine());
        }

        // Tim Sort 최악의 경우에도( NlogN)
        Arrays.sort(arr);

        BufferedWriter bww = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<N; i++){
            bww.write(arr[i]+"\n");
        }
        bww.flush();

        int [] primitiveArray = new int[]{1,2,3,4,5};
        Arrays.sort(primitiveArray);
        for(int i=primitiveArray.length-1 ; i>=0; i--){
            System.out.println(primitiveArray[i]);
        }

        Integer[] objectArray = new Integer[]{1,2,3,4,5};
        Arrays.sort(objectArray, Collections.reverseOrder());
        for(Integer x : objectArray){
            System.out.println(x);
        }

        Arrays.sort(objectArray, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // return o1 -o2; // 오름차순
                return o2 -o1; // 내림차순
            }
        });

        for(Integer x : objectArray){
            System.out.println(x);
        }

    }
}

 

 

2. [1181] 단어 정렬

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

1181번: 단어 정렬

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

// 단어 정렬
public class Baekjoon1181{


    public static void main(String[] args) {
        // 문제 : N개의 단어에 대해 중복을 제거하고 아래 조건에 맞게 정렬

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] words= new String[N];

        for(int i=0; i<N ; i++){
            words[i] = sc.next();
        }

        // 1. 길이가 짧은 것부터
        // 2. 길이가 같으면 사전 순으로
        Arrays.sort(words, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                if(s1.length() != s2.length()){
                    return s1.length() - s2.length();
                }
                return s1.compareTo(s2);
            }
        });

        // 중복된 단어는 하나만 남기고 제거해야 한다.
        System.out.println(words[0]);
        for(int i =1 ;i < N; i++)
            if(!words[i].equals(words[i-1]))
                System.out.println(words[i]);

    }
}

 

3. [10814] 나이순 정렬

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

10814번: 나이순 정렬

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

// 나이순 정렬
public class Baekjoon10814 {

    public static void main(String[] args) throws IOException {
        // 문제 : N명의 회원의 나이와 이름이 가입한 순서대로 주어질 때, 아래 조건에 맞게 정렬
        Scanner sc = new Scanner(System.in);

        int N= sc.nextInt();
        Member[] members = new Member[N];
        for(int i=0; i<N; i++){
            members[i] = new Member(sc.nextInt(), sc.next(), i);
        }

        // 1. 나이가 작은 회원 먼저
        // 2. 나이가 같으면 먼저 가입한 사람 먼저
        Arrays.sort(members);

        for(Member member : members){
            System.out.println(member.age + " " + member.name);
        }

    }

    static class Member implements Comparable<Member>{
        int age;
        String name;
        int idx;

        public Member(int age, String name, int idx){
            this.age = age;
            this.name = name;
            this.idx = idx;
        }

        // 1. 나이가 작은 회원 먼저
        // 2. 나이가 같으면 먼저 가입한 사람 먼저
        @Override
        public int compareTo(Member o) {
            if(age != o.age) {
                return age - o.age;
            }
            return idx - o.idx;
        }

    }
}

 

4. [7785] 회사에 있는 사람

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

7785번: 회사에 있는 사람

// HashSet => HashTable을 기반으로 한 undordered Collection
// TreeSet
// Binary Search Tree 를 기반으로 한 ordered Collection

TreeSet 

HashSet과 비슷한 구조를 가져서 중복 데이터를 저장하지 않고 저장 순서를 유지하지 않는다는 성질을 가집니다

HashSet과 다른 점은 TreeSet은 이진 탐색 트리(BinarySearchTree) 구조로 되어있습니다

이진 탐색 트리에서 검색능력을 더 향상시킨 레드-블랙-트리로 구현되어 있습니다

시간 복잡도 : O(N * LlogN) L: 사원의 이름 길이

import java.util.*;

// 회사에 있는 사람
public class Baekjoon7785 {

    public static void main(String[] args) {
        // 문제 : 회사 출입기록이 주어질 때, 아직 퇴근하지 못한 사람의 목록(사전 역순)
        Scanner sc = new Scanner(System.in);

        // 시간 복잡도 : O(N * LlogN)  L: 사원의 이름 길이
        int N = sc.nextInt();
        Set<String>set = new TreeSet<>();
        for(int i=0; i<N ; i++){
            String name =sc.next();
            String status = sc.next();
            // 2. 각 사원마다 마지막 기록이 enter인지 확인한다.(사전 역순)
            if(status.equals("enter"))
                set.add(name);
            else set.remove(name);
        }

        // 1. 이름 순서에 따라 출입기록을 차례로 정렬한다.
        String[] orderedName =set.toArray(new String[set.size()]);
        for(int i= orderedName.length -1; i>= 0; i--){
            // 2-1. enter이면 아직 회사에 있다는 뜻이므로 출력한다.
            System.out.println(orderedName[i]);
        }
    }
}

https://crazykim2.tistory.com/583

[JAVA] TreeSet 개념과 사용법 정리

 

5. [1302] 베스트셀러

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

1302번: 베스트셀러

 

HashMap - 해시테이블을 기반으로 한 unordered Collection 

                 - 삽입/삭제/조회 연산 : 0(1), (기대),

                  - null 저장 가능

                  - key의 순서가 보장되지 않음

 

TreeMap - BinarySearchTree 를 기반으로 한 ordered Collection

                - 삽입/삭제/조회 연산: 0(log(size)) 

                - null 저장 불가 

                - key의 순서가 보장됨

 

https://junghn.tistory.com/entry/JAVA-Map-getOrDefault-%EC%9D%B4%EB%9E%80-%EC%82%AC%EC%9A%A9%EB%B2%95-%EB%B0%8F-%EC%98%88%EC%A0%9C

[JAVA] Map - getOrDefault 이란? 사용법 및 예제

매개 변수 : 이 메서드는 두 개의 매개 변수를 허용합니다.

• key : 값을 가져와야 하는 요소의 키입니다.
• defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값입니다.

 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 베스트셀러
public class Baekjoon1302 {


    public static void main(String[] args) {
        // 시간복잡도 : O(L * N2승)
        // 문제 : 판매된 책의 제목들이 주어졌을 때 , 가장 많이 팔린 책은?
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Map<String, Integer>map = new HashMap<>();
        for(int i=0; i<N ; i++){
            String title= sc.next();
            map.put(title, map.getOrDefault(title, 0) + 1);
        }

        String maxTitle ="";
        int maxCount=0;
        for(Map.Entry<String, Integer> title : map.entrySet()){
            String titleName = title.getKey();
            int count = title.getValue();
            if( count > maxCount ||
                    ( count  == maxCount && titleName.compareTo(maxTitle) < 0 )){
                maxTitle = titleName;
                maxCount = count;
            }
        }
        System.out.println(maxTitle);
    }

}

 

 

6. [18870] 좌표 압축

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

18870번: 좌표 압축

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Baekjoon18870 {

    public static void main(String[] args) throws IOException {
        // 문제 : N개의 좌표가 주어질 때 , 각 좌표가 입력된 좌표 중 몇 번째 좌표인지 출력
        // 1. 입력된 좌표를 작은 순으로 정렬한다.
        // 단순 구현 : O(N)
        // 전체 시간복잡도 : O(N의 2승)
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] xs = new int[N][2];
        for(int i=0; i<N; i++){
            xs[i][0] = sc.nextInt();
            xs[i][1] = i;
        }

        Arrays.sort(xs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 오름차순
                return o1[0]- o2[0];
            }
        });


        // 2. 정렬된 좌표를 중복을 제거하며 압축된 인덱스를 기록한다.
        int [] ans= new int[N];
        int idx = 0;
        ans[xs[0][1]] = idx;
        for(int i =1; i<N ; i++){
            if(xs[i][0] != xs[i-1][0]){
                idx++;
            }
            ans[xs[i][1]] = idx;
        }



        // 3. 입력된 좌표에 알맞은 압축 인덱스를 출력한다.
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<N ; i++){
            bw.write(ans[i] + " ");
        }
        bw.write("\n");
        bw.flush();

    }
}

TreeSet 사용

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Baekjoon18870 {

    public static void main(String[] args) throws IOException {
        // 문제 : N개의 좌표가 주어질 때 , 각 좌표가 입력된 좌표 중 몇 번째 좌표인지 출력
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        // 1. 입력된 좌표를 작은 순으로 정렬한다.
        int[] xs = new int[N];
        Set<Integer>set = new TreeSet<>();
        for(int i=0; i<N ; i++){
            xs[i] = sc.nextInt();
            set.add(xs[i]);
        }

        // 2. 정렬된 좌표를 중복을 제거하며 압축된 인덱스를 기록한다.
        Map<Integer, Integer> sortedIndex= new HashMap<>();
        int idx=0;
        for(int x : set){
            sortedIndex.put(x, idx++);
        }

        // 3. 입력된 좌표에 알맞은 압축 인덱스를 출력한다.
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<N ; i++){
           bw.write(sortedIndex.get(xs[i]) + " ");
        }
        bw.write("\n");
        bw.flush();

    }
}

 

7. [2910] 빈도 정렬

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

2910번: 빈도 정렬

LinkedHashMap : 삽입 순서를 유지하는 HashMap    => 시간복잡도: O(NlogN)

LinkedHashMap 을 사용하면 put한 순서대로 key 가 유지되고 Integer[] 로 Tim Sort를 사용하면 stable하기 때문에

frequency 가 같다면 먼저 put된 key가 앞에 위치한다.

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

// 빈도정렬
public class Baekjoon2910 {


    static class  Message{
        int num;
        int index;
        Message(int num, int index){
            this.num = num;
            this.index = index;
        }

    }
    static  class Frequency{
        int num;
        int count;
        int firstIndex;
        public Frequency(int num, int count, int firstIndex){
            this.num = num;
            this.count = count;
            this.firstIndex = firstIndex;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();

        Message [] messages = new Message[N];
        for(int i=0; i<N ; i++){
            messages[i] = new Message(sc.nextInt(), i);
        }

        Arrays.sort(messages, new Comparator<Message>() {
            @Override
            public int compare(Message o1, Message o2) {
                // 오름차순
                return o1.num- o2.num;
            }
        });

        Frequency[] frequencies = new Frequency[N];
        int frequencyIdx = 0;
        frequencies[frequencyIdx] = new Frequency(messages[0].num, 1, messages[0].index);

        for(int i=1; i<N ; i++){
            if(messages[i].num != messages[i -1].num){
                frequencies[++frequencyIdx] = new Frequency(messages[i].num, 0, messages[i].index);
            }
            frequencies[frequencyIdx].count++;
        }

        Arrays.sort(frequencies, 0, frequencyIdx + 1, new Comparator<Frequency>() {
            @Override
            public int compare(Frequency o1, Frequency o2) {
                if(o1.count == o2.count){
                    return o1.firstIndex - o2.firstIndex;
                }
                return o2.count - o1.count;
            }
        });
        // 1. 더 많이 등장한 숫자 먼저


        // 2. 등장 횟수가 같다면 입력으로 먼저 들어온 것이 먼저
        for(int i =0; i<= frequencyIdx ; i++){
            while(frequencies[i].count-- > 0){
                System.out.print(frequencies[i].num + " ");
            }
            System.out.println();
        }
            
    }
}