[Algorithm] 그리디 알고리즘

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 그리디 알고리즘 (탐욕법)

개념

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 대표적인 알고리즘으로는 "거스름돈" 문제가 있다

- 항상 최적의 값을 보장하는 것은 아니지만 코딩테스트에서 출제하는 문제는 최적의 해를 보장하는 경우로 출제된다

문제

1543번: 문서 검색

 

 

- 첫째 줄이 문서, 둘째 줄이 검색하고 싶은 단어이다.

- 검색하고 싶은 단어가 문서에 몇 개나 있는지 세는 프로그램이다

- 그리디 알고리즘이 사용된 건지는 잘 모르겠다

---

✨ 풀이 - Java

import java.io.*;
import java.util.StringTokenizer;

public class BOJ_1543 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String findStr = br.readLine();
        String str = br.readLine();

        int size = str.length(); // 주어진 단어의 길이
        int count = 0; // 단어 개수

        // 중복 방지를 위해 str의 길이만큼 !로 치환
        // ex) abababab -> !!!b!!!b
        findStr = findStr.replace(str, "!".repeat(str.length()));

        for (int i=0; i<findStr.length(); i++) {
            if (findStr.charAt(i) == '!')
                count += 1;
        }

        // !의 개수 / 단어 길이
        System.out.println(count/size);
    }
}

 

- 중복 방지를 위해 str의 길이만큼 !로 치환했다

- ex) abababab -> !!!b!!!b

- str이 찾고자 하는 단어이기 때문에 replace() 를 활용해 문서에서 str이 있는 곳을 str의 길이만큼 !로 치환해줬다.

- !의 개수 / 단어의 길이를 함으로써 몇 번 단어가 나왔는지 값을 출력했다

- BufferedWriter은 쓰지 않았는데... 지우는 걸 깜빡했다

---

✨ 참고 자료

https://jellili.tistory.com/23