[코딩테스트 9일차] BAEKJOON 10808번, 11365번, 11720번

코딩 테스트

[코딩테스트 9일차] BAEKJOON 10808번, 11365번, 11720번

sunlight-dby 2025. 4. 22. 02:14

[BAEKJOON 10808번 : 알파벳 개수]

[문제]

[고찰]

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string S;
    int k[26] = { 0 };
    
    getline(cin, S);
    
    for (int i = 0; i < S.length(); ++i)
    {
        // 97 ~ 122
        for (int j = 'a'; j <= 'z'; ++j)
        {
            if (S[i] == j)
                k[j - 'a']++;
        }
    }
    
    for (int i = 0; i <= 25; ++i)
    {
        cout << k[i] << " ";
    }
    
    return 0;
}

위의 코드는 제가 처음 제출한 답안입니다. 답안을 제출한 뒤, 다른 분들의 풀이를 보고 역시나 효율성이 떨어지는 코드임을 깨닫고 다시 정리하고자 합니다.

[개념]

입력 방식
- getline( )을 사용하여 입력을 받기보다는, cin을 사용하는 것이 더 좋은 방법인 듯 합니다.
  애초에 공백이 없는 단어를 입력 받는 것이고, getline( )보다는 cin이 일반적으로 더 빠르게 작동하기 때문입니다.
알파벳 카운트 방식
- 저는 중첩 루프를 사용하여 각 문자가 알파벳인지 확인하고 카운트를 증가시켰습니다. 즉, 각 문자에 대해 모든 알파벳을 비교하는 방식을 사용하였습니다.
  다만, 이 방법은 효율성의 측면에서 좋지 않았습니다. 각 문자에 대해 모든 알파벳을 비교하는 만큼 비용이 증가하기 때문입니다.
- ASCII 값을 활용하여서 알파벳을 카운트 하는 것이 더 간단하고 효율적입니다.
  k[ S[i] - 'a' ] += 1; 를 사용하면 각 문자의 ASCII 값을 직접 인덱스로 사용하여 카운트를 증가시킬 수 있습니다.

[ASCII 값의 차이]

각 문자는 ASCII 값으로 표현됩니다. 참고로 'a'의 ASCII 값은 97입니다.

따라서 S[ i ] - 'a'는 현재 문자의 ASCII 값에서 'a'의 ASCII 값을 빼는 것으로, 'a'부터 'z'까지의 문자에 대해 0부터 25까지의 인덱스를 생성합니다.

k[ S[ i ] - 'a' ] += 1; 를 사용했다면 알파벳이 a일 때 S[ i ] - 'a'는 0이되고, 이는 k[ 0 ]을 의미합니다.
이를 통해 k 배열의 인덱스를 직접적으로 알파벳에 매핑할 수 있습니다.

※ count 함수 활용

count 함수를 활용하면 더욱 간단하게 문제를 풀 수 있습니다.

for문을 'a'부터 'z'까지 값을 반복할 때, 문자열(단어) S를 count 함수를 활용하는 것입니다.

int i를 'a'일때 'z'까지 반복하게 하고, count 함수를 통해 S에서 i를 찾는 것입니다.

물론 성능적으로는 ASCII 값의 차이를 활용하는 방법이 더 효율적입니다.

문자열을 한 번만 순회하여 알파벳 개수를 카운트하므로, 시간 복잡도가 O(n)으로 더 좋습니다.

이에 반해, 두 번째 코드는 각 알파벳마다 문자열을 반복적으로 탐색하므로 O(n*26) = O(n)의 시간복잡도를 갖으며, 성능이 떨어집니다.

다만, 다른 문제에서 활용할 수 있기에 정리를 같이 해둡니다.

[count 함수]

문법

string str;

// str에서 2의 개수를 셉니다.
std::count(str.begin(), str.end(), 2);

헤더파일
- <alogorithm>
매개변수
- 첫 번째 매개변수 : first - 탐색할 범위의 시작 반복자
- 두 번째 매개변수 : last - 탐색할 범위의 끝 반복자
- 세 번째 매개변수 : value - 세고자 하는 값
반환값
- count 함수는 지정된 값이 범위 내에서 나타나는 횟수를 정수형으로 반환합니다.
특징
- O(n) 복잡도 : count 함수는 주어진 범위를 한 번 순회하므로 시간 복잡도는 O(n)입니다.
- 템플릿 함수 : count는 템플릿 함수로, 다양한 데이터 타입에 대해 사용할 수 있습니다.

