import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class CreateString {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //문자열 길이
List<Character> S = new ArrayList<Character>(); //문자열 S
List<String> T = new ArrayList<String>(); //새로운 문자열 T
for (int i = 0; i < N; i++) {
S.add(sc.next().charAt(0)); //char형을 입력받기 위해 charAt 메소드 사용.
}
for (int i = 0; i < N; i++) {
if (S.get(0) > S.get(S.size() - 1)) { //가장 앞 문자보다 가장 뒷 문자가 더 작다. ex) b > a
T.add(S.get(S.size() - 1).toString()); //S는 Char이기에 String으로 바꿔줌.
S.remove(S.size() - 1);
} else if (S.get(0) == S.get(S.size() - 1) && S.size() > 1) { // 가장 앞 문자와 뒷 문자가 같다. + S의 size가 1이면.. 즉 문자가 1개 남았다면 앞뒤 사이즈가 똑같기에 패스
//그 다음 수를 생각해야함. 맨 앞의 다음 문자와 맨 뒤의 전 문자를 비교해줌.
int size = S.size();
for (int j = 1; j < S.size(); j++) {
if (S.get(0 + j) == S.get(S.size() - 1 - j)) { //또 맨 앞과 맨 뒤가 같으면 그 다음 문자 비교. 다를때까지 비교!
if (j == S.size() - 1) { //만약 모두 같은 문자로만 이루어진 입력값일 경우 대비.
T.add(S.get(0).toString());
S.remove(S.get(0));
continue;
}
continue;
} else if (S.get(0 + j) > S.get(S.size() - 1 - j)) {
T.add(S.get(S.size() - 1).toString());
S.remove(S.size() - 1);
break;
} else {
T.add(S.get(0).toString());
S.remove(S.get(0));
break;
}
}
} else {
T.add(S.get(0).toString());
S.remove(S.get(0));
}
}
for (int i = 0; i < T.size(); i++) {
if (i % 80 == 0 && i != 0) {
System.out.println();
}
System.out.print(T.get(i));
}
}
}
이번 문제는 문자열을 입력 받아서 두 가지의 규칙에 따라 만든 후 사전적순에서 가장 빠른 새로운 문자열 T를 만드는 문제였습니다. 규칙은 입력 문자열 S의 가장 앞 혹은 가장 뒤의 문자만을 T에 추가할 수 있다는 것입니다.
문자열을 입력 받으면 맨 앞 문자와 맨 뒤 문자를 비교 후 더 빠른 문자를 새로운 문자열 T에 추가해줬습니다. 이때 맨앞과 뒤의 문자가 같다면 그 다음 문자를 확인하고 그 다음 문자도 같다면 계속 확인 범위를 늘려줬습니다.
List<Character> S = new ArrayList<Character>(); //문자열 S
List<String> T = new ArrayList<String>(); //새로운 문자열 T
문자열의 경우에는 배열로 만들면 크기를 변형시켜주기가 쉽지 않기에 크기가 가변적인 ArrayList를 사용했습니다. 입력 값인 S의 경우 문제에서 입력을 한 글자씩 해주기에 Char형으로 레퍼클래스를 만들어줬고 입력 후 만들어지는 T는 String으로 만들었습니다. 하지만 둘 다 char형으로 해도 별 문제는 없을 듯합니다.
for (int i = 0; i < N; i++) {
if (S.get(0) > S.get(S.size() - 1)) { //가장 앞 문자보다 가장 뒷 문자가 더 작다. ex) b > a
T.add(S.get(S.size() - 1).toString()); //S는 Char이기에 String으로 바꿔줌.
S.remove(S.size() - 1);
}
첫 for 문은 문자열 길이만큼 반복해줘서 모든 문자를 확인해줄 수 있도록 하였습니다.
첫 if 문의 기능은 ArrayList의 값을 get메서드를 통해 받아와 사용했으며 S.get(0), 즉 가장 앞의 문자가 S.get(S.size() - 1) ,즉 가장 맨 두의 문자보다 숫자가 크다면 새로운 문자열 T에 맨 뒤의 값을 추가해주고 원래 있던 S 문자열에서 해당 문자를 삭제해줬습니다.
여기서 S는 char형이기에 유니코드를 통한 대소비교가 가능한 점을 이용했습니다. 예를 들어 b와 a를 비교한다면 b의 유니코드가 더 크기에 사전적 의미에서 더 빠른 단어는 a가 됩니다.
else if (S.get(0) == S.get(S.size() - 1) && S.size() > 1) { // 가장 앞 문자와 뒷 문자가 같다. + S의 size가 1이면.. 즉 문자가 1개 남았다면 앞뒤 사이즈가 똑같기에 패스
//그 다음 수를 생각해야함. 맨 앞의 다음 문자와 맨 뒤의 전 문자를 비교해줌.
int size = S.size();
for (int j = 1; j < S.size(); j++) {
if (S.get(0 + j) == S.get(S.size() - 1 - j)) { //또 맨 앞과 맨 뒤가 같으면 그 다음 문자 비교. 다를때까지 비교!
if (j == S.size() - 1) { //만약 모두 같은 문자로만 이루어진 입력값일 경우 대비.
T.add(S.get(0).toString());
S.remove(S.get(0));
continue;
}
continue;
} else if (S.get(0 + j) > S.get(S.size() - 1 - j)) {
T.add(S.get(S.size() - 1).toString());
S.remove(S.size() - 1);
break;
} else {
T.add(S.get(0).toString());
S.remove(S.get(0));
break;
}
}
}
다음은 맨 앞의 문자와 맨 뒤의 문자가 같을 경우입니다. 이때는 그 다음 문자를 보고 사전적으로 더 빠른 문자를 찾아야하는데 그 앞 문자도 똑같다면 더 앞의 문자를, 그 문자도 똑같다면 계속해서 더 앞의 문자를 비교해주어야 합니다. 예를 들어 cbfabc가 입력되었다고 할 때 맨 앞과 뒤 문자열을 한 번만 비교하고 같다면 앞의 문자를 임의로 쓴다고 한다면 그 결과는 ccbbaf가 됩니다. 하지만 c다음 칸을 보면 b가 서로 같고 그 다음 칸을 보면 f와 a가 남습니다. a가 사전적으로 빠르기에 저희는 오른쪽을 먼저 없애주는 쪽으로 단어를 골라줘야 합니다. 그렇게 하면 ccbabf가 나오고 사전적으로 더 빠른 단어가 되는 것을 알 수 있습니다. 또한 for문 안의 두 번째 if문의 경우에는 첫 입력에서 aaa와 같이 모두 같은 모양의 단어가 들어왔을 경우를 대비해서 만들어줬습니다.
else {
T.add(S.get(0).toString());
S.remove(S.get(0));
}
}
for (int i = 0; i < T.size(); i++) {
if (i % 80 == 0 && i != 0) {
System.out.println();
}
System.out.print(T.get(i));
}
}
마지막으로 남는 경우인 맨 앞의 문자가 사전적으로 빠른 경우를 추가해주고 80번째 줄 마다 줄넘김을 해줘서 print를 해주면 문제를 해결할 수 있습니다.
처음엔 그냥 앞뒤만 비교했는데 문자열의 길이라든지 같은 모양의 문자열만 입력될 경우라던 지를 생각하지 못해서 오랜 시간 고민하게 됐던 문제였습니다. 그래도 되게 재밌게 풀 수 있었던 거 같습니다.
출처 : 백준 6137번 링크 https://www.acmicpc.net/problem/6137
Git 주소 : https://github.com/LeejeongwooKuma/BaekJoon/blob/master/src/com/leejeongwoo/string/CreateString.java