[백준] 1157 단어공부

[1157] 단어 공부

__💡구현 (Implements)__
반복을 이용한 구현 (시간복잡도 고려필요)__
https://www.acmicpc.net/problem/1018

Question

문제

알파벳 대소문자로 된 단어가 주어지면,
이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오.
단, 대문자와 소문자를 구분하지 않는다.

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다.
주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다.
단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

 

Tag

구현, 문자열

---

Answer1 (./Main.java)

Map 객체의 반복문 활용 가능
lamda 에서는 외부 지역변수에 값을 대입할 수 없다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        solution();
    }

    static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine().toUpperCase();
        char[] alphabet = input.toCharArray();

        Map<String, Integer> result = new HashMap<>();
        for (char c : alphabet) {
            String cs = String.valueOf(c);
            result.put(cs, result.getOrDefault(cs, 0) + 1);
        }
        String maxAlphabet = "?";
        int maxCount = 0;
        for( Map.Entry<String, Integer> elem : result.entrySet() ){
            if (elem.getValue() > maxCount){
                maxAlphabet = elem.getKey();
                maxCount = elem.getValue();
            } else if (elem.getValue() == maxCount) {
                maxAlphabet = "?";
            }
        }
        System.out.println(maxAlphabet);
    }
}

메모리(kb)	시간 (ms)	시간복잡도
88872	464	$O(n)$

Answer2 (./Main2.java)

배열에서 값을 ++ 로 바로 올려줄 수 있다
간단한 문제에서는 map 보다 배열로 처리하는게 공간, 시간복잡도면에서 우위이다
시간복잡도는 동일하다(상수값이 적긴함)

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

public class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String text = st.nextToken().toUpperCase();
        int[] arr = new int[26];
        int max = 0;
        char str = '?';

        for (int i = 0; i < text.length(); i++) {
            int count = ++arr[text.charAt(i) - 65];
            if (max < count) {
                max = count;
                str = text.charAt(i);
            } else if (max == count) {
                str = '?';
            }
        }
        System.out.println(str);
    }
}

메모리(kb)	시간 (ms)	시간복잡도
21144	268	$O(n)$

---

Error

특정 코드에서는 시간복잡도로 인해 input 과 제한시간에 걸려 오답이 발생할 수 있다.
아래와 같은 다른 사용자의 코드는 단어의 길이 N(1,000,000) 일때
시간복잡도 O(N^2) 을 가져 연산 시간초과가 발생함

• 시간초과 예시코드 - 출처

public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String str = scan.next();
    str = str.toUpperCase();
    int [] arr = new int[str.length()];
    int maxNum = 0;
    char maxStr = str.charAt(maxNum);

    for(int i = 0; i<arr.length; i++){
        for(int j = 0;j<arr.length;j++){
            if(str.charAt(i)==(str.charAt(j))){
                arr[i] ++;
            }
        }
        if(arr[i]>arr[maxNum]){
            maxNum = i;
            maxStr = str.charAt(maxNum);
        }else if(arr[maxNum]==arr[i] && maxNum != i) {
            if(maxStr != str.charAt(i))
                maxStr = '?';
        }
    }
    System.out.println(maxStr);
}