[바미] 알파벳 찾기

문제

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)로 매우 작습니다.