[백준] 9996번: 한국이 그리울 땐 서버에 접속하지 (Java)

1 . 문제 설명

특정 패턴과 일치하는 파일 이름을 출력하지 못하는 문제가 생겼다.

패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.

패턴에 있는 별표를 알파벳 소문자 또는 빈 문자열로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다.

ex) "abcd", "ad", "anestonestod"는 모두 패턴 "a*d"와 일치한다. 하지만, "bcd"는 일치하지 않는다.

패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성한다.

• 파일의 개수 N: 1 ≤ N ≤ 100
• 패턴
  • 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어짐
  • 문자열의 길이는 100 이하
  • 별표는 문자열의 시작과 끝에 없음
• 파일 이름
  • 알파벳 소문자로만 이루어짐
  • 길이는 100 이하
• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 패턴을 별표 기준으로 앞/뒤 부분으로 분리한다. (patternStart, patternEnd)
• N개의 파일 이름을 확인한다.
  • “DA” 출력
    • 파일 길이가 패턴을 앞 부분과 뒷 부분을 합친 길이보다 같거나 클 때
    • 파일 이름의 접두사, 접미사 부분이 패턴과 같을 때
  • 그 외, “NE” 출력

 

3. 틀린 이유

런타임 에러(StringIndexOutOfBoundsException) 발생

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 파일 개수
        String pattern = br.readLine(); // 패턴
        String patternStart = ""; String patternEnd = "";
        boolean check = false;
        for (char c : pattern.toCharArray()) {
            // 별표 전후로 문자열 분리
            if (c == '*') {
                check = true;
                continue;
            }

            if (!check) patternStart += String.valueOf(c);
            else patternEnd += String.valueOf(c);
        }

        StringBuilder sb = new StringBuilder();
        while (N-- > 0) {
            String name = br.readLine(); // 파일 이름
            String nameStart = name.substring(0, patternStart.length());
            String nameEnd = name.substring((name.length() - patternEnd.length()));

            if (patternStart.equals(nameStart) && patternEnd.equals(nameEnd)) {
                // 시작 문자가 start와 일치하고, 끝 문자가 end와 일치하면 “DA” 출력
                sb.append("DA\\n");
            }
            else sb.append("NE\\n"); // 그 외, “NE” 출력
        }
        
        System.out.println(sb);
        br.close();
    }
}

이 에러는 substring 메서드의 인덱스 범위를 벗어났을 때 발생한다.

String nameStart = name.substring(0, patternStart.length());
String nameEnd = name.substring((name.length() - patternEnd.length()));

파일 이름(name)이 별표를 제외한 패턴 길이(patternStart.length() + patternEnd.length() 또는 pattern.length()-1)보다 크거나 같아야 한다.

만약 파일 이름의 길이가 더 짧다면, 패턴과 일치하는 것이 불가능하다.

 

4. 올바른 접근 방식 및 해결 방식

파일 이름의 길이를 확인하는 조건을 추가한다.

// 길이 조건 확인 && 파일 이름의 시작과 끝 부분의 패턴과의 일치 여부 확인
if (name.length() < totalPatternLength
        && name.startsWith(patternStart) && name.endsWith(patternEnd)) {
    sb.append("NE\\n");
} else {
    sb.append("NE\\n");
}

 

5. 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 파일 개수
        String pattern = br.readLine(); // 패턴
        
        // 별표 전후로 시작&끝 패턴 분리
        int starIndex = pattern.indexOf('*');
        // String[] split = pattern.split("\\\\*");
        String patternStart = pattern.substring(0, starIndex);
        String patternEnd = pattern.substring(starIndex + 1);
        int totalPatternLength = pattern.length() - 1;

        StringBuilder sb = new StringBuilder();
        while (N-- > 0) {
            String name = br.readLine(); // 파일 이름

            // 길이 조건 확인 && 파일 이름의 시작과 끝 부분의 패턴과의 일치 여부 확인
            if (name.length() < totalPatternLength
                    && name.startsWith(patternStart) && name.endsWith(patternEnd)) {
                sb.append("NE\\n");
            } else {
                sb.append("NE\\n");
            }
        }

        System.out.println(sb);
        br.close();
    }
}

시간복잡도: $O(N*M)$ - N: 파일 개수, M: 파일 이름의 길이, 패턴의 길이는 M보다 작으므로 상수 취급

 

6. 분석 및 참고사항

• 길이를 확인하는 것을 잊지 않기
• 문자열 메서드
  • `split()`
    • 특정 구분자(delimiter)를 기준으로 문자열을 여러 부분으로 나눈다.
    • `String[]` 배열을 반환한다.
  • `indexOf()`
    • 특정 문자 또는 문자열이 처음 나타나는 위치(인덱스)를 찾는다.
    • int (인덱스)를 반환하며, 찾지 못하면 -1을 반환한다.
  • `startsWith()`
    • 문자열이 특정 접두사(prefix)로 시작하는지 확인한다.
    • boolean (true 또는 false)을 반환한다.
  • `endsWith()`
    • 문자열이 특정 접미사(suffix)로 끝나는지 확인한다.
    • boolean (true 또는 false)을 반환한다.
• `String[] split = pattern.split("*")`로 사용할 수 없는 이유
  • `split()` 메서드의 인자는 정규표현식을 받는다. 정규표현식에서 `*`는 “앞 문자가 0번 이상 반복”된다는 의미의 수량자(Quantifier)로 사용된다. 예를 들어, `“a*”`는 `“a”`, `“aa”`, `“aaa”`, …와 일치한다. 따라서 `"a*b".split("*")`와 같이 사용하면 자바의 정규표현식 엔진은 `*`를 일반 문자가 아닌 특수한 의미로 해석하려고 한다. `split()`은 `*` 앞뒤에 빈 문자열이 있다고 간주하여 `a`와 `b`를 제대로 분리하지 못하게 된다.
  • `"*"`를 일반 문자 그대로 사용하려면, 정규표현식에서 특별한 의미를 가진다는 것을 알려주기 위해 이스케이프(escape) 처리를 해줘야 한다. 자바 문자열에서 이스케이프 문자는 `\\`이므로, `"*"`를 이스케이프하면, `split("\\\\*")`가 된다. 첫 번째 `\\`는 자바 문자열에서 `\\` 자체를 의미하고, 두 번째 `\\`는 정규표현식에서 `*`를 이스케이프하는 역할을 한다.
  • ⇒ `String[] split = pattern.split("\\\\*")`
• 정규표현식에서 특별한 의미를 가지는 문자들
  • `*` : 앞 문자가 0번 이상 반복
  • `[]` : 문자 클래스 (괄호 안의 문자 중 하나)
  • `()` : 캡처 그룹
  • `{}` : 반복 횟수 지정
  • `?` : 앞 문자가 0 또는 1번 반복
  • `+` : 앞 문자가 1번 이상 반복
  • `|` : 논리적 OR
  • `^` : 문자열의 시작
  • `$` : 문자열의 끝
  • `.` : 모든 문자 (줄 바꿈 제외)
  • `\\` : 이스케이프 문자
  • 이러한 문자를 `split()`의 구분자로 사용하려면, 모두 `split("\\\\문자")`와 같이 이스케이프 처리를 해야 한다.