[Java String Compare] Lexicographically Smallest and Largest Substrings

난이도: ★★☆☆☆ • solved on: 2025-10-17

---

문제 요약

• 문제 유형: 문자열 처리, 구현
• 요구사항:
  문자열 s에서 길이 k인 모든 연속된 부분 문자열(substring)을 추출하고,
  그중 사전 순으로 가장 작은 문자열(smallest) 과 가장 큰 문자열(largest) 를 출력해야 한다.

---

사용 개념

1. 자료구조

   • String — 불변(immutable) 문자열로, substring()을 통해 부분 문자열 생성
   • ArrayList 또는 배열 — 추출한 substring들을 저장하는 용도 (단, 공간 낭비 방지를 위해 직접 비교 가능)

2. 알고리즘/기법

   • 문자열 순회 (sliding window)
   • 사전순 비교 (compareTo() 메서드)

3. 핵심 키워드

   • lexicographical order (사전순 정렬)
   • substring windowing
   • compareTo()

---

풀이 아이디어

1. 문제 분해

   • s의 길이가 n, 부분 문자열 길이가 k라면
     가능한 substring 개수는 n - k + 1개이다.
   • s.substring(i, i + k)를 이용해 모든 substring 추출.
   • 각 substring을 lexicographical order 로 비교하며 smallest/largest 갱신.

2. 핵심 로직 흐름

   smallest = s.substring(0, k)
   largest = s.substring(0, k)
   
   for i in [1, n - k]:
       sub = s.substring(i, i + k)
       if sub.compareTo(smallest) < 0:
           smallest = sub
       if sub.compareTo(largest) > 0:
           largest = sub

3. 예외 처리

• s.length() == k인 경우: substring은 하나뿐 → smallest = largest = s
• k > s.length()인 입력은 주어지지 않음 (문제 보장)

---

개선된 정답 코드

import java.util.*;

public class Solution {

    public static String getSmallestAndLargest(String s, int k) {
        String smallest = s.substring(0, k);
        String largest = s.substring(0, k);
        
        for (int i = 1; i <= s.length() - k; i++) {
            String sub = s.substring(i, i + k);
            if (sub.compareTo(smallest) < 0) smallest = sub;
            if (sub.compareTo(largest) > 0) largest = sub;
        }
        
        return smallest + "\n" + largest;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        int k = scan.nextInt();
        scan.close();
      
        System.out.println(getSmallestAndLargest(s, k));
    }
}

---

시간·공간 복잡도

• 시간 복잡도: O(N × K)
  (substring() 생성이 O(K), 총 N−K+1회 반복)
• 공간 복잡도: O(K)
  (현재 substring 및 smallest/largest만 유지)

---

어려웠던 점

• substring의 크기 단위로 문자열을 자를 때,
  단순히 i += k로 진행하면 겹치는 부분이 누락되어 오답이 됨.
• i/k 등 몫 연산으로 인덱스를 관리하다가 의도와 다르게 substring이 짤려버림.
• 문제의 의도는 “겹치는 모든 substring”을 비교하는 것이므로, i를 1씩 증가시켜야 함.

---

배운 점 및 팁

• 문자열의 사전순 비교는 compareTo() 가 핵심이다.
  직접 charAt(0)으로 비교하면 두 번째 문자 이후의 순서 비교가 누락된다.
• substring 전체를 배열에 저장하지 않아도, smallest/largest만 유지하면 메모리를 아낄 수 있다.
• s.length() - k + 1개만 생성하면 되므로, index 범위를 정확히 지정하는 것이 중요하다.

---

참고 및 링크

• 문제 링크: https://www.hackerrank.com/challenges/java-string-compare/problem
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • BOJ 1316 - 그룹 단어 체커 — 문자열 순회와 비교 로직 유사

• 확장 문제 (GPT 추천) :

  • 문자열 내 모든 부분 문자열 중 중복 없이 사전순 정렬 후 K번째 문자열 찾기
  • Sliding window를 이용한 “가장 큰 수” 또는 “최소 윈도우 부분 문자열” 문제