반응형
🔺 문제
1251번: 단어 나누기
알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다
www.acmicpc.net
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
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();
}
}
|
cs |
🧩 해결 아이디어
• 문자열 & 정렬
- 2중 for문을 활용해 문자열을 3등분하고, 쪼갠 부분을 각각 뒤집고 합쳐 문자열 리스트에 값을 저장한다.
- 문자열 리스트를 오름차순 정렬하면 사전 순 정렬이 되므로, 맨 앞 값을 가져온다.
-> 시간 복잡도 : O(N^)
💬 느낀 점
재밌는 문자열 문제....
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 240220 |
(+ 240220 2회독 : 14936KB, 140ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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));
}
}
|
cs |
(참고)
✔ StringBuilder 활용해 문자열 뒤집기 : sb.reverse().toString()
[StringBuilder] StringBuilder.reverse() 이용해서 문자열 뒤집기
Javascript문법 공부중 this.message = this.message.split('').reverse().join('') 라는 얄미운 문법을 발견. 'Java엔 저런게 없을까' 라는 생각과 바로 시작 된 구글링. Java 또한 StringBuilder의 reverse() 메소드를 이용하
ahndding.tistory.com
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1749번: 점수따먹기 (0) | 2023.12.01 |
---|---|
[백준/JAVA] 4920번: 테트리스 게임 (0) | 2023.12.01 |
[백준/JAVA] 18114번: 블랙 프라이데이 (0) | 2023.11.30 |
[백준/JAVA] 2548번: 대표 자연수 (0) | 2023.11.29 |
[백준/JAVA] 14929번: 귀찮아 (SIB) (0) | 2023.11.28 |