[백준] 1181번 : 단어 정렬(JAVA)

패키지 지우는거 깜빡해서 분노.gif

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

1181번: 단어 정렬

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계

 

정렬의 카테고리에 포함되어 있는 문제이다.

 

알파벳 소문자로 이루어진 N개의 단어가 들어왔을 때의 조건은

 

1. 길이가 짧은 것 부터

 

2. 길이가 같으면 사전 순으로

 

이 두개의 조건을 지켜서 문제를 제출하면 된다.

 

Merge Sort로 구현을 하였으며 제출할 때 package를 지우는 것을 깜빡하고

 

3번이나 틀린 문제이다.

 

3번씩이나 틀릴 동안 질문게시판을 돌아다니며 반례만 찾고있었다...

 

다음부터는 이런  실수를 하지 말아야 겠다ㅠㅠ

 

입력과 출력은 단어의 개수가 최대 20,000개 까지 들어올 수 있다고 하여

 

더 빠르게 입력과 출력을 하는 Buffer를 사용하였다.

 

문제가 긴 만큼 설명은 코드블럭에 주석으로 달아놓았습니다.

 

import java.io.*;

class Sort {
	String[] temp;
	
	public Sort(int Number) {
		temp = new String[Number];
	}
	
	public void Merge(String[] x, int left, int right) {
		int mid;
		if(left < right) {
			mid = (left + right) / 2;
			Merge(x, left, mid);
			Merge(x, mid + 1, right);
			Merge_Last(x, left, mid, right);
		}
	}
	
	public void Merge_Last(String[] x, int left, int mid, int right) {
		int i = left;
		int j = mid + 1;
		int k = left;
		
		while(i <= mid && j <= right) {
			if(x[i].length() < x[j].length()) {	//	문자열의 길이비교
				temp[k++] = x[i++];
			} else if (x[i].length() == x[j].length()){	//	문자열의 길이가 같을 때
				
				int compare = 0;
				
				while(x[i].charAt(compare) == x[j].charAt(compare)) {	//	문자열의 각 첫 번째 문자부터 비교
					compare++;
					if(compare == x[i].length())
						break;
				}
				
				if(compare == x[i].length()) {	//	compare이 x[i].length()와 같다는건 x[j]와 똑같은 문자라는 뜻임
					temp[k++] = x[i++];
				} else {
					if(x[i].charAt(compare) < x[j].charAt(compare)) {
						temp[k++] = x[i++];
					} else {
						temp[k++] = x[j++];
					}
				}
				 				
			} else {
				temp[k++] = x[j++];
			}
		}
		
		while(i <= mid)
			temp[k++] = x[i++];
		
		while(j <= right)
			temp[k++] = x[j++];
		
		for(int index = left; index < k; index++) {
			x[index] = temp[index];
		}
	}
}

public class Question_1181 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int Number = Integer.parseInt(br.readLine());
		
		String[] Input = new String[Number];
		
		for(int i = 0; i < Number; i++) {
			Input[i] = br.readLine();
		}
		
		Sort st = new Sort(Number);
		
		st.Merge(Input, 0, Input.length - 1);
		
		for(int i = 0; i < Number; i++) {
			if(i > 0) {
				if(Input[i].equals(Input[i-1]))	//	출력할 문자열이 전에 출력한 문자열과 같으면 다음으로 넘어간다.
					continue;
			}
			bw.write(Input[i] + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}