(Baekjoon) GreedyAlgorithm - (22) 문서 검색

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

1543번: 문서 검색

최대 2500개의 문자를 50번 확인해야된다.

for(  ){
	for(  ){
	}
}

최대 105000번을 검색해야한다. 이렇게 무식하게 검색하라고 준 알고리즘은 아닐것이라고 생각한다.

근데 그게 맞았다.

 

근데 split쓰면 바로 끝나는거 아닌가? 엥?

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 document = br.readLine();
        String search = br.readLine();
        String O[] = document.split(search);
        System.out.println(O.length-1);     

    }
}

 

당연히 답은 틀렸다. 

 

1) 공백을 포함하여 문자를 받는다. (bufferedReader 또는 nextLine() 사용)

2) 전부다 char로 쪼갠다.

3) 앞에서부터 차례차례비교하여서 문자열을 찾는다.

4) 문자열을 찾으면 문자열찾은행 다음만큼부터 계속 검색한다.

package GreedyAlgorithm;

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

public class _1543 {

    static char a[];
    static char n[];

    static int compare(int k){

        int count = 0;
        for (int i = k; i < a.length; i++) {
            if(a[i]==n[count]){
                count++;
                if(count==n.length){
                    
                    return i;

                }
                continue;
            }
            else
                break;
        }
        return -1;
    }

    
    public static void main(String args[]) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String document = br.readLine();
        String search = br.readLine();

        a = document.toCharArray();
        n = search.toCharArray();

        int c;
        int num=0;
        for (int i = 0; i < a.length ; i++) {
            
            if((c = compare(i))!=-1){
                i = c;
                num++;
            }
                
        }

        System.out.println(num);
        

    }
}

 

 

특이하게 문제의 정답률이 29%이다.

나는 생각해보니까 이거 답 맞는데? 하면서 우격다짐식으로 제출을 겁나게 했다.

아마 나처럼 계속 제출해서 틀린사람이 많아서 29%가 아닐까 싶다.

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study