Substring Comparisons (부분 문자열 비교) Java

hackerrank 에서 출제된 문제입니다.

 

 Lexicographical Order (사전순 정렬)

    A < B ... < Y < Z < a < b < ... < y < z

 

문자열 S, 정수 K가 주어지면, 문자열을 정수 K만큼의 길이로 자르고 사전순정렬을 수행하십시오.

그 다음 가장 첫번째와 마지막 문자열을 반환하십시오.

 

매개변수

• String s : 문자열
• int k : 찾을 부분의 문자열 길이

반환

• 첫번째 문자열 + "\n" + 두번째 문자열

제약 조건

• 1 <= s <= 1000
• 문자열 s는 알파벳 대.소문자 [a-zA-Z]

 

입력 예시 (Sample Input)

String s = "welcometojava";
int k = 3;
getSmallestAndLargest(s, k);

 

출력 예시 (Sample Output)

ava
wel

 

해설 

String s = "welcometojava" , k = 3 :

문자열 s를 k 단위로 잘라내고, 사전순으로 정렬하면 다음과 같습니다.

["ava", "com", "elc", "eto", "jav", "lco", "met", "oja", "ome", "toj", "wel"]

 

그런 다음 첫번째 문자열과 마지막 문자열을 개행문자로 구분된 값으로 반환합니다

( "ava" + "\n" + "wel" )

 

 

먼저 문제를 분석해보겠습니다.

1. 문자열 s를 정수 k 단위로 분할한다.
2. 사전순 정렬을 기준으로, 가장 첫번째와 마지막 문자열을 반환한다.

 

문자열 s와 정수 k를 매개변수로 받는 메소드 입니다.

 

public static String getSmallestAndLargest(String s, int k) {
    String smallest = "";
    String largest = "";

    return smallest + "\n" + largest;
}

 

 

제일 먼저 해야할 것은 문자열 분할 작업입니다.

해설의 예시는 사전정렬된 배열로 다음과 같은 규칙성을 띄고 있습니다.

String s "welcometojava" :

    wel => ecl => lco => com... ava

 

분할을 할 때마다, 한글자씩 뒤로 가고 있는것 입니다.

이것은 반복문과, String.substring 메소드를 사용해서 해결할 수 있습니다.

public static String getSmallestAndLargest(String s, int k) {
    String smallest = "";
    String largest = "";
    
    int range = s.length() - k;
    for (int i = 0; i <= range; i++) {
    	String subStr = s.substring(i, i + k);
        System.out.print(subStr + " ");
    }

    return smallest + "\n" + largest;
}

출력 결과 :

wel elc lco com ome met eto toj oja jav ava

 

 

다음은 사전순으로 첫번째와 마지막 문자열을 반환해야합니다.

 

String.compareTo() 메소드를 사용하여 사전상 순서로 두 문자열을 비교할 수 있습니다.

compareTo() 메소드는 2개의 값(String은 사전상 순서)을 비교하여 

작을 경우 : 음수

같을 경우 : 0

클 경우    : 양수를 반환합니다.

public static String getSmallestAndLargest(String s, int k) {
    String smallest = "";
    String largest = "";
    
    int range = s.length() - k;
    for (int i = 0; i <= range; i++) {
        String subStr = s.substring(i, i + k);

        if (smallest.compareTo(substr) > 0)
            smallest = substr;

        if (largest.compareTo(substr) < 0)
            largest = substr;
    }
    return smallest + "\n" + largest;
}

출력 결과 :

wel

 

왜 이런 결과가 나오는 것일 까요?

smallest의 초기 값은 "" 공백 문자열입니다.

매번 공백 문자열과 분할한 3글자의 문자열을 비교하고 있기 때문에,

smallest 변수는 한 번도 값을 할당받지 못한것입니다.

 

smallest의 초기 값은 공백 문자열이 아닌, 제일 처음 잘라낸 단어가 적합해 보입니다.

추가적으로 largest 변수에도 똑같은 초기 값을 할당함으로써, 반복문의 수행회수를 1번 줄일 수 있습니다.

public static String getSmallestAndLargest(String s, int k) {
    String smallest = s.substring(0, k);
    String largest = smallest;
    
    int range = s.length() - k;
    for (int i = 1; i <= range; i++) {
        String subStr = s.substring(i, i + k);

        if (smallest.compareTo(subStr) > 0)
            smallest = subStr;

        if (largest.compareTo(subStr) < 0)
            largest = subStr;
    }
    return smallest + "\n" + largest;
}

출력 결과 :

ava

wel

 

이 문제는

String 배열과 Arrays.sort()

List와 Collections.sort()를 사용해서 간단히 해결할 수 있습니다.

여러분도 구현 해보세요.

 

출제된 문제의 제약조건에는

"문자열 s를 k로 잘라냈을 때, 중복된 단어는 없다" 라고 명시되어 있지 않으므로

SortedSet을 구현한 자료구조를 사용해서는 안됩니다.