[백준알고리즘/문자열] 1157번 문제 : 단어 공부(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 7단계 단어 공부를 풀어봤습니다

이번 문제는 답은 금방 나왔는데 해결 방법이 맘에 들지 않아서 좀 더 최적화를 위해 고민을 많이 한 문제였습니다

제가 푼 여러가지 방법에 대해서 설명하겠습니다

 

---

문제 링크입니다

https://www.acmicpc.net/problem/1157

1157번: 단어 공부

 

문제

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

 

입력

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

 

출력

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

 

 

---

 

 

문제 풀이

첫 번째 방법입니다

풀자마자 바로 제출한 정답입니다

풀고나서도 정리가 잘 안 됐어... ㅠㅜ 하지만 정답은 맞아요

아스키코드를 이용하여 알파벳에 해당하는 배열을 더해주고 제일 많이 쓴 알파벳을 구하는 방식입니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// 문자열을 입력 및 알파벳 배열 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		String str = br.readLine();
		
		int[] Ascii = new int[26];
		
		// 반복문을 사용하여 알파벳에 해당하는 배열을 입력
		for(int i = 0; i < str.length(); i++)
		{
			int comp;
			
			if(str.charAt(i) - 65 <= 26)
				comp = str.charAt(i) - 65;
			else
				comp = str.charAt(i) - 97;
			
			Ascii[comp]++;
		}
		
		// Max갯수를 계산
		int Max = 0;		
		for(int i = 0; i < 26; i++)
		{
			if(Max < Ascii[i])
				Max = Ascii[i];
		}
		
		// Max갯수가 몇 개인지 계산
		int count = 0;
		int Max_Ascii = 0;		
		for(int i = 0; i < 26; i++)
		{
			if(Max == Ascii[i]) {
				count++;
				Max_Ascii = i;
			}
		}
		
		// Max갯수가 2이상이면 "?" 출력, 1개면 알파벳 출력
		if(count > 1)
			System.out.println("?");
		else
			System.out.println((char) (Max_Ascii + 65));
	}
}

 

---

두 번째 방법입니다

 첫 번째 방법에서 조금 더 다듬었습니다

 첫 번째 방법에서는 for문을 3번 썼는데 2번째 for문에서 최대값을 구함과 동시에 결과 알파벳을 구하는 방식으로 바꿨습니다

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

public class Main2 {
	public static void main(String[] args) throws IOException {
		// 문자열을 입력 및 알파벳 배열 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		String str = br.readLine();
		
		int[] Ascii = new int[26];

		// 반복문을 사용하여 알파벳에 해당하는 배열을 입력
		for(int i = 0; i < str.length(); i++)
		{
			int comp;
			
			if(str.charAt(i) - 65 <= 26)
				comp = str.charAt(i) - 65;
			else
				comp = str.charAt(i) - 97;
			
			Ascii[comp]++;
		}
		
		// Max계산 및 가장 많이 쓴 알파벳을 구함
		int Max = 0;
		int Max_Ascii = 0;
		
		for(int i = 0; i < 26; i++)
		{
			if(Max < Ascii[i]) {
				Max = Ascii[i];
				Max_Ascii = i + 65;
			}
			else if(Max == Ascii[i])
				Max_Ascii = 63;
		}
		
		// 결과 출력
		System.out.println((char) Max_Ascii);
	}
}

 

---

마지막 방법입니다

참고 : https://www.acmicpc.net/source/26831159

위의 방법을 참고해서 구했습니다

알파벳을 입력할 때 while문을 사용 Enter키를 입력하면 while문을 종료하도록 하고, 알파벳배열에 ++를 해줍니다

제일 많이 쓴 알파벳을 구하는 방식은 두 번째 방법과 동일합니다

import java.io.IOException;

public class Main3 {
	public static void main(String[] args) throws IOException {
		// 알파벳 배열 및 비교 변수 선언
		int[] alphabet = new int[26];
		int comp;
		
		// Enter가 입력되면 while문 종료
		while((comp = System.in.read()) >= 'A' )
		{
			// 알파벳 배열에 갯수 입력
			if(comp >= 'a') alphabet[comp - 'a']++;
			else alphabet[comp - 'A']++;
		}
		
		// 최대값 및 결과 변수 선언
		int max = 0;
		char output = 0;
		
		// 제일 많이 사용한 알파벳 계산
		for(int i = 0; i < 26; i++)
		{
			if(max < alphabet[i]) {
				max = alphabet[i];
				output = (char) (i + 'A');
			} else if(max == alphabet[i]) output = '?';
		}
		
		// 결과 출력
		System.out.print(output);
	}
}

 

여기까지 제가 풀은 세 가지 방법이었습니다

 

---

속도 비교

위의 풀은 순서대로 1, 2, 3번입니다

당연히 3번 방식이 메모리와 시간이 제일 적게 나왔습니다

의외인 것은 2번 방식보다 1번 방식이 더 빠르다는 것이네요...

메모리는 2번이 더 적을 것이라 생각했는데 1번이 시간이 더 적게걸릴줄은 생각도 못 했네요 ㅎㄷ

 

이상 백준 알고리즘 1157번 단어 공부를 풀은 내용이었습니다

 

다음 문제 : 

이전 문제 : 2021.05.15 - [알고리즘/알고리즘JAVA] - [백준알고리즘/문자열] 2675번 문제 : 문자열 반복(자바/JAVA)