[Baekjoon] 21030_Frequent Alphabet

문제(출처: https://www.acmicpc.net/problem/21030)

---

< Frequent Alphabet >

 

문제 풀이 

 

i번째 문자가 S의 i번째 또는 T의 i번째 문자로 구성된 새 비밀번호를 통해 얻을 수 있는 최다 점수를 구해야 한다.

 

1) 재귀를 사용하여 만들 수 있는 모든 새 비밀번호를 구해 최다 점수를 구했다 -> 시간 초과

2) 문자열을 이중탐색하며 현재 위치에서 같은 문자를 찾아 최다 점수를 구했다 -> 시간 초과

3) 문자열을 탐색하며 HashMap에 문자의 등장 횟수를 구했다. -> 통과

 

my solution (Java)

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

public class _21030_ { // Frequent Alphabet

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(bf.readLine());

		String S = bf.readLine();
		String T = bf.readLine();

		int result = 0;

		HashMap<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < N; i++) {
			if (S.charAt(i) == T.charAt(i)) {
				if (map.containsKey(S.charAt(i))) {
					map.replace(S.charAt(i), map.get(S.charAt(i)) + 1);
				} else {
					map.put(S.charAt(i), 1);
				}
			} else {
				if (map.containsKey(S.charAt(i))) {
					map.replace(S.charAt(i), map.get(S.charAt(i)) + 1);
				} else {
					map.put(S.charAt(i), 1);
				}

				if (map.containsKey(T.charAt(i))) {
					map.replace(T.charAt(i), map.get(T.charAt(i)) + 1);
				} else {
					map.put(T.charAt(i), 1);
				}
			}
			result = Math.max(result, map.get(S.charAt(i)));
			result = Math.max(result, map.get(T.charAt(i)));
		}
		System.out.println(result);
	}
}

변수)
N : 비밀번호 길이
S, T : 문자열
result : 최다 점수
map : HashMap <Character, Integer> 

 

비밀번호 길이 N과 문자열 S, T를 입력받는다. 문자열을 전체 탐색하며 HashMap에 문자 등장 횟수를 구한다. 이때, 같은 위치에 같은 문자열이라면 1만 추가하고, 각각 다른 문자열이라면 각각 HashMap에 저장한다. result를 map의 value값 중 최댓값으로 업데이트한다. 최종 result를 출력한다.

---

---