하루 알고리즘(JS)
[바미] 알바벳 찾기
Bami
2024. 9. 20. 09:46
728x90
반응형
문제
https://www.acmicpc.net/status?user_id=ckdqja135&problem_id=10809&from_mine=1
코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
// 알파벳 위치 배열을 -1로 초기화 (알파벳 개수 26개)
const alphabetPositions = Array(26).fill(-1);
// 문자열 순회하며 각 문자의 첫 등장 위치 기록
for (let i = 0; i < input.length; i++) {
const char = input[i];
const index = char.charCodeAt(0) - 'a'.charCodeAt(0); // 'a'는 0, 'b'는 1, ..., 'z'는 25
// 첫 등장 위치만 기록
if (alphabetPositions[index] === -1) {
alphabetPositions[index] = i;
}
}
// 결과 출력
console.log(alphabetPositions.join(' '));
문제 해설
이 문제는 주어진 문자열 S에 대해 알파벳 소문자 각각이 처음으로 등장하는 위치를 찾는 문제입니다.
시간 복잡도
시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다
문자열의 길이가 최대 100이므로, 문자열을 한 번 순회하는 데 𝑂(𝑁)의 시간이 걸립니다.
공간 복잡도
공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.
배열 alphabetPositions는 고정 크기(26)를 가지므로, 공간 복잡도는 𝑂(1)로 매우 작습니다.
728x90
반응형