[BOJ] 정렬 단계2

today's alogrithm

[BOJ] 정렬 단계2 - JAVA

UR'im 2021. 2. 2. 23:43

정렬 단계

수 정렬하기3
통계학
소트인사이트
좌표 정렬하기
좌표 정렬하기2

▷ 수 정렬하기 3

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

개인적으로 수정렬하기 3번의 경우는 카운팅 소트를 사용하여 정렬해야 했기 때문에 어려웠다.

아래의 코드는 맨 처음 틀렸던 코드이다.

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        int MAX_NUM = 10000;
        int MAX_SIZE = 10000000;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int testCase = Integer.parseInt(br.readLine().trim());
        
        int[] array = new int[MAX_SIZE+1];
        int[] counting = new int[MAX_NUM+1];
        int[] result = new int[MAX_SIZE+1];
        
        for(int i = 0; i<testCase; i++){
            array[i] = Integer.parseInt(br.readLine().trim());
        }
        
        for(int i : array){
            counting[i]++;
        }
        
        for(int i = 1; i<= MAX_NUM; i++ ){
            counting[i] +=counting[i-1];
        }
        
        for(int i = array.length-1; i>0; i--){
            counting[array[i]]--;
            result[counting[array[i]]] = array[i];
        }
        
        for(int i = 1; i<result.length; i++)
            bw.write(result[i]+'\n');
        
        bw.flush();
        bw.close();
        br.close();
    }
}

MAX_NUM은 들어올 수 있는 최대 숫자이고, MAX_SIZE는 입력 받을 수 있는 최대 수 이다.

그러나 저렇게 MAX_SIZE로 사이즈를 정해두니 쓸 때 없이 for문의 길이가 길어지기 때문에 틀린 방법이였다.

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        int MAX_NUM = 10000;
        int MAX_SIZE = 10000000;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int testCase = Integer.parseInt(br.readLine().trim());
        
        int[] array = new int[testCase];
        int[] counting = new int[MAX_NUM+1];
        int[] result = new int[MAX_SIZE+1];
        
        for(int i = 0; i<testCase; i++){
            array[i] = Integer.parseInt(br.readLine().trim());
        }
        
        for(int i : array){
            counting[i]++;
        }
        
        for(int i = 1; i<= MAX_NUM; i++ ){
            counting[i] +=counting[i-1];
        }
        
        for(int i = array.length-1; i>=0; i--){
            counting[array[i]]--;
            result[counting[array[i]]] = array[i];
        }
        
        for(int i = 0; i<result.length; i++){
        	if(result[i] == 0) break;
            bw.write(result[i]+"\n");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}

입력 받는 배열은 테스트 케이스만큼으로 설정 하니 문제 없이 코드가 돌아갔다.

나머지 코트는 큰 차이가 없다. 결과 배열에 정렬 값을 담을 때 for loop의 범위는 0까지 포함이다.

counting sort는 갯수를 센 후 그것 만큼 출력하는것이 앞의 값을 축적하여 한다.

배열의 시작을 1이라 가정했을 때,

▼ 아래의 테이블이 첫번째 for문을 통해 얻은 data 배열이라고 하면

▼아래의 테이블은 두번째 for문을 통해 각 값을 counting하여 배열에 넣어준다. 0은 0개이므로 0으로 채우고 1은 2개이므로 2를 넣어준다.

▼아래 테이블은 세번째 for loop으로 배열의 앞의 값을 축적하여 저장한다.

▼ 마지막으로 배열에 끝에서부터 입력하는데, 배열의 값인 4는 data[3]의 i가 3인 숫자가 들어갈 자리이다. 숫자가 들어가면 counting 값을 -1해준다. 그렇게 되면 data[3]의 값이 4에서 3으로 떨어진다. 그리고 data[2]의 i가 2인 숫자가 결과 배열의 3번에는 2가 들어간다.

이런식으로 정리하면 결과적으로

1 1 2 3순서로 배열 된다.

▷ 통계학

www.acmicpc.net/problem/2108

2108번: 통계학

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

www.acmicpc.net

통계학 문제는 지금까지 풀었던 문제중 가장 시행착오가 많았던 문제였다.

