알고리즘 스터디 13일차

1. 트리의 순회 (2263)

1) 문제

문제 설명
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

중위 순회와 후위 순회의 성질을 알면 풀리는 문제
후위 순회의 마지막은 루트 노드
중위 순회는 루트 노드를 찾으면 서브 트리를 분리 할 수 있음

2) 풀이

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

using namespace std;

vector<int> inorder;
vector<int> postorder;

void solution(int in_left, int in_right, int post_left, int post_right)
{
    int l1,r1;
    int l2,r2;
    if (in_left > in_right) return;
    if (post_left > post_right) return;

    cout << postorder[post_right] << " ";

    int index = distance(inorder.begin(), find(inorder.begin(), inorder.end(), postorder[post_right]));
    int leftSize= index - in_left;

    solution(in_left, index - 1, post_left, post_left + leftSize - 1 );
    solution(index + 1, in_right, post_left + leftSize, post_right - 1);
    return;
}

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

    int N;
    cin >> N;

    for (int i = 0; i < N ; i++)
    {
        int temp;
        cin >> temp;
        inorder.push_back(temp);
    }

    for (int i = 0; i < N ; i++)
    {
        int temp;
        cin >> temp;
        postorder.push_back(temp);
    }

    solution(0,inorder.size() - 1, 0, postorder.size() - 1);
    return 0;
}

2. 베스트앨범

1) 문제

문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항
genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.

입출력 예
genres plays return
["classic", "pop", "classic", "classic", "pop"][500, 600, 150, 800, 2500] [4, 1, 3, 0]

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    else
        return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    // 장르의 총 재생횟수를 담는 맵
    unordered_map<string, int> totalCount;
    // 위 변수를 정렬하기 위한 벡터
    vector<pair<string, int>> totalCountVec;
    // 각 장르의 노래목록을 저장하는 맵
    unordered_map<string, vector<pair<int, int>>> songListInGenres;

    // 장르별 총 재생횟수
    // 장르별 노래 목록 저장
    for (int i = 0 ; i < genres.size(); i++)
    {
        totalCount[genres[i]] += plays[i];
        songListInGenres[genres[i]].push_back(make_pair(i, plays[i]));
    }

    // 정렬을 위해 벡터에 삽입
    totalCountVec = vector<pair<string,int>>(totalCount.begin(), totalCount.end());

    // 정렬
    sort(totalCountVec.begin(), totalCountVec.end(), [](pair<string, int> a, pair<string, int> b){
        return a.second > b.second;
    });

    // 많이 재생된 장르부터 순회
    for (auto it = totalCountVec.begin(); it != totalCountVec.end() ; ++it)
    {
        // 장르 추출 후 곡 리스트 정렬 (재생수기준 내림, 동일하면 낮은 고유번호 순)
        string genres = it->first;
        sort(songListInGenres[genres].begin(), songListInGenres[genres].end() ,cmp);
        // 2개씩 뽑음
        for (int i=0; i<2; i++)
        {
            // 1개 밖에 없는 경우 체크해서 종료
            if (i == songListInGenres[genres].size()) break;
            // 정답 배열에 곡의 고유번호를 넣음
            answer.push_back(songListInGenres[genres][i].first);
        }
    }

    return answer;
}