[정리]

문제를 풀면서 더 어떻게 성능적으로 좋게 만들까를 고민하면서 풀지만, 아직도 부족한 부분이 많습니다.

모르는 것이 많을 수록 많은 무기가 주어진다고 생각하기 때문에, 더욱 공부하고 알아가야겠다는 생각이 들게한 문제였습니다.

[Solution : ASCII 값의 차이]

#include<iostream>
#include<algorithm>

using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string S;
    cin >> S;
    
    int k[26] = { 0, };
    
    // for (auto it : S)를 통해 범위 기반 for 루프 구문을 활용할 수 있습니다.
    for (int i = 0; i < S.length(); i++)
    {
        k[S[i] - 'a'] += 1;
    }
    
    for (int i = 0; i < 26; i++)
    {
        cout << k[i] << ' ';
    }
    
    return 0;
}

[Solution : count 함수]

#include<iostream>
#include<algorithm>

using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string S;
    cin >> S; 
    
    for (int i = 'a'; i <= 'z'; i++)
    {
        cout << count(S.begin(), S.end(), i) << ' ';
    }
    
    return 0;
}

[BAEKJOON 11365번 : !밀비 급일]

[문제]

[고찰]

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string str = "";
    
    size_t pos = str.find("END");
    
    while ( 1 )
    {
        getline(cin, str);
        pos = str.find("END");
        
        if (string::npos != pos)
        {
            break;
        }
        else
        {
            for (int i = str.length(); i >= 0; --i)
            {
                cout << str[i];
            }
            
            str = "";
            cout << "\n";
        }
    }
    
    return 0;
}

위의 코드는 제가 처음 제출한 답안입니다.

무한 루프문에서 getline을 통해 입력을 계속 받고, "END"를 입력받은 문자열 str에서 찾게 되면 pos가 npos인지,아닌지에 따라 str을 거꾸로 출력하거나 루프문이 종료되게끔 구현하였습니다.

답안을 제출한 뒤, 다른 분들의 풀이를 보고 reverse 함수를 몰랐기에 이렇게밖에 풀 수 없었다는 것을 알게 되었습니다. 그래서 이에 대해 정리합니다.

그리고 어차피 입력 조건에서 마지막은 END만 입력이 된다고 하였으면 굳이 find를 활용하여 END를 체크할게 아니라,

str이 "END"인지만 체크하면 될 문제였습니다..

[개념]

reverse 함수

문법

void reverse(RandomIt first, RandomIt last);

헤더 파일
- <alogorithm>
매개변수
- first : 역순으로 변경할 범위의 시작 반복자입니다.
- last : 역순으로 변경할 범위의 끝 반복자입니다. 이 반복자는 last 위치의 요소는 포함하지 않습니다.
특징
- O(n) 복잡도 : reverse 함수는 주어진 범위의 요소들을 한 번 순회하여 역순으로 변경하므로 시간 복잡도는 O(n)입니다.
- 범위 기반 : reverse 함수는 STL의 모든 컨테이너(벡터, 리스트, 배열 등)와 함께 사용할 수 있으며, 반복자를 사용하여
  범위를 지정할 수 있습니다.
- 원본 수정 : reverse 함수는 주어진 범위의 요소들을 직접 수정하므로, 원본 데이터가 변경됩니다.
- 템플릿 함수 : reverse 함수는 템플릿 함수로, 다양한 데이터 타입에 대해 사용할 수 있습니다.

[정리]

reverse 함수도 그렇고 count 함수 역시 <alogorithm> 헤더 파일에 포함된 함수입니다.

이 두 문제를 연달아 풀면서, 문제를 더 효율적으로 풀 수 있게 해주는 <alogorithm> 헤더 파일을 더 공부해야 할 것 같다는 생각이 들었습니다.

뿐만 아니라, 입력 조건 등 문제에 주어진 조건을 모두 꼼꼼히 봐야겠습니다.

[Solution]

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string str;
    
    while (1)
    {
        getline(cin, str);
		
        if (str == "END")
        {
            break;
        }
        
        reverse(str.begin(), str.end());
        cout << str << endl;
    }
    
    return 0;
}

