백준 - 스텍, 큐, 수찾기, 요세푸스 문제 0, 집합

LOE·2025년 1월 7일
cpp

백준

목록 보기
4/5

문제 - 스텍

해결

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


using namespace std;




int main()
{
    int N, v;
    cin >> N;
    cin.ignore();
    string command;
    int arr[10000] = {0};
    int head = 9999;
    int tail = 9999;
    vector<int> result;
    for (int i = 0; i < N; i++)
    {
        getline(cin, command);
        istringstream iss(command);
        vector<string> tokens;
        string token;
        while(iss >> token)
        {
            tokens.emplace_back(token);
        }
        if (tokens[0] == "push")
        {
            arr[head--] = stoi(tokens[1]);
        }
        if (tokens[0] == "top")
        {
            if (head == tail)
            {
                result.emplace_back(-1);
            }
            else
            {
                result.emplace_back(arr[head+1]);
            }
        }
        if (tokens[0] == "size")
        {
            result.emplace_back(tail-head);
        }
        if (tokens[0] == "pop")
        {
            if (head == tail)
            {
                result.emplace_back(-1);
            }
            else
            {
                result.emplace_back(arr[head+1]);
                arr[head+1] = 0;
                head++;
            }
        }
        if (tokens[0] == "empty")
        {
            if (head == tail)
            {
                result.emplace_back(1);
            }
            else
            {
                result.emplace_back(0);
            }
        }
    }
    for (int i : result)
    {
        cout << i << "\n";
    }
}

10000자리 배열을 생성한 후 배열의 마지막 위치에 head와 tail을 가리키는 인덱스를 생성합니다. 이후 각 line을 받은 뒤 token[0]이 push일 경우 뒤의 값을 head위치에 저장하고 head값의 인덱스를 하나 줄입니다. top일 경우 result vector에 head앞의 값을 저장, pop일경우 head 값을 하나 더하고 그 값을 0으로 만듧니다. 이런식으로 결과를 result벡터에 순서대로 저장한 후 차례로 출력합니다.

문제 - 큐

해결

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

using namespace std;

int main()
{
    int N, v;
    cin >> N;
    cin.ignore();
    string command;
    int arr[10000] = {0};
    int head = 9999;
    int tail = 9999;
    vector<int> result;
    for (int i = 0; i < N; i++)
    {
        getline(cin, command);
        istringstream iss(command);
        vector<string> tokens;
        string token;
        while(iss >> token)
        {
            tokens.emplace_back(token);
        }
        if (tokens[0] == "push")
        {
            arr[tail--] = stoi(tokens[1]);
        }
        if (tokens[0] == "front")
        {
            if (head == tail)
            {
                result.emplace_back(-1);
            }
            else
            {
                result.emplace_back(arr[head]);
            }
        }
        if (tokens[0] == "back")
        {
            if (head == tail)
            {
                result.emplace_back(-1);
            }
            else
            {
                result.emplace_back(arr[tail+1]);
            }
        }
        if (tokens[0] == "size")
        {
            result.emplace_back(head-tail);
        }
        if (tokens[0] == "pop")
        {
            if (head == tail)
            {
                result.emplace_back(-1);
            }
            else
            {
                result.emplace_back(arr[head]);
                arr[head+1] = 0;
                head--;
            }
        }
        if (tokens[0] == "empty")
        {
            if (head == tail)
            {
                result.emplace_back(1);
            }
            else
            {
                result.emplace_back(0);
            }
        }
    }
    for (int i : result)
    {
        cout << i << "\n";
    }
}

위의 스텍 문제에서 head와 tail의 위치를 바꾸고 tail에서는 입력만 head에서는 출력만 되도록 변경하였습니다.

문제 - 수 찾기

해결

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


using namespace std;

map<int, int> v_numbers;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M, v;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> v; 
        v_numbers[v]++; // map의 v라는 숫자가 있는 개수의 카운트를 증가시킨다.
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> v;
        int result = v_numbers[v] > 0 ? 1 : 0;
        cout << result << "\n";
    }
    
}

cpp의 map함수는 각 노드가 key와 value로 이루어진 트리입니다. 내부가 레드블랙트리로 구현되어 있어 검색, 삽입, 삭제를 O(log⁡N)O(\log{N})입니다. map에서 N개의 값을 입력할때 한번이라도 등장했다면 value값이 양수가 됩니다. 따라서 결과출력시 양수인경우 1 음수인경우 0을 출력합니다. 이때 입출력 속도를 높이기 위해 ios::sync_with_stdio(false)를 통해 C와 C++의 입출력의 연결을 끊어줍니다. 또한 cin.tie(NULL)을 통해 cin이 호출될때마다 cout이 flush되는 작업을 하지 않게 됩니다.

문제 - 요세푸스 문제 0

해결

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


using namespace std;


int main()
{
    int N, K;
    int count = 0;
    int index = 0;
    cin >> N >> K;
    vector<int> numbers;
    vector<int> results;
    
    for (int i = 0; i < N; i++)
    {
        numbers.emplace_back(i+1);
    }
    while(1)
    {
        if (numbers[index] == 0)
        {
            index++;
            if (index == numbers.size())
            {
                index = 0;
            }            
            continue;
        }
        count++;
        if (count % K == 0)
        {
            results.emplace_back(numbers[index]);
            numbers[index] = 0;
        }
        index++;
        if (index == numbers.size())
        {
            index = 0;
        }
        if (numbers.size() == results.size())
        {
            break;
        }
    }
    for (int i = 0; i < N; i++)
    {
    if (i == 0)
        {
            cout << "<";
        }
        if (i == N - 1)
        {
            cout << results[i] << ">";
            continue;
        }
        cout << results[i] << ", ";
    }
}

