[Algorithm#1] 백준 1157 문자열

목표

 

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성

 

입력

 

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어짐, 주어지는 단어의 길이는 1,000,000을 넘지 않음

 

출력

 

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 

 

풀이

아스키 코드와 사칙연산으로 처리하는 방법

 

변수 설정 

 

• string word : 첫째 줄에서 입력받은 문자열
• int Alpa[26] : 알파벳(A~Z) 등장 횟수를 저장하는 배열
• int check : Alpa 배열에서의 최대 등장 횟수(최댓값)
• int mem : 최댓값을 가진 알파벳의 인덱스(0~25).

 

풀이 방법:

1. 문자열 word를 한 글자씩 확인하며, 아스키 코드를 이용해 대문자/소문자를 동일하게 처리한다.
   • 예: 소문자라면 대문자로 변환하거나, 인덱스 계산 시 동일한 기준으로 맞춘다.
2. 계산된 알파벳 인덱스(0~25)에 해당하는 Alpa[index] 값을 1씩 증가시켜 등장 횟수를 누적한다.
3. Alpa 배열을 순회하며 최댓값 check를 찾고, 해당 위치를 mem에 저장한다.
4. 순회 중에 check와 같은 값이 또 나오면 최댓값이 여러 개라는 의미이므로 mem = 99로 설정한다.
5. 최종적으로
   • mem == 99이면 ? 출력
   • 아니면 mem에 해당하는 알파벳('A' + mem)을 출력한다.

 

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

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);	

    string word;
    int Alpa[26] = {0};
    
    getline(cin, word);

    for(int i=0; i<word.length(); i++)
    {
        if(word[i] >= 'A' && word[i] <= 'Z'){
            Alpa[word[i]-'A']+=1;
        }
        else if(word[i] >= 'a' && word[i] <= 'z'){
            Alpa[word[i]-'a']+=1;
        }
    }
    int check = 0;
    int mem = 0;   

    for (int j=0; j<26; j++){
        if(Alpa[j] > check){
            check = Alpa[j]; 
            mem = j;
        }
        else if(Alpa[j] == check){
            mem = 99;
        }
    }

    if(mem==99) cout<<"?"<<endl;
    else cout << (char)(mem+65) << endl;

}

 

 

tolower/tourpper 과 아스키코드를 사용하는 방법

 

변수 설정 

• string word : 첫째 줄에서 입력받은 문자열
• char c : word에서 알파벳 분리
• int cnt[26] : 알파벳 저장을 위한 배열
• int mx : 동일값 판단
• int idx : 최종 알파벳 아스키 값 저장
• bool dup : 0이 아니면서 데이터가 동일한 값 판단

풀이 방법:

1. 문자열 word를 한 글자씩 확인하며, 아스키 코드를 이용해 대문자/소문자를 동일하게 처리한다.
   • 예: 소문자를 대문자로 변환하기 위해 toupper를 활용 
2. 계산된 알파벳 인덱스(0~25)에 해당하는 Alpa[index] 값을 1씩 증가시켜 등장 횟수를 누적한다.
3. Alpa 배열을 순회하며 최댓값 check를 찾고, 해당 위치를 mem에 저장한다.
4. 순회 중에 check와 같은 값이 또 나오면 최댓값이 여러 개라는 의미이므로 mem = 99로 설정한다.
5. 최종적으로
   • mem == 99이면 ? 출력
   • 아니면 mem에 해당하는 알파벳('A' + mem)을 출력한다.

 

 

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

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

    string word;
    cin >> word;

    int cnt[26] = {0};

    for (char c : word) {
        c = toupper(static_cast<unsigned char>(c));
        cnt[c - 'A']++;
    }

    int mx = 0, idx = -1;
    bool dup = false;

    for (int i = 0; i < 26; i++) {
        if (cnt[i] > mx) {
            mx = cnt[i];
            idx = i;
            dup = false;
        } else if (cnt[i] == mx && mx != 0) {
            dup = true;
        }
    }

    if (dup) cout << "?\n";
    else cout << char('A' + idx) << "\n";
}

 

시스템 콜 사용하여 속도를 극한으로 처리하는 방법

 

변수 설정 

• unsigned buf[1 << 16] : 65536 바이트 입력 버퍼(64kb), unsigned char 로 뒤서 buf[i] 값을 0~255로 안전하게 인덱싱
• uint32_t cnt[256] : ASCII 포함 모든 바이트의 빈도를 저장, 256칸이면 어떤 입력 바이트가 와도 인덱스 안정
• ssize_t n : read() 반환 타입은 ssize_t가 정석
• uint32_t mx : 현재까지의 최대 빈도
• unsigend char ans : 정답 알파벳 저장
• int dup : 동률 여부
• char out : 최종 출력

풀이 방법:

1. 문자열 word를 한 글자씩 확인하며, 아스키 코드를 이용해 대문자/소문자를 동일하게 처리한

#include <unistd.h>   // read(), write()
#include <stdint.h>   // uint32_t 같은 고정 폭 정수 타입

int main() {
    unsigned char buf[1 << 16];   // 65536바이트 입력 버퍼(64KB)
    // unsigned char로 둬서, buf[i] 값을 0~255로 안전하게 인덱싱 가능

    uint32_t cnt[256] = {0};
    // ASCII 포함 모든 바이트(0~255)의 빈도를 저장
    // 256칸이면 어떤 입력 바이트가 와도 인덱스 안전

    ssize_t n;
    // read() 반환 타입은 ssize_t가 정석(음수면 에러, 0이면 EOF)

    while ((n = read(0, buf, sizeof(buf))) > 0) {
        // 표준입력(fd=0)에서 buf 크기만큼 읽기
        // n > 0 인 동안 계속 읽어서 처리(EOF면 0, 에러면 -1)

        for (ssize_t i = 0; i < n; ++i) {
            // 이번에 읽은 n바이트를 순회하면서
            cnt[buf[i]]++;
            // 해당 바이트 값을 인덱스로 빈도 증가
        }
    }

    uint32_t mx = 0;              // 현재까지의 최대 빈도
    unsigned char ans = 'A';      // 정답 알파벳(대문자) 저장
    int dup = 0;                  // 동률 여부(1이면 '?' 출력)

    for (int c = 'A'; c <= 'Z'; ++c) {
        // 알파벳 A~Z에 대해 대소문자 빈도를 합산
        // ASCII에서 소문자 = 대문자 + 32

        uint32_t v = cnt[(unsigned char)c] + cnt[(unsigned char)(c + 32)];
        // v: 알파벳 c의 (대문자+소문자) 총 빈도

        if (v > mx) {
            // 더 큰 빈도를 찾으면 최대값/정답 갱신
            mx = v;
            ans = (unsigned char)c;
            dup = 0;  // 최대값이 갱신되었으니 동률 상태 해제
        } else if (v == mx && v != 0) {
            // 최대값과 같은 값이 또 나오면 동률 표시
            // v!=0은 "전부 0"인 비정상 상황 방지(문제 입력상 사실상 의미는 미미)
            dup = 1;
        }
    }

    char out = dup ? '?' : (char)ans;
    // 동률이면 '?', 아니면 최대 빈도의 알파벳

    write(1, &out, 1);
    // 표준출력(fd=1)에 1바이트 출력

    return 0;
}