[SWEA] #1257 - K번째 문자열

Algorithm/SW Expert Academy

[SWEA] #1257 - K번째 문자열

코드랜드 2022. 2. 23. 16:12

728x90

💡 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

💡 문제

[설명]

문자열의 부분 문자열은 문자열의 두 위치를 골라서, 이 사이의 연속한 문자열을 뽑아낸 것이다.

두 위치가 같을 때는 길이가 1인 부분 문자열이 된다.

예를 들어, 문자열 love의 모든 부분 문자열은 l, o, v, e, lo, ov, ve, lov, ove, love이다.

또 다른 예로, 문자열 food의 부분 문자열은 f, o, d, fo, oo,od, foo, ood, food가 있다. 동일한 문자열 o가 두 번 나오지만, 중복을 제거한 것에 유의하자.

부분문자열에 대해서 사전 순서로 정렬을 하고, 특정 위치에 오는 문자열을 출력해보자.

💡 아이디어

부분 문자열을 구하기 위해서는 2개의 for문을 사용한다.

먼저 첫 번째 for문에서 1부터 문자열의 길이까지로 지정하고,

두 번째 for문에선 substring을 사용하기 위해 0부터 (문자열의 길이 - 부분 문자열의 길이)까지로 지정했다.

이 값을 중복되지 않고 넣기 위해 TreeSet을 이용했다.

TreeSet은 중복을 허용하지 않고, TreeSet에 값을 추가하는데 O(log n)의 시간이 소요된다는 특징이 있다.

이 특징을 이용해 TreeSet에 값을 저장하고, K번째까지 for-each구문을 돌려 결과를 출력한다.

💡 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class P_1257 {
	static int Find;// 사전순으로 정렬했을 때 찾아야 하는 위치
	static int N;// 입력문자의 길이
	static String str;// 입력문자
	static TreeSet<String> Dick;// 사전순으로 정렬된 TreeSet

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("P1257_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			// 초기화
			Find = Integer.parseInt(br.readLine());
			str = br.readLine();
			N = str.length();
			Dick = new TreeSet<>();
			sb = new StringBuilder();
			int cnt = 0;

			for (int i = 1; i <= N; i++)// 한 글자에서 str의 길이만큼
				for (int j = 0; j <= N - i; j++)
					Dick.add(str.substring(j, j + i));// substring으로 분리한 다음 TreeSet에 삽입

			// TreeSet을 탐색
			for (String t : Dick) {
				if (cnt == Find - 1) {
					sb.append("#" + TC + " " + t);
					System.out.println(sb.toString());
				}
				cnt++;
			}
		}
		br.close();
	}
}