/<BOJ 백준 15904번> UCPC는 무엇의 약자일까? - Java

 

문제 15904번 : UCPC는 무엇의 약자일까?

문제 해설

전형적인 그리디 알고리즘 문제이다. 입력받은 문자열에 순서대로 U, C, P, C가 존재하는지 확인만 하면 풀 수 있는 문제이다. 이를 코드로 나타내면 다음과 같다.

 

public boolean isUCPC(String string) {
    int index = 0;

    for(char c : string.toCharArray()) {
        if(c == "UCPC".charAt(index)) {
        index++;
        	if(index == 4) {
            	return true;
        	}
        }
    }
    return false;
}

 

string을 하나의 문자로 쪼개어 나눈다. 해당 문자가 문자열 "UCPC"의 index에 해당하는 문자와 일치하면 index를 1 추가하여 비교하는 방식이다. 해당 코드는 c의 개수, 즉 string의 크기에 의해 시간복잡도가 결정된다. string의 크기가 N이라면 시간복잡도 O(N)을 갖는다.

코드

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

public class Main {

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String string = br.readLine();

        if(isUCPC(string)) {
        	System.out.println("I love UCPC");
        }
        else {
        	System.out.println("I hate UCPC");
        }
    }

    public boolean isUCPC(String string) {
    	int index = 0;

    	for(char c : string.toCharArray()) {
    		if(c == "UCPC".charAt(index)) {
    			index++;
    			if(index == 4) {
        			return true;
    			}
    		}
    	}
    	return false;
    }

    public static void main(String[] args) throws Exception {
    	new Main().solution();
    }
}