단어 정렬
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.
예제 입력 1
13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours
예제 출력 1
i
im
it
no
but
more
wait
wont
yours
cannot
hesitate
내가 처음 푼 방식.
wordList 이름의 ArrayList를 만들고, 단어를 입력받아서 넣을 때 마다 길이와 오름차순 순서, 같은 단어 여부를 비교해서 추가했다.
입력받아 리스트에 넣을 때 마다 리스트에 들어있는 단어들과 비교하니 실행 시간이 엄청 오래 걸렸다..
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
List<String> wordList = new ArrayList<>();
String word = br.readLine();
wordList.add(word);
out:for (int i = 0; i < N - 1; i++) {
word = br.readLine();
int size = wordList.size();
for (int j = 0; j < size; j++) {
String getWord = wordList.get(j);
if (word.length() < getWord.length()) {
wordList.add(j, word);
continue out;
}else if(word.length() == getWord.length()) {
if(word.compareTo(getWord) < 0) {
wordList.add(j, word);
continue out;
}else if(word.equals(getWord)) {
continue out;
}
}
}
wordList.add(word);
}
for (int i = 0; i < wordList.size(); i++) {
bw.write(wordList.get(i) + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
두 번째로 푼 방식.
Map을 만들고, key는 해당 단어의 length, values는 해당 length를 가진 단어들을 ArrayList 형태로 넣었다.
출력할 때 key순으로(단어 길이 순으로), 거기서 단어를 오름차순으로 정렬해서 출력했다.
실행 시간이 줄긴 했는데 여전히 조금 오래 걸리는 것 같다..!
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Map<Integer, ArrayList<String>> wordMap = new HashMap<>();
ArrayList<String> wordList;
String word;
int length;
for (int i = 0; i < N; i++) {
word = br.readLine();
length = word.length();
if (wordMap.containsKey(length)) {
wordList = wordMap.get(length);
} else {
wordList = new ArrayList<>();
}
if (wordList.contains(word)) {
continue;
}
wordList.add(word);
wordMap.put(length, wordList);
}
Object[] lengths = wordMap.keySet().toArray();
Arrays.sort(lengths);
for (int i = 0; i < lengths.length; i++) {
length = (int) lengths[i];
wordList = wordMap.get(length);
Collections.sort(wordList);
for (int j = 0; j < wordList.size(); j++) {
bw.write(wordList.get(j) + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
}
세 번째 방법..
입력 받은 단어를 set에 추가하고, 단어 길이가 ~50까지 이므로, 1-50까지 set에서 각각의 길이에 해당하는 단어를 찾아 arraylist에 추가하고 set에서는 삭제 후 출력시켰다.
시간이 조금.. 더 줄긴 했다
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Set<String> wordSet = new HashSet<>();
for (int i = 0; i < N; i++) {
wordSet.add(br.readLine());
}
ArrayList<String> wordList;
for (int i = 1; i <= 50; i++) {
Iterator<String> iterator = wordSet.iterator();
wordList = new ArrayList<>();
while (iterator.hasNext()) {
String word = iterator.next();
if (word.length() == i) {
wordList.add(word);
}
}
wordSet.removeAll(wordList);
Collections.sort(wordList);
for (int j = 0; j < wordList.size(); j++) {
bw.write(wordList.get(j) + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
}
마지막으로 다른 분들 코드를 참조한 풀이.
arrayList에 입력받은 단어를 모두 추가하고, Comparator를 이용해 길이순으로, 오름차순으로 정렬했다.
그리고 출력할 때 중복된 값을 제외하고 출력하도록 했다.
나는 값을 넣을 때 중복 값은 넣지 않도록 하려 했는데, 아래 방식으로는 출력할 때 이전 인덱스 값과만 비교해서 같으면 출력하지 않도록 했다. 여기서 시간이 많이 단축되었다!!
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
ArrayList<String> wordList = new ArrayList<>();
String word;
for (int i = 0; i < N; i++) {
word = br.readLine();
wordList.add(word);
}
Collections.sort(wordList, 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;
}
}
});
bw.write(wordList.get(0) + "\n");
for (int i = 1; i < wordList.size(); i++) {
if (!wordList.get(i).equals(wordList.get(i - 1))) {
bw.write(wordList.get(i) + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
}
'6. 자료구조 & 알고리즘 > 6-2. 백준' 카테고리의 다른 글
백준 - [ 11051번: 이항 계수2 ] (0) | 2022.08.16 |
---|---|
백준 - [ 2477번: 참외밭 ] (0) | 2022.08.04 |
백준 - [1436번: 영화감독 숌] (0) | 2022.07.29 |
2751번: 수 정렬하기 2 (0) | 2022.07.01 |
백준 - [1018번: 체스판 다시 칠하기] (0) | 2022.06.27 |