[백준알고리즘] 정렬 - 1181 단어 정렬 문제(+추가할 내용 있음)

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

1181번: 단어 정렬

결론부터 말하자면 세번만에 맞았습니다가 떴는데,

두번 다 시간초과 이슈로 실패했었다..

초기 풀이과정은 이러했다

단어들을 입력받아 저장할 String 배열과 각 단어의 길이를 저장할 int배열을 선언하고

이중 for문 내에서 가장 큰 값과 그 위치를 찾고, 만약 찾아놓은 큰 값과 비교할 값이 같다면

또 for문을 돌면서 단어의 문자열의 첫번째~n번째 문자(charAt()사용)를 하나씩 int로 형변환해 비교하여

더 큰 값을 가지는 원소가 뒤로 배치되도록 했다

(정수형으로 변환해서 더 큰값이 나온다는건 아스키코드표 순서상 더 뒤에 있다는 의미이므로 사전순과도 부합할것이다)

안쪽 for문을 다 돌고나면 String 배열, Int 배열에서 동일하게 위치교환이 이루어지도록 했고

이 정렬 과정이 끝나면 String 배열을 LinkedHashSet로 만들어 원소 중복을 제거하고 나온 결과가 출력되도록 했다.

근데 시간초과가 떴다. 혹시 LinkedHashSet이 문제였나 싶어 이번엔 이걸 사용하지 않고

정렬 과정이 끝나고 난 뒤 이중for문으로 배열을 돌면서 중복되는 값을 공백문자열로 대체하고

출력할때 공백 문자열은 빼고 출력되도록 조건을 주었다.

결과는 이번에도 시간초과..

내가 코드를 넘 비효율적으로 짰나?싶어서 뇌에 힘주고 다시 봤다

음..쓸데없는 부분이 너무 많았다...이래서 코드짤때 애초에 집중해서 해야한다..냅다 하지 말고..의심해가면서..

일단 어디어디를 고쳤나면

정렬 하기 전에 LinkedHashSet을 이용하여 중복 원소를 미리 제거했고,

굳이 사용할 필요 없었던 int배열(단어들의 길이를 저장하는 배열)과 그 관련코드를 삭제하고

한 원소의 길이가 필요할때마다 그냥 Length()함수를 쓰게 했다

고친 보람이 있어서 다행이었다...~

 

최종풀이코드

package baekjoonWeek2;

import javax.imageio.IIOException;
import java.io.*;
import java.util.Arrays;
import java.util.LinkedHashSet;

public class WordSorting {  //백준 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 N = Integer.parseInt(br.readLine());    //입력될 단어의 수
        String[] words = new String[N];
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine(); 
        }

        int max = 0; int maxIndex = 0;
        String compareM; String compareJ; String temp = "";
        int intM; int intJ;

        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(Arrays.asList(words));
        // LinkedHashSet을 배열로
        words = linkedHashSet.toArray(new String[0]);

        int length = words.length;
        for (int i = 0; i < length; i++) {
            max = 0;    //가장 긴 문자열원소의 길이
            for (int j = 0; j < length - i; j++) {
                if (words[j].length() > max) {
                    max = words[j].length();
                    maxIndex = j;
                } else if (words[j].length() == max) {
                    compareM = words[maxIndex]; //비교할 단어
                    compareJ = words[j];
                    for (int k = 0; k < words[maxIndex].length(); k++) {
                        intM = compareM.charAt(k);  //자동형변환 char -> int (반대는 명시적 형변환?뭐더라)
                        intJ = compareJ.charAt(k);
                        if (intM < intJ) {  //j가 정수형으로 바꿨을떄 더 큰수가 된다는건 더 뒤에있는 문자라는 의미일테니까 뒤에 배치되도록
                            max = words[j].length();
                            maxIndex = j;
                            break;  //중간에 브레이크 안하면 맨 마지막 문자만 비교하는꼴이 된다!!
                        }else if (intM > intJ) {
                            break;  //바꿀건 없다
                        }
                    }
                }

            }
            //교환
            temp = words[length-i-1];
            words[length-i-1] = words[maxIndex];
            words[maxIndex] = temp;
        }

        for (int i = 0; i < length; i++) {
            bw.write(words[i]);
            bw.newLine();

        }
        bw.flush();
        bw.close();


    }
}

+아, LinkedHashSet를 사용하지 않고 중복 문자열을 제거하는 최대한 간단한 방법을 찾아서 추가해두겠다.