[백준 -1181번] 단어정렬 - JAVA 정리 및 해설

안녕하세요. 오늘은 단어 정렬과 그 속에 체크할 점을 짚고 넘어가겠습니다.

단어정렬 이문제는 그렇게 어려운 문제는 아닙니다. 기본적으로 정렬이라는 간단한 알고리즘을 통해서 문제를 풀어 내면 됩니다.

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

자바에서 여러가지 조건을 동시에 만족하는 정렬을 사용할때는 Comparator를 이용해서 정렬을 사용해야합니다.

문제의 정렬 조건은

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

위와 같기때문에 잘 짚고 넘어가야됩니다.  

자바에서는 Comparator가 세부적인 정렬 

예를들면, 자료 1 자료 2가 있을때 자료 1은 오름차순 자료 2는 내림차순으로 정렬을 해야하는 경우일때 기본정렬로는 해결이 잘 안되기때문에 comparator를 새로 지정해서 만들어줘야합니다.

기본적 로직은 코드 위 문단에 적었습니다. 약간의 정리문들은 넘기시고 보셔도됩니다.

저는 이 문제에서 런타임에러를 많이 나왔는데요. 문제는 comparator를 잘못썼다는 것에 있습니다.  

25번째 줄의 else if문에서  

 if(x.charAt(0)-y.charAt(0)>0){

  return 1;

  }

맨 앞글자만 비교를 해서 정리를 했는데요. 사실 같은 글자들 예를 들면 aa ab ac인경우 정렬이 이상하게 꼬인다는 문제가 있었습니다.

첫 번째 글자 이후로 다른 경우 compare(x,y)와 compare(y,x) 모두가 -1을 반환하는데 이는 x<y 이고 y<x라는 의미이기 때문에 올바르지 않은 비교 함수가 됩니다. (제 질문 답변 참조) 

위와 같은 이유로 런타임 에러가 발생했습니다. 

참고로 제가 실수했었던 부분이었던 compareTo를 너무 간과했습니다. ㅠ

즉 단어의 길이가 같은 조건 1인 경우에 그저 compareTo를 하면 문제가 문제없이 풀릴수 있는데요. 

Tip! : CompareTo는 String도 비교가 가능하고 사전순 배열을 알아서 해줍니다. 만약에 역순배열을 하려면 그 compareTo값에 -으로 리턴하면 역순배열(Z-A)배열도 가능합니다.  

https://m.blog.naver.com/PostView.nhn?blogId=cheesedrive&logNo=220148513502&proxyReferer=https%3A%2F%2Fwww.google.com%2F

혹시 compareTo 매소드에 대해서 자세하게 알아보시려면, 위의 블로그를 확인해주세요.

기본적 로직은 이렇습니다. 

일단 모든 단어를 받고 리스트 n에 넣기전에 한번 체크를 합니다. 중복되는 경우는 없어야합니다. 

<단, 리스트를 이용해서 중복처리를 하기때문에 저는 실행시간이 좀 많이 걸렸습니다. 다른분은 Hashset을 이용해서 중복처리를 하고 List를 넣은 경우도 있습니다.>

조건을 활용해서 1번 조건 길이는 String x변수의 .length()로 비교해서 체크 2번조건은 CompareTo를 통해서 해결. 

정렬 조건을 완료했으면, Collection의 Sort를 통해서 정렬 해주면 됩니다. 제가 만들었던 Comparator를 이용해서요.

List의 size를 통해서 for문을 만들어서 list안의 모든 단어를 출력해내면 됩니다.

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.List;

public class Main {
	 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		List<String> n = new ArrayList<String>(20010);
		for(int i =0; i<T; i++){
			String temp= br.readLine();
			if(!n.contains(temp))
			n.add(temp);
		}
		Comparator<String> myComparator = new Comparator<String>() {
			  public int compare(String x, String y) { 
				  if(x.length()>y.length()){
					  return 1;
				  }
				   else if(x.length()==y.length()){
					  return x.compareTo(y);
				  }
				  return -1;
			  }
			};
		Collections.sort(n, myComparator);
		for(int i =0; i<n.size(); i++){
			System.out.println(n.get(i));
		}
		
		
	}
}

 

단어 정렬 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	16385	5820	4113	36.822%

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.