[백준/BOJ][Java][1543] 문서 검색

2023.08.21 - [Java] - Java String 이해

Java String 이해

 

---

 

https://www.acmicpc.net/problem/1543

1543번: 문서 검색

 

내가 푼 풀이

 

입력받은 str에서 target 글자를 자르는 방식으로 작성했습니다.

str안에 target이 처음 등장하는 인덱스와 target길이 만큼 더하기 연산해서 나온 int값을 subtring이용해서 자릅니다.

다음에 나오는 str부터는 잘려진 이후부터 검사합니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // nextLine()은 띄어쓰기를 포함한 문자열 받음
        String str = sc.nextLine();
        String target = sc.nextLine();
        int count = 0;
        // str의 내용에 target을 더이상 자를 수 없을 때까지 잘라서 개수 반환
        while(str.length() >= target.length()) {
            if (str.contains(target)) {
                // 마지막 인덱스 = str중에서 target가 처음 등장하는 인덱스 + 끝나는 곳
                int endIdx = str.indexOf(target) + target.length();
                str = str.substring(endIdx);
                count++;
            } else {
                break;
            }
        }
        System.out.println(count);
    }
}

메모리	시간	언어	코드 길이
17844KB	236ms	Java11	572B

강의 풀이

문제 : 주어진 단어가 문서에 등장하는 횟수

 

1. 문서의 첫 글자부터 순회한다.

for (int i = 0; i < doc.lenght(); i++) {
	// 문서를 훑는다
}

   2. 문서의 지금 글자부터 주어진 단어와 한글자 씩 비교한다.

for (int i = 0; i < doc.lenght(); i++) {
	for (int j = 0; j < word.length(); j++) {
    	if (doc.charAt(i+j) != word.charAt(j)) {
        	// 문서에서 i번째 인덱스부터 시작하는 단어는
            // 주어진 단어와 일치하지 않는다
        }
    }
}

for (int i = 0; i < doc.lenght(); i++) {
	boolean isMatch = true;
	for (int j = 0; j < word.length(); j++) {
    // 안쪽 반복문을 통해서 j를 통해 word와 doc의 지금 글자와 길이까지 한글자씩 비교하면서
    // 한번이라도 달랐다면 isMatch가 false로 되고, 안달랐다면 그대로 true
    	if (doc.charAt(i+j) != word.charAt(j)) {
        	isMatch = false;
            break;
        }
    }
}

for (int i = 0; i < doc.lenght(); i++) {
	boolean isMatch = true;
	for (int j = 0; j < word.length(); j++) {
	// 만약 i가 doc.length()-1이고 j가 1이면 i+j가 doc.length()랑 같은 값이 된다
    // 그러면 이때 i+j값은 doc가 가진 인덱스값을 넘어서 런타임 에러가나면서 죽어버릴것이다
    // 그래서 인덱스를 다룰때는 항상 범위 체크를 함께 해줘야한다
    	if (i + j >= doc.length() || doc.charAt(i+j) != word.charAt(j)) 
        	isMatch = false;
            break;
        }
    }
}

       3-1. 단어와 완전히 일치하면 개수를 올린다.

              해당 단어가 등장한 이후부터 2를 반복한다.

for (int i = 0; i < doc.lenght(); i++) {
	boolean isMatch = true;
	for (int j = 0; j < word.length(); j++) {
    	if (i + j >= doc.length() || doc.charAt(i+j) != word.charAt(j)) 
        	isMatch = false;
            break;
        }
    }
    if (isMatch) {
    	count++;
        // 중복되지 않는 단어를 찾는다고 했으니, 이 단어가 등장한 이후부터 검색이 되어야 한다
        // word.length()를 더해야할까?
        // word.length() -1 을 더해야할까?
        // 반복문이 끝날때마다 i를 하나씩 더해주고 있기 때문에 그걸 감안해야한다
        // ((length() - 1) + 1) 을 감안
        i += word.length() - 1;
    }
}

       3-2. 단어와 매치 되지 않았다면 다음 글자에서 2를 반복한다.

 

 

하지만 String.indexOf를 사용하면 좀 더 편리하게 풀 수 있다!

 

doc 문자열의 startIndex부터 처음으로 등장하는 word 문자열을 찾는다.
찾았다면 일치하는 시작 인덱스를 반환한다. 찾지 못했다면 -1을 반환한다.

1. 문서의 첫 글자부터 순회한다 ( startIndex = 0)

   2.  startIndex부터 단어가 처음으로 등장하는 인덱스를 찾는다.

   3-1. 찾았다면 개수를 올린다. 다음 검색부터 해당 단어가 등장하는 이후부터 찾도록 startIndex를 옮기고 2를 반복한다.

   3-2. 찾지 못했다면 검색을 종료한다.

int startIndex = 0;
int count = 0;
while (true) {
	int findIndex = doc.indexOf(word, startIndex);
    if (findIndex < 0) // 찾지 못했다면 findIndex가 -1 음수로 나올 것이다
    	break;
    startIndex = findIndex + word.length();
    count++;
}

// 강의 풀이 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String doc = sc.nextLine();
        String word = sc.nextLine();

        int count = 0
        // 어디까지 검색이 되었는지 표현 -  문서의 처음부터 시작하기 위해 0부터 시작
        int startIndex = 0;

        while (true) {
           // word라는 문자열을 찾고 싶고, startIndex의 인덱스값부터 찾아줘
            int findIndex = doc.indexOf(word, startIndex);
            if (findIndex < 0)
                break;
            count++;
            // 내가 지금 찾은 단어 뒤부터 검색하기 위함
            startIndex = findIndex + word.length();
        }
        System.out.println(count);
    }
}

메모리	시간	언어	코드 길이
17656KB	240ms	Java11	524B

 

// 강의 풀이 2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String doc = sc.nextLine();
        String word = sc.nextLine();
        // doc내부에서 word가 등장하면 전부 없애라
        String replaced = doc.replace(word, "");
        // 남아있는 길이
        int length = doc.length() - replaced.length();
        // 워드의 길이로 남아있는 길이를 나누면 , 사라진 길이에서 word가 몇번 등장했는지 알 수 있다
        // length는 word의 배수만큼 사라졌기 때문에 count는 항상 정수로 나올것이다
        int count = length / word.length();
        System.out.println(count);
    }

메모리	시간	언어	코드 길이
17744KB	236ms	Java11	402B