코딩생존기

https://www.acmicpc.net/problem/1764

n개의 단어에서 나온 값과 m개의 단어에서 나온 값이 같은게 몇개인지 출력하고 해당하는 단어를 사전 순으로 출력해주면 되는 문제이다.

나는 map자료형을 통해 중복되는 단어를 vector에 저장하고 sort를 통해 사전순으로 정렬한 다음 해당 vector의 크기와 

원소를 순서대로 출력해주었다.

정답코드

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

using namespace std;

unordered_map<string, bool>hear;
vector<string> both;
int main()
{
	int n, m, cnt = 0;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string person;
		cin >> person;
		hear[person] = true;
	}

	for (int i = 0; i < m; i++)
	{
		string person;
		cin >> person;
		if (hear[person])
		{
			both.push_back(person);
		}
	}

	// 사전 순으로 정렬
	sort(both.begin(), both.end());

	cout << both.size() << '\n';  
	for (const auto& name : both) {
		cout << name << '\n'; 
	}

	return 0;
}

https://www.acmicpc.net/problem/1620

문제가 굉장히 길다 앞부분보다는 입력과 출력 위주로 보고 풀면된다. 나는 입력을 받은 다음에 map과 vector자료형을 

사용하여 만약 문자가 온다면 string과 저장순서가 int로 기록된 map을 통해 출력해주고 만약 숫자가 온다면 벡터안에 저장된 순서에서 1을 빼준 인덱스의 문자를 출력해주는 방식으로 풀어보았다. 

처음에 시간초과가 났는데 이유는 입출력의 크기가 크기 때문이라고 생각해서 cin과 cout를 scanf와 printf 로 바꿔서 풀어주었더니 시간안에 풀 수 있었다.

정답코드

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

using namespace std;

vector<string> pocket;
unordered_map<string, int> pocket2;
int main()
{
	int n, m;

	char buffer[21];  // 포켓몬 이름을 받을 버퍼

	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
	{
		string pocketmon;
		scanf("%s", buffer);
		pocket.push_back(buffer);
		pocket2[buffer] = i + 1;
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%s", buffer);
		if (isdigit(buffer[0]))
		{
			printf("%s\n", pocket[stoi(buffer)-1].c_str());
		}
		else
		{
			printf("%d\n", pocket2[buffer]);
		}
	}

	return 0;
}

https://www.acmicpc.net/problem/7785

이 문제는 문자열 변수 2개를 받고 만약 enter이라면 set 자료형을 통해 넣어주고 leave이면 제거해주면 된다. 그 후에 역순으로 출력해주면된다.

정답코드

#include "iostream"
#include "set"
#include "string"

using namespace std;

set<string> s;
int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string name, action;
        cin >> name >> action;

        if (action == "enter") {
            s.insert(name);  // 회사에 들어왔으면 set에 추가
        }
        else if (action == "leave") {
            s.erase(name);  // 나갔으면 set에서 제거
        }
    }

    // 역순으로 출력
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
        cout << *it << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/14425

N개의 문자를 받고 받은 문자가 M개의 문자에서 몇개나 있는지 검사하면 된다. 나는 map 자료형을 사용해서 string과 bool을 매치시켜주어서 N개의 문자에서 발견된거라면 true를 배정해주고 이를 m개의 단어를 받으면서 true라면

cnt를 증가시켜주었다. 

이때 unordered_map을 자주 사용하는데 

데이터의 정렬이 필요하지 않고, 평균적으로 빠른 성능을 원하는 경우 unordered_map이 적합하고 정렬, 추가적인 메모리 오버헤드 방지, 탐색성능이 예측가능한 상황이 필요할 때  map이 적합하다.

정답코드(map 사)

#include "iostream"
#include "map"
using namespace std;

