[백준] 6137번 : 문자열 생성 - Java(자바)

이정우·2022년 2월 21일
0

백준

목록 보기
32/32

Step 0. 해답 코드

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에 추가할 수 있다는 것입니다.

Step 1. 문제 접근

문자열을 입력 받으면 맨 앞 문자와 맨 뒤 문자를 비교 후 더 빠른 문자를 새로운 문자열 T에 추가해줬습니다. 이때 맨앞과 뒤의 문자가 같다면 그 다음 문자를 확인하고 그 다음 문자도 같다면 계속 확인 범위를 늘려줬습니다.

Step 2. 문제 해결

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를 해주면 문제를 해결할 수 있습니다.

Step 3. 느낀 점

처음엔 그냥 앞뒤만 비교했는데 문자열의 길이라든지 같은 모양의 문자열만 입력될 경우라던 지를 생각하지 못해서 오랜 시간 고민하게 됐던 문제였습니다. 그래도 되게 재밌게 풀 수 있었던 거 같습니다.

출처 : 백준 6137번 링크 https://www.acmicpc.net/problem/6137

Git 주소 : https://github.com/LeejeongwooKuma/BaekJoon/blob/master/src/com/leejeongwoo/string/CreateString.java

profile
프로그래밍 공부 중!

0개의 댓글