[TIL] 2025-02-05

2025-02-05 TIL

알고리즘 문제

이번에 푼 문제도 어려울까 조금 걱정했지만 걱정과 다르게 쉬운 문제였습니다.
프로그래머스 문자열 나누기

자료구조

스파르타 내배캠의 챌린지반 강의와 추가적인 학습을 통해 관련 내용을 정리하고 수정해보았습니다.
레드 블랙 트리의 개념만 살펴보았는데 처음 봤을 때 좀 어렵다는 느낌도 있었습니다.
직접 구현해보진 못하겠지만 그래도 개념은 잘 이해한 것 같습니다.
[C++ Data Structure] 레드-블랙 트리

수학

스파르타 내배캠에서 수학과 관련된 강의가 있었고, 추가로 학습해본 뒤 정리해보았습니다.
[수학] 실수

[수학] 스칼라

[수학] 벡터

챌린지반

다음과 같은 문제 풀이를 진행해보았습니다.

Q. 사용자로부터 n개의 단어를 입력받아, 각 단어의 등장 횟수를 계산하세요.
그 후, 등장 횟수를 기준으로 각 단어에 순위를 매기고, 단어와 그 순위를 출력하세요.
동일한 빈도를 가진 단어는 사전 순으로 정렬하고, 같은 순위를 부여하세요.

다음은 저의 풀이입니다.

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>

bool customSort(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b)
{
    if (a.second == b.second)
    {
        return a.first < b.first;
    }

    return a.second > b.second;
}

int main()
{
    // 단어의 개수
    int n;
    std::cin >> n;

    // 단어를 저장할 자료구조
    std::unordered_map<std::string, int> wordCount;

    // 단어의 개수만큼 입력받고, 카운트 세기
    for (int i = 0; i < n; ++i)
    {
        std::string str;
        std::cin >> str;

        ++wordCount[str];
    }

    // 정렬을 위해 벡터 자료형으로 복사
    std::vector<std::pair<std::string, int>> vec(wordCount.begin(), wordCount.end());
    
    // 정렬
    std::sort(vec.begin(), vec.end(), customSort);

    // 순위
    int rank = 0;
    // 이전에 나온 단어의 카운트와 같다면 횟수 카운트
    int prev = -1;
    int prevCount = 0;
    for (auto e : vec)
    {
        // 이전에 나온 단어와 다르다면 순위 및 관련 변수 수정
        if (prev != e.second)
        {
            prev = e.second;
            ++rank;
            rank += prevCount;
            prevCount = 0;
        }
        // 이전에 나온 단어와 같다면 횟수 카운트
        else
        {
            ++prevCount;
        }

        // 출력
        std::cout << e.first << ": " << rank << std::endl;
    }
};