map<string, bool> mp;
int main()
{
	int n, m, cnt = 0;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string word;
		cin >> word;
		mp[word] = true;
	}

	for (int i = 0; i < m; i++)
	{
		string word;
		cin >> word;
		if (mp[word]) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

정답코드2(unordered_map 사용)

#include "iostream"
#include "unordered_map"
using namespace std;

unordered_map<string, bool> mp;
int main()
{
	int n, m, cnt = 0;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string word;
		cin >> word;
		mp[word] = true;
	}

	for (int i = 0; i < m; i++)
	{
		string word;
		cin >> word;
		if (mp[word]) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

위가 unordered_map 방식이고 밑이 map방식으로 푼 결과이다. 

https://www.acmicpc.net/problem/10815

N개의 수를 입력받은 다음에 M개의 수를 입력받는데 이 수가 처음 입력받는 N개의 수 중에 있다면 1을 출력해주고 아니라면 0을 출력해주면 된다. 

정답코드

#include "iostream"
#include "unordered_map"
using namespace std;

unordered_map<int, bool> mp;

int main()
{
	int n, m;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		mp[x] = true;
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		if (mp[x]) {
			cout << 1 << " ";
		}
		else {
			cout << 0 << " ";
		}
	}

	return 0;
}

https://www.acmicpc.net/problem/18870

이 문제는 해당 원소의 값보다 작은 서로 다른 좌표의 개수가 몇개인지 출력해주면 되는 문제이다. 그렇기 때문에 벡터

입력을 받은 다음 새로운 벡터를 만들어서 값을 복사한 다음 그 벡터를 정렬하고 중복되는 원소를 제거한 다음 그 벡터에서해당 원소의 위치를 저장해주면 되는 문제이다.

정답코드

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    vector<int> sorted_v;

    // 좌표 입력받기
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        sorted_v.push_back(v[i]);
    }

    // 중복 제거 후 정렬
    sort(sorted_v.begin(), sorted_v.end());
    sorted_v.erase(unique(sorted_v.begin(), sorted_v.end()), sorted_v.end());

    // 좌표 압축 적용: 각 값의 압축된 인덱스를 저장
    map<int, int> compression;
    for (int i = 0; i < sorted_v.size(); i++) {
        compression[sorted_v[i]] = i;
    }

    // 원래 좌표에 대해 압축된 결과 출력
    for (int i = 0; i < n; i++) {
        cout << compression[v[i]] << " ";
    }

    return 0;
}

https://www.acmicpc.net/problem/10814

Pair 자료형을 이중으로 사용해주고 이를 vector에 저장해서 정렬함수를 만들어서 정렬해주었다. 이때 가입한 순서는 int 변수를 하나씩 증가시켜주어서 이를 통해 비교하도록했다.

하지만 pair 자료형을 이중으로 사용하면 가독성이 떨어지고 입력받을 때 명시적으로 관리하기 어렵기 때문에 구조체를 사용해서 관리하는 것도 하나의 방법이다. 

정답코드(Pair,Vector사용)

#include "iostream"
#include "vector"
#include "utility"
#include "algorithm"

using namespace std;

bool cmp(pair<pair<string, int>, int>vp1, pair<pair<string, int>, int>vp2)
{
	if (vp1.first.second == vp2.first.second)
		return vp1.second < vp2.second;
	else
		return vp1.first.second < vp2.first.second;
}

vector<pair<pair<string, int>, int>> vpp;
int main()
{
	int n, cnt = 1;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string name;
		int age;
		cin >> age >> name;
		vpp.push_back({ { name,age }, cnt });
		cnt++;
	}

	sort(vpp.begin(), vpp.end(), cmp);

	for (int i = 0; i < n; i++)
	{
		cout << vpp[i].first.second << " " << vpp[i].first.first << endl;
	}

	return 0;
}

정답코드2(구조체 사용)

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

using namespace std;

// 회원 정보를 담는 구조체
struct Member {
    int age;
    string name;
    int order;  // 가입 순서
};

// 정렬 기준 함수: 나이가 같으면 가입 순서대로, 그렇지 않으면 나이 순
bool cmp(const Member &a, const Member &b) {
    if (a.age == b.age) {
        return a.order < b.order;  // 나이가 같으면 가입 순서대로 정렬
    }
    return a.age < b.age;  // 나이 순으로 정렬
}

