[백준] 1431 시리얼 번호 - 정렬(Sorting) JAVA

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

코드설명

정렬 문제입니다.

 

문제에서 어떻게 정렬을 할까 고민했습니다.

1. 첫번쨰 방법은 Comparator<String> 를 활용한 방식입니다.

 

2. 두번쨰 방법은 Comaprable<Node>를 활용한 방식입니다.

저는 주로 객체를 생성하여 하는 방식으로 진행하므로, 두번쨰 방법을 선호합니다.

 

또, 문제에서 주어진 조건을 모두 직접 구현해도 되지만, Integer.compare(A, B) : A, B를 오름차순으로 정렬.

String,compareTo(String2) : 오름차순으로 정렬.

을 통해 오름차순으로 손쉽게 정렬할 수 있습니다.

 

만약, 내림차순으로 정렬하고 싶다면, 매개변수의 순서를 바꿔주면 해결됩니다.

이런 함수를 적용해서 코드작성시간을 줄이는 것이 좋습니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, T, M; 
    public static int answer = 0;
    public static ArrayList<Node> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String a = st.nextToken();
			arr.add(new Node(a));
		}
		Collections.sort(arr);
		for(int i=0;i<N;i++) {
			System.out.println(arr.get(i).str);
		}
	}
    
    
    private static class Node implements Comparable<Node>{
    	String str;
    	
    	public Node(String str) {
    		this.str = str;
    	}
    	
    	@Override
    	public int compareTo(Node other) {
    		//A와 B의 길이가 다르면, 짧은 것이 먼저온다.
			if(this.str.length() > other.str.length()) {
				return 1; 
			} 
    		//만약, 서로의 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은합을 가지는 것이 먼저온다.(숫자인것만 더한다.)
			else if(this.str.length() == other.str.length()) {
				int ASum = getSum(this.str);
				int BSum = getSum(other.str);
				
				if(ASum > BSum) {
					return 1;
				}
				//만약, 1, 2 번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다.
				//숫자가 알파벳보다 사전순으로 작다.    				
				else if(ASum == BSum) {
					return this.str.compareTo(other.str);
				}else if(ASum < BSum) {
					return -1;
				}
			}else if(this.str.length() < other.str.length()) {
				return -1;
			}
    		
    		return 0;
    	}
    	
    	private int getSum(String a) {
    		int sum = 0;
    		for(int i=0; i<a.length();i++) {
    			if(a.charAt(i) >= '0' && a.charAt(i) <='9') {
    				sum += a.charAt(i) - '0';
    			}
    		}
    		return sum;
    	}
    }
    
}

 

Integer.compare와 str.compareTo(str2) 를 통해서 더 깔끔한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, T, M; 
    public static int answer = 0;
    public static ArrayList<Node> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String a = st.nextToken();
			arr.add(new Node(a));
		}
		Collections.sort(arr);
		for(int i=0;i<N;i++) {
			System.out.println(arr.get(i).str);
		}
	}
    
    
    private static class Node implements Comparable<Node>{
    	String str;
    	
    	public Node(String str) {
    		this.str = str;
    	}
    	
    	@Override
    	public int compareTo(Node other) {
    		//길이에 따른 오름차순 정렬합니다.
    		if(this.str.length() != other.str.length())
    			return Integer.compare(this.str.length(), other.str.length());
    		
    		int ASum = getSum(this.str);
			int BSum = getSum(other.str);
			if(ASum != BSum)
				return Integer.compare(ASum, BSum);
    		
    		return this.str.compareTo(other.str);
    	}
    	
    	private int getSum(String a) {
    		int sum = 0;
    		for(int i=0; i<a.length();i++) {
    			if(a.charAt(i) >= '0' && a.charAt(i) <='9') {
    				sum += a.charAt(i) - '0';
    			}
    		}
    		return sum;
    	}
    }
    
}

 

Comparator<String>을 활용하여 굳이 Node객체를 생성안합니다.

package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    public static int N;
    public static ArrayList<String> arr = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            arr.add(a);
        }
 
        Collections.sort(arr, new CustomComparator());
 
        for(int i = 0; i < N; i++) {
            System.out.println(arr.get(i));
        }
    }
    
    private static class CustomComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            // 길이에 따른 오름차순 정렬
            if(a.length() != b.length())
                return Integer.compare(a.length(), b.length());
            
            // 숫자 합 비교
            int sumA = getSum(a);
            int sumB = getSum(b);
            if(sumA != sumB)
                return Integer.compare(sumA, sumB);
            
            // 사전순 비교
            return a.compareTo(b);
        }
        
        private int getSum(String s) {
            int sum = 0;
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    sum += s.charAt(i) - '0';
                }
            }
            return sum;
        }
    }
}

 

Comparator와 익명클래스를 함꼐 구현한다면,

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    public static int N;
    public static ArrayList<String> arr = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            arr.add(a);
        }
 
        Collections.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                // 길이에 따른 오름차순 정렬
                if(a.length() != b.length())
                    return Integer.compare(a.length(), b.length());
                
                // 숫자 합 비교
                int sumA = getSum(a);
                int sumB = getSum(b);
                if(sumA != sumB)
                    return Integer.compare(sumA, sumB);
                
                // 사전순 비교
                return a.compareTo(b);
            }
            
            private int getSum(String s) {
                int sum = 0;
                for(int i = 0; i < s.length(); i++) {
                    if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                        sum += s.charAt(i) - '0';
                    }
                }
                return sum;
            }
        });
 
        for(int i = 0; i < N; i++) {
            System.out.println(arr.get(i));
        }
    }
}

만약 사전순 정렬을 직접 구현하고싶다면, 아래와 같이 구현할 수 있습니다.

private int customCompare(String a, String b) {
    int len = Math.min(a.length(), b.length());
    for (int i = 0; i < len; i++) {
        char charA = a.charAt(i);
        char charB = b.charAt(i);
        if (charA != charB) {
            // 숫자가 알파벳보다 사전순으로 작음
            if (Character.isDigit(charA) && !Character.isDigit(charB)) {
                return -1;
            } else if (!Character.isDigit(charA) && Character.isDigit(charB)) {
                return 1;
            } else {
                return Character.compare(charA, charB);
            }
        }
    }
    // 여기까지 왔다면 모든 문자가 같다는 의미이므로 0을 반환
    return 0;
}