BAEKJOON / 백준 - JAVA 29198번 이번에는 C번이 문자열

2024.06.27기준 - 실버3

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 제공된 문자열을 통해 k만큼 조합해 사전순으로 가장 빠르게 나올 수 있는 단어를 찾는 문제입니다.

 

이 문제의 핵심은 조합된 문자열을 다시 정렬을 할 수 있다는 것이 핵심이라고 생각합니다.

 

1. 입력받은 문자열을 문자 별로 사전순 정렬합니다.

arr = br.readLine().toCharArray();
Arrays.sort(arr); // 입력 받은 문자열을 문자 별로 정렬

합쳐진 문자열도 사전순으로 정렬을 하기 때문에, 입력 받은 문자열을 사전순으로 정렬을 하여 계산에 편하게 접근했습니다.

 

2. 정렬된 문자로 리스트에 저장을 합니다.

// 정렬된 문자를 저장
sub = new StringBuilder();
for (int j = 0; j < m; j++) {
    sub.append(arr[j]);
}

 

3. 저장된 리스트를 사전순으로 정렬합니다.

Collections.sort(list); // 하나하나 정렬된 문자열 전체를 사전순으로 정렬

 

4. 정렬된 리스트에서 k번 만큼 단어를 꺼내 붙여 줍니다.

// k개 만큼 전부 합쳐준다.
for (int i = 0; i < k; i++) {
    sub.append(list.get(i));
}

 

5. 붙여진 문자열를 문자열의 문자를 사전순으로 정렬 뒤 출력을 해줍니다.

arr = sub.toString().toCharArray();
Arrays.sort(arr); // k만큼 합쳐진 문자열의 문자를 사전순으로 정렬

// 정렬된 문자열 출력
for (char c : arr) {
    sb.append(c);
}

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 문자열 개수
		int m = Integer.parseInt(st.nextToken()); // 문자열 길이
		int k = Integer.parseInt(st.nextToken()); // 합쳐야 되는 문자열 수
		
		StringBuilder sub; 
		char[] arr;
		List<String> list = new LinkedList<>();
		for (int i = 0 ; i < n; i++) {
			arr = br.readLine().toCharArray();
			Arrays.sort(arr); // 입력 받은 문자열을 문자 별로 정렬
			
			// 정렬된 문자를 저장
			sub = new StringBuilder();
			for (int j = 0; j < m; j++) {
				sub.append(arr[j]);
			}
			
			// 정렬된 문자열을 리스트에 저장
			list.add(sub.toString());
		}
		
		sub = new StringBuilder();
		Collections.sort(list); // 하나하나 정렬된 문자열 전체를 사전순으로 정렬
		
		// k개 만큼 전부 합쳐준다.
		for (int i = 0; i < k; i++) {
			sub.append(list.get(i));
		}
		
		arr = sub.toString().toCharArray();
		Arrays.sort(arr); // k만큼 합쳐진 문자열의 문자를 사전순으로 정렬
		
		// 정렬된 문자열 출력
		for (char c : arr) {
			sb.append(c);
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}