class2 - 1181번 단어 정렬 (자바)

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

 

Array.sort(배열)

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html

배열 오름차순 정렬 함수

Arrays.sort(배열,Comparator.reverseOrder()); // 내림차순

 

<사용자 정의 정렬>

Integer[] intArr = new Integer[] {1,3,2,5,4};
Arrays.sort(intArr,new Comparator<Integer>() {
	@Override
	public int compare(Integer a, Integer b) { // a는 앞의 수 b는 뒤의 수
		System.out.println(a.compareTo(b));
        return a.compareTo(b); // 오름차순
        //return b.compareTo(a); // 내림차순
    }
});

 

a.compareTo(b)

a == b :  return 0

a > b : return 1

a < b : return -1 

 

Comparator

인터페이스.

import java.util.Comparator;	// import 필요
public class ClassName implements Comparator<Type> { 
 
/*
  ...
  code
  ...
 */
 
	// 필수 구현 부분
	@Override
	public int compare(Type o1, Type o2) {
		/*
		 비교 구현
		 */
	}
}

compare 함수도  compareTo 함수와 마찬가지로

o1 == o2 : return 0

o1 < o2 : return -1

o1 > o2 : return 1

을 반환한다.

 

compare의 리턴값이 1일때 배열에서 o1, o2 두 값을 swap한다.

그래서 o1 - o2 하면 오름차순,

o2 - o1 하면 내림차순이다.

 

 

question?

Comparator은 인터페이스인데

Arrays.sort(intArr,new Comparator<Integer>() {} 이런식으로 어떻게 함수처럼 바로 쓸까?

익명 클래스를 사용했기 때문이다!

위의 new Comparator() {}는 익명 클래스 객체이다.

원래 Comparator 객체를 사용하려면 Comparator 인터페이스를 구현한 클래스 하나 만들고, 또 그 클래스 객체를 만들어 사용해야하는데 이 과정이 너무 비효율적이다.

그래서 이런식으로 과정을 확 줄여서 사용한다,

인터페이스명 변수명 = new 인터페이스명() {
    // 인터페이스 메서드 구현
    // 추가적인 멤버 변수 또는 메서드도 선언 가능
};

 

 

 

소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class q_1181 {
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int num = Integer.parseInt(br.readLine());            
            String[] arr = new String[num];
            
            for (int i = 0; i < num; i++) {
            	arr[i] = br.readLine();
            }
            
            // 정렬
            Arrays.sort(arr, new Comparator<String>() {
            	@Override
            	public int compare(String a, String b) {
            		if (a.length() == b.length()) {
            			return a.compareTo(b); // 사전 순 정렬
            		}
            		else {
            			return a.length() - b.length(); // 단어 길이 순 정렬
            		}            		
            	}
            });
            
            // 출력
            bw.write(String.valueOf(arr[0])+"\n");
            for (int i = 1; i < arr.length; i++) {
            	if (!arr[i - 1].equals(arr[i])) {
            		bw.write(String.valueOf(arr[i])+"\n");
            	}
            }

            // close
            br.close();
            bw.flush();
            bw.close();
      }
      catch (IOException e) {
          System.out.println("IOException 발생");
      }
	}
}

 

 

문제 풀었던 과정

문제를 읽자마자 

1. 길이가 짧은 것부터 -> 정렬 알고리즘 사용(버블정렬을 사용했다)
2. 길이가 같으면 사전 순으로 -> 문자열을 아스키코드 변환해서 오름 차순 정렬

생각이나서 문제를 풀었다.

package backjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class q_1181 {
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int num = Integer.parseInt(br.readLine());            
            String[] arr = new String[num];
            
            for (int i = 0; i < num; i++) {
            	arr[i] = br.readLine();
            }
            
            // 정렬
            String temp;
            int result = 0;
            for (int i = 0; i < num; i++) {
            	for (int j = 0; j < num-1; j++) {
            		if (arr[j].length() > arr[j + 1].length()) {
            			temp = arr[j];
            			arr[j] = arr[j + 1];
            			arr[j+1] = temp;
            		}
            		if (arr[j].length() == arr[j + 1].length()) {
            			result = arr[j].compareTo(arr[j + 1]); // 값 비교
                		if (result < 0) { // 사전 순 정렬
                			temp = arr[j];
                			arr[j] = arr[j + 1];
                			arr[j+1] = temp;
                		}
                		
                		else if (result == 0) { // 값이 같음
                			arr[j] = "";
                		}
            		}
            	}
            }

            // 출력
            for (int i = 0; i < arr.length; i++) {
            	if (arr[i].length() != 0) {
            		bw.write(String.valueOf(arr[i])+"\n");
            	}
            }

            // close
            br.close();
            bw.flush();
            bw.close();
      }
      catch (IOException e) {
          System.out.println("IOException 발생");
      }
	}
}

 

결과 : 시간 초과

버블 정렬을 사용한것이 문제인것 같다.