[백준] 단계별로 풀어보기 > 정렬 (java)

+) 풀이 코드

https://github.com/jung0115/CodingTestPractice.git

GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.

 

+) 백준에 Java 코드를 제출할 때는 class명을 Main으로 해주어야 오류가 발생하지 않는다.

 

2750번 - 2022.01.14.금

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int N;
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        int[] num = new int[N];
        for(int i = 0; i < N; i++) {
            num[i] = scan.nextInt();
        }
        scan.close();

        for(int i = 0; i < N-1; i++) {
            int min = i;
            for(int j = i+1; j < N; j++)
                if(num[j] < num[min]) min = j;
            
            if(min != i){
                int tmp = num[min];
                num[min] = num[i];
                num[i] = tmp;
            }
            System.out.println(num[i]);
        }
        System.out.println(num[N-1]);
    }
}

 

2751번 - 2022.01.17.월 (Time Limited)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
    static int[] num;
    public static void main(String[] args) throws IOException {
        int N;
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        num = new int[N];
        for(int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(bf.readLine());
        }

        quickSort(0, N-1);

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++)
            printSet.append(num[i] + "\n");
        System.out.print(printSet);
    }
    static int partition(int start, int end) {
        int pivot, left, right;
        boolean done;
        pivot = num[start];
        left = start+1;
        right = end;
        done = false;
        while(!done) {
            while(left <= right && num[left] <= pivot) left++;
            while(left <= right && num[right] >= pivot) right--;

            if(right < left) done = true;
            else {
                int tmp = num[left];
                num[left] = num[right];
                num[right] = tmp;
            }
        }
        int tmp = num[start];
        num[start] = num[right];
        num[right] = tmp;

        return right;
    }
    static void quickSort(int start, int end) {
        if(start < end) {
            int pivot = partition(start, end);
            quickSort(start, pivot-1);
            quickSort(pivot+1, end);
        }
    }
}

입출력에서 시간을 줄여봐도 시간초과가 걸리고, Quick sort를 이용해도 시간초과가 됐다. 퀵 정렬을 사용했을 경우 최악의 시간복잡도가 O(n^2)가 나올 수 있는데, 입력 데이터 중에 이 최악의 경우를 나오게 유도하는 값이 있다고 한다. 그래서 평균적인, 최악의 시간 복잡도도 빠른 정렬 방법을 사용해야 한다.

 

2751번 - 2022.01.19.수 (해결)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        ArrayList<Integer> num = new ArrayList<Integer>();
        for(int i = 0; i < N; i++)
            num.add(i, Integer.parseInt(bf.readLine()));

        Collections.sort(num); //Timsort

        StringBuilder printSet = new StringBuilder();
        for(int set : num)
            printSet.append(set).append("\n");
        System.out.print(printSet);
    }
}

입출력에 BufferedReader, StringBuilder 사용하고 정렬은 Timsort 방법 사용. Timsort 정렬 알고리즘 정확히 이해하고 직접 코드 작성해볼 필요 있음.

 

10989번 - 2022.01.19.수

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] nums = new int[N];
        for(int i = 0; i < N; i++)
            nums[i] = Integer.parseInt(bf.readLine());
        
        int[] count = new int[10001];
        int max = 0;
        //기본적으로 java는 int 배열이 0으로 초기화 됨.
        for(int n : nums) {
            count[n]++;
            if(n > max) max = n;
        }
        for(int i = 1; i <= max; i++)
            count[i] += count[i-1];
        
        int[] setNums = new int[N];
        for(int i = N-1; i >= 0; i--) {
            int n = nums[i];
            count[n]--;
            setNums[count[n]] = n;
        }
        
        StringBuilder printSet = new StringBuilder();
        for(int set : setNums)
            printSet.append(set).append("\n");
        System.out.print(printSet);
    }
}

Counting sort 방식 이용

 

