[자바스크립트] 10808 알파벳 개수

10808번: 알파벳 개수

10808번: 알파벳 개수

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

 

 

출력

단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다.

 

 

예제 입력 1

baekjoon

 

 

예제 출력 1

1 1 0 0 1 0 0 0 0 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0

 

 

자료구조

① 문자열: s

 

 

알고리즘

① 문자열 s를 순회하면서 각 문자가 alphabet 문자열에서 어떤 인덱스에 대당하는지 확인한다.

② 해당 인덱스와 동일한 array 배열 요소를 증가한다.

 

 

소스 코드 1

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let s = fs.readFileSync(filePath).toString();

const alphabet = "abcdefghijklmnopqrstuvwxyz";
const array = Array.from({ length: 26 }, () => 0);

for (let i in s) {
  for (let j in alphabet) {
    if (s[i] === alphabet[j]) {
      array[j] += 1;
    }
  }
}

console.log(array.join(" "));

140ms

• `for (let i in input) { ... }`: 문자열의 길이를 N이라고 할 때, 각 문자에 대해 상수 시간이 소요되므로 시간 복잡도는 $O(N)$이다.
• `for (let j in alphabet) { ... }`: 알파벳의 각 문자에 대해 반복하는 부분으로 알파벳은 상수 크기(26)이므로 이 부분의 시간 복잡도도 $O(1)$이다.
• `array[j] += 1`: 배열에 값을 증가시키는 부분도 상수 시간이 소요되므로 시간 복잡도는 $O(1)$이다.

입력 문자열의 길이가 N이라면 시간 복잡도는 $O(N)$

 

소스 코드 2

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let s = fs.readFileSync(filePath).toString();

const alphabet = "abcdefghijklmnopqrstuvwxyz";
const array = Array.from({ length: 26 }, () => 0);

for (let i in s) {
  const index = alphabet.indexOf(s[i]);
  array[index]++;
}

console.log(array.join(" "));

140ms

• `const index = alphabet.indexOf(char)`: 알파벳에서 특정 문자의 인덱스를 찾는 부분은 상수 시간이 소요되므로 시간 복잡도는 $O(1)$이다.

입력 문자열의 길이가 N이라면 시간 복잡도는 $O(N)$이다.

 

 

 

✔ 출처

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