[BAEKJOON 11720번 : 숫자의 합]

[문제]

[고찰]

이 문제도 ASCII 값을 활용하여 풀면 되는 간단한 문자입니다.

해당 문제를 풀 당시에는 알파벳 개수를 구하는 문제를 통해 아이디어를 얻지 못했을 당시였기에, 입력받은 문자열을 정수형으로 형 변환을 할 생각만 하였습니다.

사실 이 형 변환에 아이디어에서 ASCII 값을 활용하는 방법을 떠올렸으면 좋았을텐데 그러지 못하여서, 다시 한번 정리해둡니다.

[개념]

[static_cast를 활용한 형 변환]

일단 문자열을 정수형으로 형 변환을 할 수는 있습니다. static_cast를 사용하면 됩니다.

sum += static_cast<int>(arr[i]);

하지만 형 변환으로는 이 문제를 풀 수는 없습니다. 그렇기에 생각해야할 것이 ASCII 값의 차이입니다.

[ASCII 값의 차이]

일단 입력으로 주어진 숫자 N개를 배열로 입력받아 각 자리 숫자를 더해야 했습니다.

각 자리 숫자를 더하기 위한 아이디어로 ASCII 값을 활용했어야 합니다.

for (int i = 0; i < n; ++i)
{
    // sum += static_cast<int>(numbers[i] - '0');와 동일하지만, 아래의 구문이 더 간단하고 일반적입니다.
    sum += numbers[i] - '0'; 
}

코드의 n은 문제에서의 N이고, numbers는 입력받은 숫자를 저장한 문자열입니다. sum은 문제에서 요구하는 답입니다.

이 코드에서 arr[ i ] - '0'로 각 자리의 숫자를 더할 수 있는 이유는 문자의 ASCII 값을 사용하여 변환하기 때문입니다.

일단 입력으로 주어진 숫자를 모두 문자열로 받았기 때문에 ASCII 값을 활용할 수 있는 것 입니다.

문자 '1'은 10진수로 49의 값을 가집니다. 문자 '0'은 10진수로 48의 값을 가집니다. 이 문장으로 이해가 딱 되지 않았을까 싶습니다.

문자 '1'부터 '9'를 문자 '0'으로 빼게 되면, 10진수 값의 계산으로 인해 문자 '1'에서는 값 1이, 문자 '9'에서는 값 9가 나오게 되는 것입니다.

'1' - '0' == 49 - 48; // 1
'9' - '0' == 57 - 48; // 9

[ASCII 코드표]

[정리]

추후 ASCII 값을 활용한 문제들이 더 나올 수 있으므로, 기본적으로 숫자와 영어 대소문자의 첫 번째와 마지막의 10진수 값은 외워둬야할 것 같습니다.

[Solution]

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::syns_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string numbers;
    
    cin >> n;
    cin >> numbers;
    
    int sum = 0;
    
    for (int i = 0; i < n; ++i)
    {
        sum += numbers[i] - '0';
    }
    
    cout << sum;
    
    return 0;
}

'코딩 테스트' 카테고리의 다른 글

[코딩테스트 11일차] BAEKJOON 2525번 : 오븐시계, BAEKJOON 2914번 : 저작권 (0)	2025.05.01
[코딩테스트 10일차] BAEKJOON 2442번 ~ 2446번 : 별 찍기 5 ~ 9 (0)	2025.04.26
[코딩테스트 8일차] BAEKJOON 2439, 2440번 : 별 찍기 - 2, 3 (0)	2025.04.20
[코딩테스트 7일차] BAEKJOON 1264번 : 모음의 개수 (0)	2025.04.19
[코딩테스트 6일차] BAEKJOON 9498번 : 시험 성적 (0)	2025.04.11

현재글[코딩테스트 9일차] BAEKJOON 10808번, 11365번, 11720번

sunlight-dby 님의 블로그

sunlight-dby 님의 블로그 입니다.

코딩테스트, Unreal Engine 5, State, 프리팹, C#, 2d, 추상 클래스, switch, pixel, Unity, 게임 개발, king's adventure, canvas, PlayerPrefs, hfsm, 인터페이스, Delegate, 팩토리 메서드, UE5, Prefab,

Today :
Yesterday :

sunlight-dby 님의 블로그