백준 문제 풀이 - 심화 1 단계 - 1157번 단어 공부 (브론즈 1)

알파벳 대소문자로 된 단어가 주어졌을 때, 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하는 문제이다.

 

제한이 좀 있는데, 알파벳의 대 소문자를 구분하지 않으며, 가장 많이 사용된 알파벳을 대문자로 출력하여야 한다.

주어진 단어는 최대 100만의 길이를 가질 수 있다.

또한 가장 많이 사용된 알파벳이 여러 개 존재하는 경우 ? 를 출력한다.

 

처음 문제를 풀때에는 찾을 문자열의 갯수를 리턴하는 메서드를 만들어, 문자열의 길이만큼 반복하며 최대 값의 문자를 찾는 방법으로 구상을 하였다.

그래서 메서드를 filter를 사용한 람다식으로 구성하였는데 코드는 다음과 같다.

 

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

class Main{
    public static String s;
    public static char result;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine().toUpperCase();
        br.close();

        long max = 0;
        for(int i = 0; i< s.length();i++){
            if (s.charAt(i) == result) {
                result = '?';
                continue;
            } else if (countChar(s,s.charAt(i)) > max) {
                max = countChar(s, s.charAt(i));
                result = s.charAt(i);
            }
        }
        System.out.println(result);

    }

    public static long countChar(String s, char targetChar) {
        return s.chars().filter(c -> c == targetChar).count();
    }
}

로직을 간단하게 보면, 입력받은 문자열 만큼 반복하며 찾을 문자를 메서드로 넘겨 몇번 나오는지 계산하고 max 값과 비교하여 더 많이 나왔으면 해당 문자를 출력하는 형태이다.

그런데 해당 코드를 제출하자 시간 초과라는 결과를 얻었다.

따라서, 좀더 속도를 높이기 위해 filter 메서드가 아니라 for 문으로 로직을 변경하였다.

(Stream보다 반복문이 조금 더 속도가 빠르다)

 

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

class Main{
    public static String s;
    public static char result;
    public static int max,cnt;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine().toUpperCase();
        br.close();

        for(int i = 0; i< s.length();i++){
            cnt = countChar(s, s.charAt(i));
            if (s.charAt(i) == result) {
                continue;
            } else if (cnt == max) {
                result = '?';
            } else if (cnt > max) {
                result = s.charAt(i);
                max = cnt;
            }
            }

        System.out.println(result);
        }


    public static int countChar(String s, char target) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == target) {
                result++;
            }
        }
        return result;
    }
}

로직은 동일한데 countChar 메서드에 문자열 s 와 찾을 문자 target을 던지고 해당 문자열에 target이 몇번 나오는지 리턴 받아 max 값과 비교하여 더 큰 값을 출력한다.

그런데 여전히 결과를 제출하니 시간이 초과되었다.

 

잘 생각해보니 내가 짠 코드는 2중 포문의 형태인데 전체 문자열의 길이만큼 반복하니 만약 문자열의 길이가 100만이면 100만 * 100만번 도는 형태이다.

그렇기에 아마 시간이 초과되지 않았나 생각이 되었다.

 

그래서 아예 다른 방법으로 생각을 하였는데, 결국 우리가 찾는 것은 문자가 문자열에서 몇번이 반복되었는지를 찾는 것이므로 그냥 아스키 코드값 만큼의 배열을 만들어 두고 해당 배열에 각 문자 위치에 반복 수를 넣은 후 최대 값과 비교하는 것이 더 나을것 같았다.

이렇게 하면 문자열의 길이만큼은 한번만 돌아도 되므로 속도 면에서 훨씬 나아질 것이라고 생각하였다.

따라서 다음과 같이 코드를 변경하였다.

 

import java.io.*;

class Main{
    public static String s;
    public static char result;
    public static int max;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine().toUpperCase();
        br.close();

        int[] nums = countChar(s);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                result = (char) i;
            } else if (max == nums[i] && result != (char) i) {
                result = '?';
            }
        }

        System.out.println(result);
    }


    public static int[] countChar(String s) {
        int[] result = new int[256];
        for (char c: s.toCharArray()) {
            result[c]++;
        }
        return result;
    }
}

int 배열 nums를 만들고 해당 배열에 아스키 코드만큼의 배열을 만든 후 문자열에 각 문자들이 얼마나 반복되는지 카운트 해두었다.

 

그 후, nums의 크기 만큼 반복하여 최대값을 출력해 낸다. 인덱스 i의 값이 곧 해당 문자의 값이므로, int값 i를 char 타입으로 변환만 해주면 완료.

이렇게 하면 원래 문자열의 길이의 제곱만큼 반복하던 것을 문자열의 길이 * 256 만큼만 반복해도 되므로 반복 숫자를 확 줄여 속도를 높일 수 있을 것이라고 생각했다.

 

결과적으로 성공적으로 코드가 제출 된 것을 확인 할 수 있었다.

 

다른 사람이 푼 것과 비교해 보았는데, 좀 괜찮아 보였던 것은 int 형태의 ArrayList에 넣어두고 Frequency로 Max와 비교한 것이 가장 심플하고 간단해 보였다.

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

public class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		ArrayList<Integer> array = new ArrayList<>(Collections.nCopies(26,0));
		
		for(int i = 0; i < s.length(); i++){
		    int tmp = (int)s.charAt(i)-65;
		    if((int)s.charAt(i) > 96)
		        tmp = (int)s.charAt(i)-32-65;
		        
		    array.set(tmp,array.get(tmp)+1);
		}
		
		int maxIndex = array.indexOf(Collections.max(array));
		
		int max = maxIndex+65;
		
	    char maxChar = (char)max;
	    
	    if(Collections.frequency(array,Collections.max(array)) > 1)
	        maxChar = '?';
	    
	    System.out.println(maxChar);
		
	}
}

이렇게 하면 전체 문자열이 int로 변환되어 ArrayList에 저장되고, 저장된 것 중 가장 큰 값을 maxIndex로 뽑아내어 다시 char 형태로 형변환 해준다.

그후 frequency를 이용해 동일한 값이 있는지 확인하고 출력하면 완료

굉장히 간단하고 심플하게 잘 구현한 코드 같다.