정말 풀다가 울고싶을 지경이였다. 거의 다와서 정렬했던 코드를 지웠던게 문제가 되어 틀렸던것이었다...

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Main m = new Main();
        
        List<Integer> arr = new ArrayList<>();
        int n_size = Integer.parseInt(br.readLine().trim());

        for(int i = 0; i<n_size; i++){
            arr.add(Integer.parseInt(br.readLine().trim()));
        }
        Collections.sort(arr);
        
        int min = Collections.min(arr);
        int max = Collections.max(arr);
        
        int avg = m.calcAverage(arr);
        int median = arr.get(arr.size()/2);
        int mode = m.findmode(arr);
        int range = m.findRange(max, min);
        
        bw.write(avg+"\n"+median+"\n"+mode+"\n"+range+"\n");
        
        bw.flush();
        bw.close();
        br.close();
    }
    public int calcAverage(List<Integer> arr){
        int sum = 0;
        for(int i : arr){
            sum +=i;
        }
        return sum/arr.size();
    }
    
    public int findmode(List<Integer> arr){
        Map<Integer, Integer> hp = new HashMap<Integer, Integer>();
        Map.Entry<Integer, Integer> maxEntry = null;
        for(int i : arr){
            if(hp.containsKey(i)){
                hp.put(i,hp.get(i)+1);
            }else{
                hp.put(i, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : hp.entrySet()) {
            if (maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0) {
	            maxEntry = entry; //compareTo를 이용해 제일 높은 map값이 maxEntry에 저장됨
            }
        }
        return maxEntry.getKey();
    }
    
    public int findRange(int max, int min){
        int range;
        if(max > 0 && min > 0 || max < 0 && min < 0){
            range = Math.abs(max - min);
        }else{
            range = Math.abs(max) + Math.abs(min);
        }
        return range;
    }
}

처음 작성했던 코드는 길이가 길기도 하고, 문제 이해를 잘못해서 틀린게 많았다. 예를 들어 산술평균값을 구할때 반올림 해야되는걸 하지 않았다던가, 중앙값을 구할 때 중복값을 제외하고 구했는데 그렇게 하면 안되는거였다,,,,

특히 최빈값 구하는 부분이 스트레스였다. 앞서 counting sort로 하려고 했는데 값이 음수값이 들어올 수 있는 것을 까먹고 있었다.

그래서 counting sort가 아닌 다른 방법을 써야하는데 하고 고민하다 그냥 hashmap을 사용했다...

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Main m = new Main();
        
        List<Integer> arr = new ArrayList<>();
        int n_size = Integer.parseInt(br.readLine().trim());
        int sum = 0;
        for(int i = 0; i<n_size; i++){
            arr.add(Integer.parseInt(br.readLine().trim()));
            sum += arr.get(i);
        }
        
        Collections.sort(arr);
        
        int min = Collections.min(arr);
        int max = Collections.max(arr);
        
        int avg = (int)Math.round((sum*1.0)/n_size);
        int median = arr.get(((n_size+1)/2)-1);
        int mode = m.findmode(arr);
        int range = Math.abs(Collections.max(arr) - Collections.min(arr));
        
        bw.write(avg+"\n"+median+"\n"+mode+"\n"+range+"\n");
        
        bw.flush();
        bw.close();
        br.close();
    }
    
    public int findmode(List<Integer> arr){
        Map<Integer, Integer> hp = new HashMap<Integer, Integer>();
	    List<Integer> maxKey = new ArrayList<>();
        int maxValue = -4001; int mKey = 0;
        
        for(int i : arr){
            if(hp.containsKey(i)){
                hp.put(i,hp.get(i)+1);
            }else{
                hp.put(i, 1);
            }
        }
        
        for(Integer key: hp.keySet()){ 
            if(hp.get(key) == maxValue){
            	maxKey.add(key);
            }
            if(hp.get(key) > maxValue){ 
                maxKey.clear();
                maxValue = hp.get(key); 
                mKey = key; 
                maxKey.add(key);
            }
        }
        
        Collections.sort(maxKey);
        
        if(maxKey.size() > 1) return maxKey.get(1);
        else return maxKey.get(0);
    }
}

최종 결과코드이다. 아주 약간 짧아진 정도지만 결국 최빈값 구하는 부분은 줄일 수가 없었다... 최빈값도 그냥 구하는게 아니라 수가 동일하면 두번째로 작은 값을 찾으라고 해서 화가나서 그냥 꺼버리기도 했다,,, (늦은 시간이라 그냥 자야지 싶었다,,,)

멘붕의 두 문제를 풀고나니 아래의 3 문제는 매우 쉽게 느껴졌다.

▷ 소트인사이트

www.acmicpc.net/problem/1427

1427번: 소트인사이드

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

소트 인사이드는 문자로 받은 숫자들을 정렬하는 문제였는데, 난 항상 뭔갈 까먹고 실행시켜서 컴파일 에러 뜬것 말고는 한번에 맞췄다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String N = br.readLine().trim();
        String[] splitN = N.split("");
        Arrays.sort(splitN, Collections.reverseOrder());
        for(String i : splitN){
            bw.write(i);
        }
        bw.flush();
        bw.close();
        br.close();
        
    }
}

코드도 별로 길지 않고,,, 쉽게 끝낼 수 있는 문제였다. 다른 사람들도 그랬는지 정답률이 60%가 넘어간다,,, 통계학과 수정렬은 20% 초반이었는데 말이다,,,,

