[백준] 1181 - 단어 정리

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

1181번: 단어 정렬

문제

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

• 길이가 짧은 것부터
• 길이가 같으면 사전 순으로

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

출력
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

접근방법

N개의 단어를 기준에 맞게 정렬하는 문제이다. 이 문제는 문자열을 크기 순으로 정렬하고, 크기가 같은 것들에 대해서는 사전 순의 추가적인 정렬을 원한다. 그러기 위해선 1차적으로 문자열로 비교를 하고, 2차적으로 같은 길이에 대해 문자를 비교해야 한다. 또한 같은 단어에 대해서는 중복제거도 해야한다.

 그러면 생각해야 할 것이 명확해진다. 이 문제는 정렬 문제이지만, 특수한 조건이 붙은 정렬 문제이다. 그럼 특정 조건에 따라 문자열을 정렬할 생각을 가지고 문제에 접근해야 한다.

풀이

풀이에 앞서, 나는 이 문제를 3번 풀었다. 3번 풀이의 차이는 자료형의 차이이다. 종류는 아래와 같다.

1. HashMap을 사용함
2. ArrayList를 사용함
3. String만을 사용함

1. HashMap 이용

시간 초과의 이유로 통과를 하지 못했다. 궁금하다면, 접은 글을 참고 바란다.

왜 HashMap을 사용했는가?

나는 입력을 위해 String 배열을 N개 만들기가 싫었다. 그래서 동적 배열로 한 번에 정리가 되게 만들고 싶었고, 

그래서 HashMap을 사용했다. Key - Value의 구조이니, [Key - 단어의 길이 , Value - 단어들]로 정리하면, 한 번에 가능할 것이라고 생각했다. 코드는 다음과 같다.

import java.util.*;

public class BJ_1181 {
    public static void main(String[] args) {
        BJ_1181 test = new BJ_1181();
    }

    public BJ_1181() {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        HashMap<Integer, ArrayList<String>> dic = new HashMap<>();
        int tc = sc.nextInt();

        //개행 문자 삭제
        sc.nextLine();


        for (int i = 0; i < tc; i++) {
            String str = sc.nextLine();
            ArrayList<String> list;

            //Hash에 해당 길이를 가진 키값이 없다면
            if (!dic.containsKey(str.length())) {
                //새로 생성하여 삽입
                list = new ArrayList<>();
                list.add(str);
                dic.put(str.length(), list);
            } else {
                //해당 길이를 가진 키값이 존재한다면, value list를 가져와서 단어를 넣음
                list = dic.get(str.length());
                if(!list.contains(str)){
                    list.add(str);
                }
                //정렬을 수행함
                Collections.sort(list);
                //Hash에 다시 저장
                dic.put(str.length(), list);
            }


        }

        for (Map.Entry<Integer,ArrayList<String>>entry : dic.entrySet()){
            for (String answer : entry.getValue()){
                sb.append(answer+"\n");
            }
        }


        System.out.println(sb);
    }

}

 

어찌 보면 시간 초과가 난것은 당연하다. 반복문을 돌 때마다 Collections.sort 메소드가 사용된다. 그리고 애초에 정리하는 객체도 작은 객체가 아니다. Hashmap에 또다른 ArrayList 객체가 들어가 있다. 이것만 해도, 이 문제를 풀기엔 과도하게 큰놈을 데려온 것이다.

 

아마 많은 Collections.sort() 때문일 수도 있지만, 시간초과가 난 후, 너무 큰 놈으로 접근했다는 생각이 강해서, 자료형부터 바꿔서 다시 진행했다.

 

2.ArrayList 이용

입력된 문자열을 ArrayList에 담은 후에 정렬을 진행했다.

 

왜 ArrayList를 사용했나?

나는 중복을 제거하기 위해 사용했다. 단어의 중복을 미리 제거하고 정렬을 해야 나중에 고민할 필요가 없다고 생각했기 때문이다. 

 

문자열 비교 후 심지어 길이가 같을 때는 사전 순 정렬도 해야 하는데 어떻게 해나?

오늘의 핵심은 이 부분이라고 생각한다. 앞에도 언급되었지만, 해당 문제는 '특정 조건에 의한 정렬을 수행할 수 있는 코드를 만들 줄 아는가?'를 묻는 게 핵심이다. 그럼 일단 ArrayList에 중복이 제거된 데이터가 모였다고 생각해보자. 그럼 ArrayList가 정렬 메서드를 지원하는지부터 확인해보자.

 

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

ArrayList (Java Platform SE 8 )

다행히 지원한다. 공식 문서에서는 다음과 같이 얘기한다.

 

파라미터가 Comparator다. compare룰 통해 비교하란다. 정리하면 이렇다. sort메서드를 특정 조건에 의해 사용하려면, comparator로 된 인스턴스가 필요하다는 것까진 알겠다. 또 API에서는 친절히 compare메서드가 있어야 CastException에 안 던지시겠된다. 오케이 여기까지 알고, 그럼 Comparator를 알아보러 가자.

 

