[백준알고리즘-JAVA]1157번 풀이(단어공부)

안녕하세요

인포돈 입니다.

백준 알고리즘 1157번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1157 (단어 공부)

 

문제

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

입력

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

출력

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

입력 예시 -1

Mississipi

출력 예시 -1

?

입력 예시 -2

zZa

출력 예시 -2

 

Z

입력 예시 -3

z

출력 예시 -3

Z

입력 예시 -4

baaa

출력 예시 -4

A

 

실패 코드

import java.io.*;
import java.util.HashMap;
import java.util.Map.Entry;

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] ch = br.readLine().toUpperCase().toCharArray();
		HashMap<Character, Integer> map = new HashMap<>();
		int max = 0;
		char sus_c = ' ';
			
		for(char c : ch) {
			if(map.containsKey(c)) {
				map.replace(c, map.get(c)+1);
			}else {
				map.put(c, 1);
			}
		}

		 for(Entry<Character, Integer>  entry : map.entrySet()) {
			 
			 if(max < entry.getValue()) {
				 max = entry.getValue();
				 sus_c = entry.getKey();
			 }
			 else if( max == entry.getValue()) {
				 sus_c = '?';
				 break;
			 }
		 }
		 br.close();
		 System.out.println(sus_c);
		}	
		}

성공코드

import java.io.*;
import java.util.HashMap;
import java.util.Map.Entry;

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] ch = br.readLine().toUpperCase().toCharArray();
		HashMap<Character, Integer> map = new HashMap<>();
		int max = 0;
		char sus_c = '?';
		int cnt = 0;
			
		for(char c : ch) {
			if(map.containsKey(c)) {
				map.replace(c, map.get(c)+1);
			}else {
				map.put(c, 1);
			}
		}
		
		for(char c : map.keySet()) {
			if(max < map.get(c))
				max=map.get(c);
		}
		
		 for(Entry<Character, Integer>  entry : map.entrySet()) {
			 if(entry.getValue().equals(max)) {
				 sus_c = entry.getKey();
				 cnt++;
			 }
		 }
		 br.close();
		 System.out.println(cnt > 1 ? "?" :sus_c);
		 
		}
		}

 

사실 실패 코드도 정상적으로 돌아가기는 합니다. (제가 찾지 못한 반례가 있을 수도 있습니다.) 그런데 백준 알고리즘에 올려보면, 계속 틀렸다고 나오네요... (해당 사항에 대해 정확히 파악한 후 글을 수정하겠습니다!)

---

우선은 성공 코드로 분석해 드리겠습니다. 물론 해당 문제를 알파벳 개수인 26개의 배열을 만들어서 푸는 방법도 있지만, 이번에는 Hashmap에 대해서 알아보고자 Hashmap을 사용해보고자 했습니다.

 

Hashmap은 기본적으로 key, value형태로 이루어져 있습니다.

 

성공코드의 기본적인 알고리즘 흐름도를 본다면 아래와 같습니다.

입력받은 문자열 대문자로 바꿔주기 -> 대문자 문자열을 hashmap에 넣기 (단, 중복이 되면 count를 하나 올린다.) -> 그곳에서 최대로 많이 나온 max를 int형으로 찾는다. -> 찾은 max값을 통해 hashmap에서 그 key값을 꺼내와 출력한다.

 

사실 가장 생각이 필요한 부분은 마지막 for 구문일 것입니다.

일반 hashmap에서 key값을 가져올 수 없기 때문에 entry라는 객체를 사용해야 합니다. 이 entry라는 객체는 hashmap에 있는 하위 객체로 볼 수 있습니다. 

 

 for(Entry<Character, Integer>  entry : map.entrySet()) {
			 if(entry.getValue().equals(max)) {
				 sus_c = entry.getKey();
				 cnt++;
			 }

해당 코드를 자세히 보면 for each문을 이용해 하나의 값을 가져옵니다. (순서는 저희가 hashmap을 넣은 순서대로 나오게 됩니다.) 하나하나 값들을 getValue로 가져와 max값과 비교합니다.

 

만약 같다면, 그게 바로 처음에 입력받은 문자 열중 가장 많이 쓰인 알파벳이겠죠?

 

그 알파벳을 sus_c 변수에 넣어줍니다. 단, cnt + 1을 하면서 말이죠 (왜냐면 max값이 하나가 아니면 "?"를 출력해야 되기 때문이죠)

 

System.out.println(cnt > 1 ? "?" :sus_c);

이러한 반복문을 모두 순회한 뒤 마지막으로 출력을 할 때 삼항 연산자를 이용해 간단히 출력해 주었습니다.

(삼항 연산자를 간단히 말로 표현하면,  "cnt가 1보다 크면 "?"를 출력하고, 아니면 sus_c를 출력해라"라는 의미입니다.)

 

해당 문제에서 제가 푼 방식대로 풀려면 크게 Hashmap, Entry, for each, 삼항 연산자 이 4가지를 알고 있다면, 쉽게 풀이하실 수 있을 것입니다.!!

---

스스로 검색을 통해서 해당 방법의 풀이를 찾는 것도 좋겠지요.

만약 내가 hashmap에서 key값을 가져오고 싶다면 "How to get key in hashmap in java" 뭐 이런 식으로 검색을 하시면, 막대한 양의 자료들을 보실 수 있으실 겁니다. 다양한 방법으로 key값을 가져올 수 있고 그중에 가장 마음에 드는 방식으로 진행하실 수도 있고요.

 

---

앞서 말했듯이 실패 코드 또한 hashmap을 통하여 풀이한 것이지만, 출력을 정확히 되지만, 백준 알고리즘에 제출하면 틀렸다는 답변이 옵니다. 이유를 아직 잘 몰라 찾고 있는 중이어서 발견한다면 글을 수정해서 올리겠습니다!