역시 다들 비슷비슷하구나 싶었다,,

▷ 좌표 정렬하기

www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

www.acmicpc.net

좌표 정렬하기의 경우에도 hashmap을 사용했다.

아래의 코드는 처음에 틀린 코드이다. 출력 값을 볼 수 없어서 다른 웹으로 자바 코드를 돌리는 사이트를 이용해서 봤더니 x값이 정렬이 안되있었다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        Map<Integer,ArrayList<Integer>> hp = new HashMap<Integer,ArrayList<Integer>>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int testCase = Integer.parseInt(br.readLine().trim());
        
        for(int i = 0; i<testCase; i++){
            ArrayList<Integer> arr ;
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int x =Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if(hp.containsKey(x)){
                arr = hp.get(x);
            }else{
                arr = new ArrayList<>();
            }
            arr.add(y);
            Collections.sort(arr);
            hp.put(x, arr);
        }
        
        for(Integer key : hp.keySet()){
            for(int i : hp.get(key)){
                bw.write(key+" "+i);
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

▼ 그래서 x값 (key) 값을 정렬하여 키 값에 해당되는 y값 배열을 가져와 출력했다.

Object[] mapKeys = hp.keySet().toArray();
Arrays.sort(mapKeys);
        
for(Object key : mapKeys){
   for(int i : hp.get((int)key)){
       bw.write(key+" "+i+"\n");
   }
}

아래는 맞은 코드이다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        Map<Integer,ArrayList<Integer>> hp = new HashMap<Integer,ArrayList<Integer>>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int testCase = Integer.parseInt(br.readLine().trim());
        
        for(int i = 0; i<testCase; i++){
            ArrayList<Integer> arr ;
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int x =Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if(hp.containsKey(x)){
                arr = hp.get(x);
            }else{
                arr = new ArrayList<>();
            }
            arr.add(y);
            Collections.sort(arr);
            hp.put(x, arr);
        }
        
        Object[] mapKeys = hp.keySet().toArray();
        Arrays.sort(mapKeys);
        
        for(Object key : mapKeys){
            for(int i : hp.get((int)key)){
                bw.write(key+" "+i+"\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

▷ 좌표 정렬하기 2

www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

www.acmicpc.net

이번 문제는 위의 문제와 반대로 y값을 기준으로 정렬하고 같을 때는 x값을 오름차순으로 정렬하는 방법이다.

위의 코드에서 x,y값의 위치만 바꿔주면 된다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        Map<Integer,ArrayList<Integer>> hp = new HashMap<Integer,ArrayList<Integer>>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int testCase = Integer.parseInt(br.readLine().trim());
        
        for(int i = 0; i<testCase; i++){
            ArrayList<Integer> arr ;
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int x =Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if(hp.containsKey(y)){
                arr = hp.get(y);
            }else{
                arr = new ArrayList<>();
            }
            arr.add(x);
            Collections.sort(arr);
            hp.put(y, arr);
        }
        
        Object[] mapKeys = hp.keySet().toArray();
        Arrays.sort(mapKeys);
        
        for(Object key : mapKeys){
            for(int i : hp.get((int)key)){
                bw.write(i+" "+key+"\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

오늘도 이렇게 코딩 공부를 마무리 한다.

다음에는 인프런 알고리즘 강의 게시글로 찾아오겠담,

develop-recode.tistory.com/19

[BOJ] 정렬 단계 - JAVA

정렬 단계 수 정렬하기 수 정렬하기 2 ▷ 수 정렬하기 www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이..

develop-recode.tistory.com

저작자표시 비영리 변경금지 (새창열림)

'today's alogrithm' 카테고리의 다른 글

[프로그래머스] SQL 고득점 Kit - oracle sql (0)	2021.02.04
[BOJ] 정렬 단계3 - JAVA (0)	2021.02.03
[BOJ] 정렬 단계 - JAVA (0)	2021.01.31
[프로그래머스] SQL고득점 Kit - oracle sql (0)	2021.01.26
[BOJ] 재귀 단계 - JAVA (0)	2021.01.24

현재글[BOJ] 정렬 단계2 - JAVA

개발'새발 개발일기

안녕하세요. 개발새발 코드 짜는 개발자입니다. 나아중에는 꼭 클린코드를 짜는 개발자가 되기위해 노력하려고 합니다.

뉴비톤, 프로그래머스, 취준일기, 공부, 오늘의기록, java, Vue.js, 우물128, boj, 정렬, 알고리즘공부, 백준, 코딩, 자바, 알고리즘 공부, 백준알고리즘, 코딩공부, 스터디, 알고리즘, 코딩테스트,

Today :
Yesterday :

개발'새발 개발일기