Comparable로 구현하는 방법도 있다. 급하게 이해가 필요하다면, 접은 글을 펼쳐보시면 도움이 될 것 같다.

st님께서 두 인터페이스의 차이를 잘 설명해주셨다. 참고 바란다.

https://st-lab.tistory.com/243?category=830901#none 

자바 [JAVA] - Comparable 과 Comparator의 이해

 

 

 

https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#compare-T-T-

Comparator (Java Platform SE 8 )

이 녀석은 문서를 보니까, interface 였다. 그럼 오버라이드 해서 쓰겠구나 라는 생각을 가지고, 공식 문서에 있는 Abstract Methods들이 무엇이 있나 한번 보자.

 

오버라이딩해야만 하는 메서드가 두 개 정도 보인다. 거기에 우리가 아까 보았던 익숙한 메서드의 이름이 보인다. Compare 메서드다. '그럼 오버라이딩해서 내부에 조건을 걸면 되지 않을까?' 라는 생각을 할 수 있다.

정답이다. 우리가 원하는 특정 정렬 조건을 여기에 만들 것이다.

 

(익명 클래스 생성 시, compare만 강제되는데 이유를 아시는 분은 댓글로 좀 알려주면 감사하겠습니다.)

 

자 이제 그럼 저 파라미터를 본다면, 우리가 어떻게 해야 할지 생각해보자.

• 우선적으로 문자열을 우린 비교할 것이기에 파라미터의 자료형은 String이 될 것이다.
• 두 문자열이 파라미터로 들어왔다. 그럼 글자 수로 우선적으로 비교한다.
• 글자가 같을 경우에 한해서 두 개를 자연 비교(사전 순 비교) 한다.

cf) compare 메서드는 -1이면 o1, 0이면 같음, 1이면 o2를 의미한다.

 

 

이제 풀이를 본다면, 보다 쉽게 아래 코드를 볼 수 있을 것이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        //입력
        int tc = sc.nextInt();
        String[] data = new String[tc];
        //개행문자 제거
        sc.nextLine();


        //입력
        for (int i = 0; i < tc; i++) {
            data[i] =sc.nextLine();
        }

        ArrayList<String> answers = new ArrayList<>();
        for (String str : data){
            if(answers.contains(str)){
                continue;
            }else{
                answers.add(str);
            }

        }
        
        //익명클래스를 이용
        answers.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                //같으면
                if (o1.length() == o2.length()){
                    //자연비교(사전순)
                    return o1.compareTo(o2);
                }else{
                    //글자수가 적은 원소가 나올 수 있게 조절
                    if (o1.length() < o2.length()){
                        return -1;
                    }else{
                        return 1;
                    }

                }

            }
        });

        for (String answer : answers){
            sb.append(answer+"\n");
        }

        System.out.println(sb);
    }

}

 

sort 메서드에 익명 클래스를 통해 인스턴스를 생성했고, 오버 라이딩된 compare메서드 안에 조건을 걸었다.

 

 

3.String 사용

 ArrayList를 이용하고 나니, 시간이 너무 무자비했다. 3 초라니, 혹시나 하고 다른 블로거분들의 결과를 보았더니, 압도적으로 시간 차이가 났다. 원인은 String 객체를 사용한 것도 있고, 중복을 제거하는 것이 아닌 출력선에서 동일 단어를 배제하여, 시간을 줄였다. 위와 원리는 동일하다. 다른 인터페이스를 사용했을 뿐이다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        //입력
        int tc = sc.nextInt();
        String[] data = new String[tc];
        //개행문자 제거
        sc.nextLine();


        //입력
        for (int i = 0; i < tc; i++) {
           data[i] =sc.nextLine();

        }

        //문자열 sorting을 위해 Comparator를 문자열에 따라 재정의함
        Arrays.sort(data,new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                //길이가 같다면 알파벳순
                if (o1.length() == o2.length()){

                    return o1.compareTo(o2);
                }else{
                    //아니라면 길이순으로 정렬
                    if (o1.length() < o2.length()){
                        return -1;
                    }else{
                        return 1;
                    }

                }

            }
        });

        sb.append(data[0]+"\n");
        for (int i = 1 ; i < data.length ; i++){
            if(data[i].equals(data[i-1])){
                continue;
            }
            sb.append(data[i]+"\n");
        }


        System.out.println(sb);
    }

}

 

결과

32347726 : String을 사용한 결과

32343388 : ArrayList를 사용한 결과

32342656 ,32342773 : HashMap을 사용한 결과

 

 

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

읽어주셔서 감사합니다. 

 

 

출처:

https://st-lab.tistory.com/112