[class 1]백준 알파벳 찾기(10809번) 풀이 (C++/Python)

문제 : 알파벳 찾기(10809번)(Bronze II)

문제 링크 : https://www.acmicpc.net/problem/10809
출처 : Baekjoon Online Judge

 

 

이 문제는 문자열 하나 입력 받고 index 0부터 순차 탐색(sequential search)을 해서 해당 글자가 처음으로 등장하는 위치(index)를 출력하는 문제입니다.

이 때 해당 글자가 들어가지 않으면 -1로 출력하게 됩니다.

 

우선 비어 있는 문자열(size = 0)이라고 가정하면 모든 글자가 출력되지 않으니 초기 배열은 크기가 26이고 모두 -1로 초기화합니다.

int alphabet[26];
for(int i = 0; i < 26; i++) alphabet[i] = -1;

그 다음 문자열 s를 입력 받고 문자열의 크기를 저장합니다.

string s;
cin >> s;

int size = s.size();

이 다음이 핵심입니다.

for문 돌려서 순차 탐색을 진행합니다.

이 때 해당 글자를 0, 1, 2, 3, ..., 25로 index 형식으로 바꿀려면 아래와 같이 작성해주세요.

char ch = s[i] - 'a';

만약 s[i]가 'a'라고 가정합니다.

그러면 'a'와 'a'의 거리가 0이므로 ch는 0이 됩니다.

이번엔 s[i]가 'd'라고 가정해볼까요?

a에서 d로 옮길려면 총 3칸 정도 움직여야 하므로 ch는 3이 됩니다.

이렇게 index 형식으로 변경하고 그 다음 유효성 검사를 진행합니다.

if(alphabet[ch] == -1) alphabet[ch] = i;

-1이면 아직 갱신되지 않았다는 뜻이니 해당 글자의 위치 번호로 저장합니다.

그런데 만약 -1이 아니라면 이미 한 번 기록했다는 뜻이니 두 번 기록하지 않습니다.

마지막으로 각 알파벳이 처음 나오는 위치를 하나씩 출력하면 됩니다.

for(int i = 0; i < 26; i++) cout << alphabet[i] << " ";

이렇게 모두 다 출력하면 백준 문제 해결입니다.

이 모든 과정을 아래에 전체 소스 코드로 정리합니다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int alphabet[26];
    for(int i = 0; i < 26; i++) alphabet[i] = -1;


    string s;
    cin >> s;

    int size = s.size();

    for(int i = 0; i < size; i++) {
        char ch = s[i] - 'a';
        // warning: array subscript has type ‘char’ <- 이 경고 없애기 위해 정수형으로 변환
        int index = ch;

        if(alphabet[index] == -1) alphabet[index] = i;
    }

    for(int i = 0; i < 26; i++) cout << alphabet[i] << " ";

    return 0;
}

 

Python으로 구현하면 다음과 같습니다.

import sys

input = sys.stdin.readline

alphabet:list = [-1 for _ in range(26)]

S:str = input().rstrip()

for i in range(len(S)) :
    ch:int = ord(S[i]) - ord("a")
    if alphabet[ch] == -1 :
        alphabet[ch] = i

print(*alphabet)

ord()로 해당 문자를 아스키 코드(정수)로 변환하고 두 아스키 코드의 차를 구해서 이를 index로 활용합니다.

 

여기까지 왔다면 수고 많았습니다!

class 1 모든 문제를 해결했습니다.