벡터로 입력을 저장하고 count와 index를 0으로 초기화한 후 관리해가며 벡터를 순회합니다. 이때 count%K==0 즉 K번째가 되면 result 벡터로 값을 옮긴후 기본 벡터의 값을 0으로 만듧니다. 이러한 방식으로 순회하며 값이 0인 경우에는 count의 수를 증가시키지 않으면 기존 벡터의 길이를 변경하지 않고도 result벡터로 값을 추출할 수 있게 됩니다.

문제 - 집합

해결

초기구현

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


using namespace std;


map<int, int> info;

int main()
{
    int M;
    cin >> M; // 명령의 갯수
    cin.ignore();
    vector<int> results;
    for (int i = 0; i < M; i++)
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        string command;
        string token;
        vector<string> tokens; 
        getline(cin, command); 
        istringstream iss(command);
        while(iss >> token)
        {
            tokens.emplace_back(token);
        }
        if (tokens[0] == "add")
        {
            info[stoi(tokens[1])] = 1; // map에서 add할 value에 해당하는 값을 1 증가시킴 예를 들어 1이 한번 들어갔다면 info[1] = 1이 됨.
        }
        if (tokens[0] == "check")
        {
            if (info[stoi(tokens[1])] > 0) //x에 해당하 값이 map에 존재한다면
            {
                results.emplace_back(1);
            }
            else
            {
                results.emplace_back(0);
            }
        }
        if (tokens[0] == "remove")
        {
            info[stoi(tokens[1])] = 0;
        }
        if (tokens[0] == "toggle")
        {
            if (info[stoi(tokens[1])] > 0) // x값이 map에 존재한다면 0으로 만듦
            {
                info[stoi(tokens[1])] = 0;
            }
            else
            {
                info[stoi(tokens[1])] = 1;
            }
        }
        if (tokens[0] == "all")
        {
            for (int i = 1; i <= 20; i++)
            {
                info[i] = 1;
            }
        }
        if (tokens[0] == "empty")
        {
            for (int i = 1; i <= 20; i++)
            {
                info[i] = 0;
            }
        }
    }
    for (int i : results)
    {
        cout << i << "\n";
    }

}

초기에는 map을 통해 값에 해당하는 숫자를 늘리고 이를 0이 아닌 값을 출력하는 식으로 구현했습니다. 하지만 if 문을 통해 비교한 후 작업을 수행하는 점과 map을 사용하는 면에서 시간이 초과 되었다고 생각하여 다시 구상하였습니다.

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

using namespace std;

unordered_map<string, function<void(int)> > func;

int value = 0;

void Add(int n)
{
    value |= (1 << (n-1));
}

void Check(int n)
{
    if (value & (1 << (n-1)))             
    {
        cout << 1 << "\n";    
    }
    else
    {
        cout << 0 << "\n";    
    }
}

void Remove(int n)
{
    value &= ~(1 << (n-1));
}

void Toggle(int n)
{
    value ^= (1 << (n-1));
}

void All(int n)
{
    value |= ~(1 << 30);
}
void Empty(int n)
{
    value = 0;
}

int main()
{
    int M;
    cin >> M; // 명령의 갯수
    cin.ignore();
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    func["add"] = Add;
    func["check"] = Check;
    func["remove"] = Remove;
    func["toggle"] = Toggle;
    func["all"] = All;
    func["empty"] = Empty;
    for (int i = 0; i < M; i++)
    {
        string command;
        string operation; 
        getline(cin, command); 
        stringstream iss(command);
        iss >> operation;
        int val;
        iss >> val;
        func[operation](val);
    }
    return 0;
}

이후에는 비트 마스킹 기법을 통해 32비트 int 자료형의 1 ~ 20 번째 비트를 키고 끄는 식으로 명령을 구현하였습니다. 또한 unordered map을 사용하여 함수를 분리하여 저장하엿습니다. 하지만 시간초과가 났습니다. 알고보니 원인은 string stream을 통해 명령을 받아오는 부분에서 딜레이가 많이 되었습니다. 

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


using namespace std;


map<int, int> info;

int main()
{
    int M;
    cin >> M; // 명령의 갯수
    cin.ignore();
    for (int i = 0; i < M; i++)
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        string command;
        int val;
        cin >> command;
        if (command == "add")
        {
            cin >> val;
            info[val] = 1; // map에서 add할 value에 해당하는 값을 1 증가시킴 예를 들어 1이 한번 들어갔다면 info[1] = 1이 됨.
        }
        if (command == "check")
        {
            cin >> val;
            if (info[val] > 0) //x에 해당하 값이 map에 존재한다면
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\n";
            }
        }
        if (command == "remove")
        {
            cin >> val;
            info[val] = 0;
        }
        if (command == "toggle")
        {
            cin >> val;
            if (info[val] == 0) // x값이 map에 존재하지 않는다면 1로 만듦.
            {
                info[val] = 1;
            }
            else
            {
                info[val] = 0;
            }
        }
        if (command == "all")
        {
            for (int i = 1; i <= 20; i++)
            {
                info[i] = 1;
            }
        }
        if (command == "empty")
        {
            for (int i = 1; i <= 20; i++)
            {
                info[i] = 0;
            }
        }
    }
}

이후 길이가 20인 벡터에 값을 저장하여 다시 구현하였습니다.

profile
LOE
hi
이전 포스트

백준 - 수 정렬하기 2, 좌표 정렬하기, 체스판 다시 칠하기, 카드2, 괄호

다음 포스트

백준 - 듣보잡, 피보나치 함수, 1,2,3 더하기, 구간 합 구하기 4, 유기농 배추

0개의 댓글