백준 1181번 "단어정렬"

백준 1181번

 

• 문제

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

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

단, 중복된 단어는 하나만 남기고 제거해야 한다.

 

• 입력

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

 

• 출력

조건에 따라 정렬하여 단어들을 출력한다.

 

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

1181번: 단어 정렬

 

 

 

 

처음 제출한 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let word_num = +input[0];
let words = [];
let result = [];

//입력받은 값을 배열화
for(let i = 1;i<input.length;i++){
    words.push(input[i].trim());
}

//선형 검색
for(let i = 0;i<words.length;i++){
    for(let j = i+1;j<words.length;j++){
    	//단어의 길이를 비교하여 서로 위치를 바꿔줌
        if(words[i].length > words[j].length){
            let buffer = words[i];
            words[i] = words[j];
            words[j] = buffer;
            i--;
            break;
        }
    }
}

//선형검색
for(let i = 0;i<words.length;i++){
    for(let j = i+1;j<words.length;j++){
    	//같은 단어일경우 배열에서 삭제
        if(words[i] == words[j]){
            words.splice(j,1);
            i--;
            break;    
        }
        //단어의 길이가 같을경우 서로의 위치를 바꿔줌
        if(words[i].length == words[j].length){
            let iString = [];
            let jString = [];
            iString = words[i].toString();
            jString = words[j].toString();
            if(iString[0] > jString[0]){
                let buffer = words[i];
                words[i] = words[j];
                words[j] = buffer;
                i--;
                break;
            }
        }
    }
}
//출력
for(let i = 0; i < words.length;i++){
    console.log(words[i]);
}

 

 

처음 위 문제를 봤을때 아무 계획없이 무작정 구현만 하면 되겠구나 싶었다.

그결과 위와 같은 깨끗하지 않은 코드가 탄생하게 되었다..

 

위에서 작성한것은 js에서 제공하는 메소드를 적절히 사용하지 못한거 같다.

딱히 이렇다할 풀이방법이 없고 그저 배열로 만들어 선형검색으로 전체 배열을 검색하고 확인하여 데이터를 처리했다.

 

그결과는 당연히 시간초과이다!

 

위와 같은 방법이 정답이 될 수도 있겠지만(0.000001% 정도) 

위 방식은 처리해야하되는 데이터가 늘어나면 늘어날 수록 처리해야하는 양이 기하급수적으로 늘어난다.

 

즉,효율성면에서 완전 꽝이라는 것이다...

 

 

 

정답으로 제출한 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let word_num = +input[0];
let words = [];
let words_length = [];

for(let i = 1;i<input.length;i++){
    words.push(input[i].trim());
    words_length.push(input[i].trim().length);
}

//단어의 길이가 가장 큰것을 기준으로 배열의 크기를 선언한다.
let result = new Array(Math.max(...words_length));
for(let i = 0; i < result.length;i++){
    result[i] = [];
}

//단어의 길이별로 배열에 push 해준다
for(let i = 0; i < words.length; i++){
    result[words[i].length-1].push(words[i]);
}


for(let i = 0; i < result.length; i++){
	//정렬
    result[i].sort();
    for(let j = 0; j < result[i].length; j++){
    	//중복되있는 단어는 배열에서 제거해준다
        if(result[i][j] == result[i][j+1]){
            result[i].splice(j,1);
            j--;
        }
    }
    //배열안에 있는 값을 차례대로 출력해준다
    for(let j = 0;j<result[i].length;j++){
        console.log(result[i][j]);
    }
}

 

결과

 

 

문제를 해결함에 있어서 가장 중요한 단서는 단어의 길이인거 같다.

 

그래서 입력받은 값들을 1차적으로 분류를 해주었다.

 

단어의 길이가 같은것끼리 한 배열안에 모이도록 분류를 했다.

 

그 이후 배열안에 있는것만 정렬하여 같은 단어를 제거해주는 단계를 거쳤다.

(현재 이 글을 작성하면서 중복단어의 제거는 set 를 사용했다면 더 간편하게 해결했을거 같다는 생각이 든다)

 

초기보다 훨씬 깔끔한 코드가 짜여진것같다.

역시 무작정 구현보다는 어떻게하면 효율적으로 코드를 짤 수 있을까 많은 생각을 해야할거 같다..