int main() {
    int n;
    cin >> n;

    vector<Member> members;

    // 회원 정보를 입력받기
    for (int i = 0; i < n; i++) {
        Member member;
        cin >> member.age >> member.name;
        member.order = i;  // 가입 순서를 저장
        members.push_back(member);
    }

    // 정렬: 나이 순 -> 나이가 같으면 가입 순서대로
    sort(members.begin(), members.end(), cmp);

    // 결과 출력
    for (const Member &member : members) {
        cout << member.age << " " << member.name << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/1181

중복된 단어를 제거해야 하기 때문에 집합 자료형인 set을 사용하고 set를 vector로 변환해서 다시 정렬함수를 적용하면 된다. 

정렬함수에서는 길이로 먼저 비교하고 사전순은 string 자체를 비교하면 된다.

정답코드

#include "iostream"
#include "vector"
#include "set"
#include "algorithm"

using namespace std;

// 정렬 기준 함수
bool cmp(const string& a, const string& b) {
	if (a.length() == b.length()) {
		return a < b;  // 길이가 같으면 사전순 정렬
	}
	return a.length() < b.length();  // 길이가 다르면 짧은 순으로 정렬
}

int main()
{
	int n;

	cin >> n;
	set<string> s;

	for (int i = 0; i < n; i++)
	{
		string word;
		cin >> word;
		s.insert(word);
	}

	//set -> vector
	vector<string> v(s.begin(), s.end());

	sort(v.begin(), v.end(),cmp);

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

	return 0;
}

https://www.acmicpc.net/problem/11651

전에 풀었던 문제에서 x좌표의 오름차순에서 y좌표의 오름차순으로 바뀐 문제이다. 정렬함수만 살짝 바꿔주면 풀 수 있는 문제이다. pair에서 first보다 second를 먼저 비교하고 second가 같을 경우 first를 비교해주면 된다.

정답코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> vp;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
    if (p1.second == p2.second) {
        return p1.first < p2.first;
    }
    return p1.second < p2.second;
}

int main() {
    int n;
    scanf("%d", &n);

    vp.reserve(n);

    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vp.push_back({ x, y });
    }

    sort(vp.begin(), vp.end(), cmp);

    for (int i = 0; i < n; i++) {
        printf("%d %d\n", vp[i].first, vp[i].second);
    }

    return 0;
}

https://www.acmicpc.net/problem/11650

pair와 vector를 사용해서 좌표를 저장하고 정렬에 비교함수를 설정해서 비교하면 되겠다고 생각해서 해봤는데 시간초과가 떴다. 그래서 입력이 커서 그런가 싶어서 입출력 최적화를 하기위해 아래 코드를 넣었지만 그래도 시간초과가 떴다.

// 입출력 속도 최적화
    ios::sync_with_stdio(false);
    cin.tie(NULL);

이유를 찾아보니 cin과 cout 보다는 scanf와 printf가 성능이 더 좋다는 것을 알게되어서 이렇게 입출력을 바꿔주니 정답이었다. 

초기코드(cin, cout 사용)

#include "iostream"
#include "utility"
#include "vector"
#include "algorithm"

using namespace std;

vector<pair<int, int>> vp;

bool cmp(pair<int, int> p1, pair<int, int> p2)
{
	if (p1.first == p2.first) {
		return p1.second < p2.second;  // x 좌표가 같을 때는 y 좌표로 비교
	}
	return p1.first < p2.first;  // x 좌표로 비교
}
int main()
{
	// 입출력 속도 최적화
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;

	cin >> n;

	vp.reserve(n);  // 미리 벡터의 메모리를 예약하여 성능 최적화

	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		vp.push_back({ x,y });
	}

	sort(vp.begin(), vp.end(), cmp);

	for (int i = 0; i < vp.size(); i++)
	{
		cout << vp[i].first << " " << vp[i].second << endl;
	}

	return 0;
}

정답코드(printf & scanf 사용)

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> vp;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
    if (p1.first == p2.first) {
        return p1.second < p2.second;
    }
    return p1.first < p2.first;
}

int main() {
    int n;
    scanf("%d", &n);

    vp.reserve(n);

    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vp.push_back({ x, y });
    }

    sort(vp.begin(), vp.end(), cmp);

    for (int i = 0; i < n; i++) {
        printf("%d %d\n", vp[i].first, vp[i].second);
    }

    return 0;
}