백준 1157번 단어공부 풀이

문제는 위와같다.

입력의 크기가 백만인데 시간제한이 2초다. 시간복잡도가 대충 O(n) ~ O(nlogn) 정도면 무난하게 통과할 것이라 생각하고 알고리즘을 구현해 보았다.

우선, 각 알파벳이 문장내에서 몇번 쓰였는지 횟수를 구해야 한다. 그래야 가장 많이 사용된 알파벳을 구할 수 있을테니까.

즉, 문장 하나를 문자단위로 탐색해야 하므로  O(n)의 복잡도가 걸리고, 이를 26개의 알파벳마다 모두 반복해야 한다.

입력이 낮을 때는 26이라는 상수가 의미가 있겠지만, 여기선 최대 입력이 백만이므로 의미가 없다.

 

각 알파벳이 문장 내에서 몇번 쓰였는지 확인 했으므로 이제 그 중에서 최댓값을 구해야 한다.

단, 이때 최댓값이 여러개 존재하는지도 확인해야 한다. 최대값이 여러개일 경우 ?를 출력하라고 적혀있기 때문.

 

// 최댓값을 구하며 최댓값이 여러번 등장하는 지 판별하는 코드
int max = 0;
boolean flag = false;
for(int i=1;i<=25;i++) {
	if(counts[max]<counts[i]) {
		max = i;
		flag = false;
	}else if(counts[max]==counts[i]) {
	flag = true;
	}
}

일반적인 최댓값 구하는 코드에 flag를 추가하여 최댓값이 여러번 등장하는 경우를 구분할 수 있게 하였다.

최댓값을 구하는 알고리즘역시 순차탐색이므로 O(n)의 복잡도를 가진다.

따라서 전체 알고리즘의 복잡도는 O(n) 이다.

전체 코드는 아래와 같다.

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        str = str.toUpperCase();
        int counts[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        for(char a='A';a<='Z';a++) {
        	for(int i=0;i<str.length();i++) {
        		if(str.charAt(i)==a) {
        			counts[a-'A']++;
        		}
        	}
        }
        int max = 0;
        boolean flag = false;
        for(int i=1;i<=25;i++) {
        	if(counts[max]<counts[i]) {
        		max = i;
        		flag = false;
        	}else if(counts[max]==counts[i]) {
        		flag = true;
        	}
        }
        char a ='A';
        if(!flag) {
        	System.out.println((char)(a+max));
        }else {
        	System.out.println("?");
        }
        
    }
}