2108번 - 2022.01.20.목

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        ArrayList<Integer> nums = new ArrayList<Integer>();
        for(int i = 0; i < N; i++)
            nums.add(i, Integer.parseInt(bf.readLine()));

        Collections.sort(nums); //Timsort
        
        double sum = 0;
        int[][] cnt = new int[2][2];
        boolean check = true;
        
        for(int n : nums) {
            sum += n;
            if(cnt[1][1] == 0 || cnt[1][0] == n) {
                cnt[1][0] = n;
                cnt[1][1]++;
            }
            else {
                if(cnt[0][1] < cnt[1][1]) {
                    check = true;
                    cnt[0][0] = cnt[1][0];
                    cnt[0][1] = cnt[1][1];
                }
                else if(cnt[0][1] == cnt[1][1] && check) {
                    check = false;
                    cnt[0][0] = cnt[1][0];
                    cnt[0][1] = cnt[1][1];
                }
                
                cnt[1][0] = n;
                cnt[1][1] = 1;
            }
        }
        if(cnt[0][1] < cnt[1][1] || (cnt[0][1] == cnt[1][1] && check)) {
            cnt[0][0] = cnt[1][0];
            cnt[0][1] = cnt[1][1];
        }

        StringBuilder printSet = new StringBuilder();

        printSet.append(Math.round(sum/N)).append("\n"); //산술평균
        printSet.append(nums.get(N/2)).append("\n"); //중앙값
        printSet.append(cnt[0][0]).append("\n"); //최빈값
        printSet.append(nums.get(N-1) - nums.get(0)); //범위

        System.out.print(printSet);
    }
}

 

1427번 - 2022.01.20.목

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        ArrayList<Integer> nums = new ArrayList<Integer>();
        int len = 0;
        for(int i = 0; N > 0; i++) {
            nums.add(i, N%10);
            N /= 10;
            len++;
        }

        Collections.sort(nums); //Timsort

        StringBuilder printSet = new StringBuilder();
        for(int i = len-1; i >= 0; i--)
            printSet.append(nums.get(i));

        System.out.print(printSet);
    }
}

 

11650번 - 2022.01.20.목 (Time Limited)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[][] dots = new int[N][2];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            dots[i][0] = Integer.parseInt(st.nextToken());
            dots[i][1] = Integer.parseInt(st.nextToken());
        }

        int[] set = new int[N];
        for(int i = 0; i < N; i++) {
            int cnt = 0;
            for(int j = 0; j < N; j++) { //dots[i]보다 앞에 위치하는 좌표의 개수 count
                if(dots[i][0] > dots[j][0] || (dots[i][0] == dots[j][0] && dots[i][1] > dots[j][1])) cnt++;
            }
            set[cnt] = i;
        }

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++)
            printSet.append(dots[set[i]][0]).append(" ").append(dots[set[i]][1]).append("\n");
        System.out.println(printSet);
    }
}

좌표값이 저장된 배열을 정렬하지 않고 각 좌표의 앞에 위치하는 좌표의 개수를 세어 몇 번째에 올지 파악하는 형태로 코드를 작성했다. 답은 제대로 나오지만 시간초과가 걸리고 말았다... 시간을 단축하는 방법을 생각해봤지만 해당 방법으로는 더이상 단축을 할 수 없을 것 같아 새로운 방법을 찾아보았다.

 

11650번 - 2022.01.20.목 (해결)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[][] dots = new int[N][2];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            dots[i][0] = Integer.parseInt(st.nextToken());
            dots[i][1] = Integer.parseInt(st.nextToken());
        }

        //람다식(익명함수) 이용
        Arrays.sort(dots, (dot1, dot2) -> {
            if(dot1[0] == dot2[0]) //x좌표 값이 같은 경우 y좌표로 비교
                return dot1[1] - dot2[1];
            else //다른 경우 x좌표로 비교
                return dot1[0] - dot2[0];
        });

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++)
            printSet.append(dots[i][0]).append(" ").append(dots[i][1]).append("\n");
        System.out.println(printSet);
    }
}

Array.sort() 메소드를 이용하여 시간초과를 해결하였다. 람다식을 적절히 사용해서 2차원 배열을 정렬할 수 있다.

 

