LeetCode 1002. Find Common Characters - 공통 문자 추출 문제

URL : https://leetcode.com/problems/find-common-characters

문제

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

Example 1:

Input: words = [“bella”,”label”,”roller”] Output: [“e”,”l”,”l”]

Example 2:

Input: words = [“cool”,”lock”,”cook”] Output: [“c”,”o”]

제약 조건

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters.

접근 방법

• 주어진 모든 word에서 공통적으로 나타나는 문자를 체크하기 위해 int 배열을 사용한다. int 배열은 정수의 최대 값으로 초기화 한다. 0이 아닌 정수의 최대 값으로 초기화 하는 이유는 모든 문자에서 공통적으로 나타나는 알파벳의 최소 빈도를 담을 것이기 때문이다.
  • ex) 모든 문자에서 b가 1번씩 나왔으면 b를 나타내는1번 인덱스에 값 1을 대입한다. 만약 마지막 문자에서 b가 나오지 않았다면 모든 문자에서 공통적으로 나타나지 않았기 때문에 0으로 업데이트 되어야 한다.
• 각 문자에 대해 알파벳이 몇 번 나왔는지도 int 배열로 담는다. 이 배열은 알파벳 빈도를 카운팅 해야 하기 때문에 0으로 초기화한다.
  • ex) bella -> a : 1, b : 1, e : 1, l : 2 로 카운팅
• 하나의 문자를 모두 확인하였으면 이전 문자의 alphabet frequency를 담고 있는 배열의 값과 현재 문자의 alphabet frequency값을 비교하여 더 작은 수로 업데이트 한다.

풀이

class Solution {
    public List<String> commonChars(String[] words) {
        int numOfAlphabet = 26;
        int[] freqCharInWords = new int[numOfAlphabet];
        Arrays.fill(freqCharInWords, Integer.MAX_VALUE);

        for(int i = 0; i < words.length; i++){
            int[] freqCharInAlpha = new int[numOfAlphabet];
            //Arrays.fill(freqCharInAlpha, 0);

            for(char c : words[i].toCharArray()){
                int charToInt = (int)(c -'a'); // 타입캐스팅 생략 가능
                freqCharInAlpha[charToInt]++;
            }

            for(int j = 0 ; j < freqCharInAlpha.length; j++){
                freqCharInWords[j] = Math.min(freqCharInWords[j], freqCharInAlpha[j]);
            }
        }
        List<String> answer = new ArrayList<>();
        for(int i = 0 ; i < numOfAlphabet; i++ ){
                while(freqCharInWords[i] > 0){
                    answer.add( Character.toString (i + 'a'));
                    freqCharInWords[i]--;
                }
        }
        return answer;
    }
}

생각

실무에서는 아스키 코드 변환을 잘 사용하지 않다보니 아스키 코드 변환 방법을 매번 검색하게 된다.

자바에서 char타입을 int타입으로 변환할 때는 타입캐스팅을 활용한다. 이번 문제에서 a를 숫자 0, b를 숫자 1 … z 를 숫자 25로 치환이 필요하여 (int)(char c - 'a') 로 변환 했다.

타입캐스팅 시 명시적 타입캐스팅 사용하였는데 묵시적 타입캐스팅으로 (int)를 생략하여 코드를 작성할 수 있다.

다시 숫자를 문자로 바꾸기 위해서는 int 타입 숫자에 알파벳 기준 a을 더해 character 타입으로 타입 캐스팅 한 뒤, Character의 toString을 사용하여 String형태로 변환한다.

Character toString은 내부적에서 String.valueOf 메소드를 호출한다.

valueOf 메소드는 내부에서 String 생성자를 호출한다 return new String(data)