백준 1181번-단어 정렬(JAVA)

www.acmicpc.net/problem/1181

1181번: 단어 정렬

 

N개의 단어를 입력받고

그 단어들을 길이가 짧은 순으로, 길이가 같다면 사전 순으로 정렬하는 문제입니다.

중복되는 단어가 있다면 하나만 출력합니다.

 

 

HashMap을 사용하면 깔끔하게 구현할 수 있습니다.

저는 정렬 후 출력할 때 중복되는 값은 출력되지 않게 하는 방식으로 구현했는데

두 방법 모두 작성해보겠습니다.

 

---

 

 

제가 쓴 코드입니다.

 

- HashMap 없이 구현한 방식

import java.util.*;

public class Main {
    public static void main(String[] args) {

        // 1181번
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        String[] arr = new String[N];
        sc.nextLine();

        for(int i=0;i<N;i++){
            arr[i]=sc.nextLine();
        }

        Arrays.sort(arr, new Comparator<String>() {
            public int compare(String o1, String o2) {
                if(o1.length()>o2.length()){
                    return 1;
                }else if(o1.length()<o2.length()){
                    return -1;
                }else if(o1.length()==o2.length()){
                    return o1.compareTo(o2);
                }
                return 0;
            }
        });

        int flag=0;

        for(int i=0;i<N;i++){
            flag=0;

            for (int j = i-1; j>=0; j--) {
                if (arr[i].equals(arr[j])) {
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                System.out.println(arr[i]);
            }
        }
    }
}

 

풀이과정

1. 단어 개수 N을 받고, N크기의 String 배열을 생성.

   반복문을 통해 단어를 입력받습니다.

 

2. 받은 문자열을 정렬해줍니다.

   Arrays.sort 메소드 사용.

   익명 인터페이스 Comparator를 구현합니다.

   

    compare 메소드에선 각 단어끼리의 길이를 비교합니다.

    비교한 결과에 따라 1이나 -1이 반환됩니다.

    둘의 길이가 같을 경우엔 사전순으로 정렬하면 되므로, String의 compareTo를 수행한 값을 반환해줍니다.

 

3. 중복된 단어 없이 출력합니다.

   이때 중복일 경우엔 출력이 안되도록 할 식별자로 변수 flag를 반복문 바깥쪽에 미리 선언해둡니다.

   

   바깥쪽 반복문이 수행될 때마다 flag를 0으로 초기화해줍니다.

   안쪽 반복문에선 중복값이 있을 경우 flag를 1로 바꿉니다.

   

   flag가 0일 경우에만 단어가 출력됩니다.

 

 

---

HashMap을 사용하면 중복제거 과정이 필요 없기 떄문에 좀더 간결해집니다.

 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {

        // 1181번
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        HashMap<String,String> map = new HashMap<String, String>();
        sc.nextLine();

        for(int i=0;i<N;i++){
            map.put(sc.nextLine(),"");
        }

        ArrayList<String> list = new ArrayList<String>(map.keySet());

        Collections.sort(list, new Comparator<String>() {
            public int compare(String o1, String o2) {
                if(o1.length()>o2.length()){
                    return 1;
                }else if(o1.length()<o2.length()){
                    return -1;
                }else if(o1.length()==o2.length()){
                    return o1.compareTo(o2);
                }

                return 0;
            }
        });

        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }

    }
}

 

 

풀이과정

1. 문자 개수 N을 입력받고, HashMap을 생성합니다.

   반복문에서 단어를 입력받습니다. (value는 사용하지 않을 것이므로 임의로 빈 문자열을 넣음)

   Map에선 key값이 중복되지 않으므로, 입력과 동시에 중복제거가 되었습니다.

 

2. Collections.sort 를 사용할 것이므로 map을 ArrayList에 옮겨줍니다.

   위와 같은 방식으로 Comparator를 구현해 길이가 짧은 순, 사전 순으로 정렬합니다.

 

3. 출력합니다.