[2025 1학기 알고리즘 스터디] 남윤찬 #5주차

5주차는 문자열을 다루는 문제들이 주제였습니다.

 

부분 문자열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputString;

        while ((inputString = br.readLine()) != null) {
            StringTokenizer st = new StringTokenizer(inputString);
            comp(st.nextToken(), st.nextToken());
        }
    }

    public static void comp(String s, String t) {
        int idx = 0;
        for (int k = 0; k < t.length(); k++) {
            if (s.charAt(idx) == t.charAt(k)) {
                idx++;
            }
            if (idx == s.length()) break;
        }

        if (idx == s.length()) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

어떻게 보면 그리디 알고리즘?인 간단한 문자열 비교하기. idx를 하나씩 늘리면서 t와 s의 알파벳을 순차적으로 비교하면 쉽게 구할 수 있는 문제이다. 그런데 계속 NoSuchElement 에러가 떴는데, 이게 StringTokenizer에 null이 들어가면 뜨는 건지, comp 함수에 넣을 때 null이면 뜨는 건지 모르겠다;

---

문서 검색

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String doc = br.readLine();
        String word = br.readLine();

        int docLength = doc.length();
        int wordLength = word.length();

        doc = doc.replace(word, "");
        System.out.println((docLength - doc.length()) / wordLength);
    }
}

처음에는 찾으려는 단어를 처음 주어지는 문자열에서 지우며 카운트를 늘려나가려는 방식으로 하려했는데, 더 간결하다는 생각이 드는 다른 방식을 찾게 되었다. replace()를 해서 찾으려는 단어를 모두 지우고나면 남는 문자열의 길이를 기존의 문자열의 길이에서 빼고 찾으려던 단어의 길이로 나누면 문자열에 단어가 총 몇 개가 들어가는지 알 수 있다. 이 방식이 반복문을 사용하는 것보다 간단하게 처리하는 방법이 될 수 있다고 생각했다.

---

접미사 배열

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String s = scanner.nextLine();
        LinkedList<String> words = new LinkedList<>();
        words.add(s);
        while (s.length() > 0) {
            s = s.substring(1);
            words.add(s);
        }
        words.sort(null);
        words.pollFirst();
        for (String k : words) {
            System.out.println(k);
        }
    }
}

문자열 비교만 하면 되는 문제여서 혹시나 해서 LinkedList의 메서드 중 sort를 써봤는데 생각보다 더 간단하게 해결되었다.