[Level 0] 문자열 등장 횟수

문제 

숫자로 이루어진 문자열 s가 있습니다. 
이 문자열에서 가장 많이 등장하는 0 ~ 9 사이의 숫자를 출력하는 프로그램을 구현하세요.
단, 가장 많이 등장하는 수가 여러 개라면, 그 중 가장 작은 수를 반환하세요.

 

입력 형식

• s 는 숫자로 이루어진 문자열 

 

출력 형식

• 가장 많이 등장하는 수를 정수로 반환 

 

제약 사항 

• 0 < s.length <= 100

 

입출력 예시 

• 예시1

• 입력 : s = "174771177"
• 출력 : 7
• 설명 : 7이 가장 많이 등장하였으므로 답은 7이다.

 

• 예시2

• 입력 : s = "552342502"
• 출력 : 2
• 설명 : 2와 5가 가장 많이 등장하지만, 2가 더 작으므로 2를 반환 

 

---

내 풀이

function solution(s) {
    const setArr = [...new Set(s)].sort((a,b) => a-b);
    let max = 0;
    let result = 0;
    setArr.forEach((v) => {
        let count = [...s].reduce((a,c) => c === v ? a += 1 : a, 0);
        if(max < count) {max = count; result = +v}
        else if (max === count) {
            result = Math.min(result, +v);
        }
    });

    return result;
}

 

• 시간 복잡도 : O(n^2)
• 설명 : 해당 코드는 문자열 s를 중복을 제거한 후 정렬하여 setArr 배열에 저장한다. 그리고 setArr 배열을 순회하면서 각 문자(v)가 s에 몇 번 등장하는지 세는데, 이를 위해 또 다시 s를 배열로 만들어 reduce 메서드를 사용한다. 이렇게 되면 각 문자마다 다시 전체 문자열을 검사하므로 시간 복잡도가 O(n)인 reduce 메서드를 setArr의 길이만큼 호출하게 된다. 이는 효율적이지 않은 방법이며, 특히 문자열이 매우 긴 경우에는 성능이 더욱 저하될 수 있다.

 

---

해결 방법

function solution(s) {
  const charCounts = new Map();

  for (const char of s) {
    if (charCounts.has(char)) {
      charCounts.set(char, charCounts.get(char) + 1);
    } else {
      charCounts.set(char, 1);
    }
  }

  let maxCount = 0;
  let resultChar;

  charCounts.forEach((count, char) => {
    if (count > maxCount) {
      maxCount = count;
      resultChar = char;
    } else if (count === maxCount && char < resultChar) {
      resultChar = char;
    }
  });

  return resultChar;
}

 

• 시간 복잡도 : O(n)
• 설명 : 해결 방법으로는 문자열을 한 번만 순회하면서 각 문자의 등장 횟수를 세는 방법이 있다. 이렇게 하면 중복 계산을 피할 수 있으며, 시간 복잡도를 O(n)으로 개선할 수 있다. ⇒ 문자의 등장 횟수를 세는 방법으로 map을 사용하자.