[백준/JAVA] 1251번: 단어 나누기

🔺 문제

1251번: 단어 나누기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static String str;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
 
        List<String> list = new ArrayList<>();  // 단어 저장 집합
        int len = str.length();
 
        for(int i = 1 ; i < len ; i++) { // 쪼갤 첫 번째 위치
            for(int j = i + 1 ; j < len ; j++) { // 쪼갤 두 번째 위치
                String tmp = getWords(i, j);
                list.add(tmp);
            }
        }
        Collections.sort(list); // 단어 오름차순 정렬하기
 
        System.out.println(list.get(0));    // 사전 순 가장 앞서는 단어
    }
 
    private static String getWords(int s, int e) {
        StringBuilder sb = new StringBuilder();
 
        // 1. 문자열 3등분 쪼개기
        StringBuilder sb1 = new StringBuilder(str.substring(0, s));
        StringBuilder sb2 = new StringBuilder(str.substring(s, e));
        StringBuilder sb3 = new StringBuilder(str.substring(e));
 
        // 2. 쪼갠 부분 각각 뒤집고 합치기
        sb.append(sb1.reverse().toString());
        sb.append(sb2.reverse().toString());
        sb.append(sb3.reverse().toString());
 
        return sb.toString();
    }
}

 

 

🧩  해결 아이디어

• 문자열 & 정렬

- 2중 for문을 활용해 문자열을 3등분하고, 쪼갠 부분을 각각 뒤집고 합쳐 문자열 리스트에 값을 저장한다.

- 문자열 리스트를 오름차순 정렬하면 사전 순 정렬이 되므로, 맨 앞 값을 가져온다.

-> 시간 복잡도 : O(N^)

 

 

---

💬 느낀 점

재밌는 문자열 문제....

 

1회독	2회독	3회독	4회독	5회독
V	240220

 

 

(+ 240220 2회독 : 14936KB, 140ms)

import java.util.*;
import java.io.*;
 
public class Main {
    static String str;
    static List<String> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        
        for(int i = 1 ; i < str.length() - 1 ; i++) {
            for(int j = i + 1 ; j < str.length() ; j++) {
                StringBuilder sb = new StringBuilder();
                
                StringBuilder sb1 = new StringBuilder(str.substring(0, i));
                StringBuilder sb2 = new StringBuilder(str.substring(i, j));
                StringBuilder sb3 = new StringBuilder(str.substring(j));
                
                sb.append(sb1.reverse()).append(sb2.reverse()).append(sb3.reverse());
                list.add(sb.toString());
            }
        }
        
        Collections.sort(list);
        System.out.println(list.get(0));
    }
}

 

---

(참고)

✔ StringBuilder 활용해 문자열 뒤집기 : sb.reverse().toString()

[StringBuilder] StringBuilder.reverse() 이용해서 문자열 뒤집기