11651번 - 2022.01.21.금

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[][] dots = new int[N][2];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            dots[i][0] = Integer.parseInt(st.nextToken());
            dots[i][1] = Integer.parseInt(st.nextToken());
        }

        //람다식(익명함수) 이용
        Arrays.sort(dots, (dot1, dot2) -> {
            if(dot1[1] == dot2[1]) //y좌표 값이 같은 경우 x좌표로 비교
                return dot1[0] - dot2[0];
            else //다른 경우 y5좌표로 비교
                return dot1[1] - dot2[1];
        });

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++)
            printSet.append(dots[i][0]).append(" ").append(dots[i][1]).append("\n");
        System.out.println(printSet);
    }
}

11650번 푼 방식에서 정렬 기준을 y로만 바꿔주었다.

 

1181번 - 2022.01.21.금

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        String[] words = new String[N];
        for(int i = 0; i < N; i++) {
            words[i] = bf.readLine();
        }

        //람다식(익명함수) 이용
        Arrays.sort(words, (word1, word2) -> {
            int len1, len2;
            len1 = word1.length();
            len2 = word2.length();
            if(len1 == len2) //단어의 길이가 같은 경우 사전순으로
                return checkDic(word1, word2, len1);
            else //다른 경우 단어의 길이가 짧은 순으로
                return len1 - len2;
        });

        StringBuilder printSet = new StringBuilder();
        String checkSame = "";
        for(int i = 0; i < N; i++) {
            if(!words[i].equals(checkSame))
                printSet.append(words[i]).append("\n");
            checkSame = words[i];
        }
        System.out.println(printSet);
    }
    static int checkDic(String word1, String word2, int len) {
        char[] word1Char, word2Char;
        word1Char = word1.toCharArray();
        word2Char = word2.toCharArray();
        for(int i = 0; i < len; i++) {
            if(word1Char[i] < word2Char[i]) return -1;
            else if(word1Char[i] > word2Char[i]) return 1;
        }
        return -1;
    }
}

 

10814번 - 2022.01.25.화

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        String[][] people = new String[N][2];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            people[i][0] = st.nextToken();
            people[i][1] = st.nextToken();
        }

        Arrays.sort(people, (person1, person2) -> {
            int age1, age2;
            age1 = Integer.parseInt(person1[0]);
            age2 = Integer.parseInt(person2[0]);
            if(age1 == age2)
                return 0;
            else
                return age1 - age2;
        });

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++)
            printSet.append(people[i][0]).append(" ").append(people[i][1]).append("\n");
        System.out.println(printSet);
    }
}

 

18870번 - 2022.01.25.화(Time Limited)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        ArrayList<Integer> Xdots = new ArrayList<Integer>();
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++)
            Xdots.add(i, Integer.parseInt(st.nextToken()));
        
        HashSet<Integer> hashSet = new HashSet<Integer>(Xdots); //HashSet 이용하여 중복 값 삭제

        //좌표 압축
        int[] resultXdots = new int[N];
        for(int i = 0; i < N; i++) {
            int checkXdot = Xdots.get(i);
            for(int Xdot : hashSet)
                if(Xdot < checkXdot) resultXdots[i]++;
        }

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++)
            printSet.append(resultXdots[i]).append(" ");
        System.out.println(printSet);
    }
}

HashSet을 이용하여 입력 좌표들 중 중복값을 삭제하고, 자신보다 작은 수를 세는 형태로 계산을 했는데, 답은 나오지만 시간초과가 걸렸다.

 

18870번 - 2022.01.25.화(해결)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        ArrayList<Integer> Xdots = new ArrayList<Integer>();
        ArrayList<Integer> copys = new ArrayList<Integer>();
        for(int i = 0; i < N; i++) {
            Xdots.add(i, Integer.parseInt(st.nextToken()));
            copys.add(Xdots.get(i));
        }
    
        Collections.sort(copys); //Timsort
        
        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();
        int rank = 0;
        for(int copy : copys) {
            if(!rankingMap.containsKey(copy)){
                rankingMap.put(copy, rank);
                rank++;
            }
        }

        StringBuilder printSet = new StringBuilder();
        for(int Xdot : Xdots)
            printSet.append(rankingMap.get(Xdot)).append(" ");
        System.out.println(printSet);
    }
}

도처히 방법이 생각나질 않아서 또 검색 찬스... HashMap의 key 값을 이용하는 방식으로 했더니 시간 초과가 발생하지 않고 잘 동작했다.