백준 10809번 [알파벳 찾기](C++)-yes6686- 티스토리

백준 문제 풀이: 10809 [알파벳 찾기]

---

문제 링크: https://www.acmicpc.net/problem/10809

문제 설명:

알파벳 소문자로만 이루어진 단어가 주어졌을 때, 각 알파벳이 단어에서 처음 등장하는 위치를 구하는 프로그램을 작성하세요. 만약 단어에 포함되지 않은 알파벳이 있다면 -1을 출력합니다.

입력 조건:

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

출력 조건:

• 각 알파벳에 대해 단어에서 처음 등장하는 위치를 공백으로 구분하여 출력한다. 단어의 첫 번째 글자는 0번째 위치이다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    // 알파벳 26개의 위치를 저장하는 배열
    int arr[26];
    fill_n(arr, 26, -1); // 모든 값을 -1로 초기화

    string s;
    cin >> s; // 단어 입력

    // 문자열 순회
    for (int i = 0; i < s.size(); i++) {
        int index = s[i] - 'a'; // 알파벳의 인덱스 계산
        if (arr[index] == -1) {
            arr[index] = i; // 해당 알파벳의 첫 등장 위치 저장
        }
    }

    // 결과 출력
    for (int i = 0; i < 26; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 입력받은 문자열에서 알파벳 소문자의 위치를 효율적으로 찾습니다.

• 배열 초기화: `arr` 배열은 알파벳 소문자의 위치를 저장하며, 초기값은 -1로 설정합니다. 이는 해당 알파벳이 등장하지 않았음을 나타냅니다.
• 문자열 탐색:
  • `s[i] - 'a'`를 이용하여 알파벳의 인덱스를 계산합니다.
  • 각 알파벳의 첫 등장 위치만 저장하기 위해 배열 값이 -1일 때만 갱신합니다.
• 출력: 배열의 값을 순서대로 출력하며, 각 값은 공백으로 구분됩니다.

시간 복잡도 분석:

• 문자열 길이를 N이라 할 때, 문자열 탐색은 O(N).
• 출력은 26개의 알파벳에 대해 상수 시간이 소요되므로 O(1).

따라서 전체 시간 복잡도는 O(N)입니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
baekjoon

출력:
1 0 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 5 -1 -1 3 2 -1 -1 -1 -1 -1 -1

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!