문제 내용은 주어진 문자열을 받아 사전 순 가장 빠른 문자열을 출력해야 하는데, 주의해야 할 점이 단순 문자열을 가지고 가장 빠른 문자열을 만드는게 아니라 예를 들어 부분에 있는 규칙에 의거해서 가장 빠른 문자열을 만들어줘야 한다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
for (int i = 0; i < count; i++) {
br.readLine();
String[] arr = br.readLine().split(" ");
ArrayDeque<String> deque = new ArrayDeque<>();
for (int j = 0; j < arr.length; j++) {
if (deque.isEmpty()) {
deque.add(arr[j]);
} else {
char c = arr[j].charAt(0);
if (deque.peek().charAt(0) >= c) {
deque.addFirst(arr[j]);
} else {
deque.addLast(arr[j]);
}
}
}
StringBuilder val = new StringBuilder();
for (String value : deque) {
val.append(value);
}
System.out.println(val.toString());
}
}
}문제를 꼼꼼하게 읽어보지 않았었다면, 그냥 우선순위큐 써서 가장 빠른 문자열 만들면 끝 아닌가 싶겠지만, 규칙에 의거해서 가장 빠른 문자열을 만들어야 하기 때문에
deque를 사용해서 문제를 풀어줘야 하는데, 문자열을 받아서 비어있을 때는 가장 앞에 넣어주고, 그 다음부터는 deque 가장 앞에 있는 값보다 빠른 문자열이면 앞에 넣어주고 아니면 뒤에 넣어주는 식으로 값을 모두 받아 처리해준 후 출력해주면 끝이다.
처음에 문제를 제대로 이해하지 못했다면, 엄청난 시간을 허비할 수 있기 때문에 문제 개발쇠발 써 놨어도 잘 읽고 진행해줘야 한다.
Leave a Reply