정신차료~

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

백준 1620번: 나는야 포켓몬 마스터 이다솜

맵을 써본 적이 없어서 벡터로 해결하려고 난리치다가 시간 제한에 걸리는 바람에 엄청 헤맸다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	int pokemon, question;
	string temp;

	vector<pair<int, string>>dic;

	cin >> pokemon >> question;

	for (int i = 0; i < pokemon; i++)
	{
		cin >> temp;
		dic.push_back({ i + 1, temp });
	}

	for (int i = 0; i < question; i++)
	{
		cin >> temp;

		if (temp[0] >= 65 && temp[0] <= 90)
		{
			for (int j = 0; j < pokemon; j++)
			{
				if (dic[j].second == temp)
				{
					cout << dic[j].first << "\n";
					break;
				}
			}
		} // 이름 들어옴, 숫자 찾기
		else
		{
			cout << dic[stoi(temp) - 1].second << "\n";
		} //숫자 들어옴
	}
}

벡터로 해결해보려고 노력했던 코드. 의도한 출력이 나오긴 한다.

find를 사용했어도 find의 내부는 for문이기 때문에 시간 초과가 나오는 건 똑같았을 것이다.

결국 map을 사용하여 해결...

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int pokemon, question;
	string temp;
	int numTemp;
	map<string, int> nameDic;
	map<int, string> numDic;

	cin >> pokemon >> question;

	for (int i = 0; i < pokemon; i++)
	{
		cin >> temp;
		nameDic.insert({ temp, i + 1 });
		numDic.insert({ i + 1, temp });
	}

	for (int i = 0; i < question; i++)
	{
		cin >> temp;

		if (temp[0] >= 65 && temp[0] <= 90)
		{
			cout << nameDic[temp] << "\n";
		} //이름 들어옴, 숫자 찾기
		else
		{
			numTemp = stoi(temp);
			cout << numDic[numTemp] << "\n";
		} //숫자 들어옴, 이름 찾기
	}
}

key로 value를 찾는 건 가능한데, for문을 사용하지 않고 value로 key를 찾는 방법은 없을까?

value로 key가 찾고 싶어서 또 한참 방황하다가 결국

<string, int> 맵 하나, <int, string> 맵 하나, 이렇게 두 개를 사용하는 것으로 해결했다.

도움을 받은 글

https://life-with-coding.tistory.com/305

https://psh50zmfhtm.tistory.com/m/5

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

백준 10814번: 나이순 정렬

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


bool compare(pair<int, string> a, pair<int, string> b)
{
	return a.first < b.first;
}

int main()
{
	int num;
	int age;
	string name;
	vector<pair<int, string>> members;

	cin >> num;

	for (int i = 0; i < num; i++)
	{
		cin >> age >> name;
		members.push_back({ age, name });
	}

	stable_sort(members.begin(), members.end(), compare);

	for (int i = 0; i < num; i++)
	{
		cout << members[i].first << ' ' << members[i].second << "\n";
	}
}

stable_sort 대신 그냥 sort를 쓰게 되면,

algorithm 헤더의 기본 sort는 quicksort를 사용하여, 정렬 과정에서 입력된 순서가 보장되지 않을 수 있음

정렬 관련 참고 > https://code-lab1.tistory.com/24

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

백준 2108번: 통계학

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;


int nums[500001];

int main()
{
	int N;
	
	int average = 0;
	int middle = 0;
	int range = 0;


	cin >> N;

	
	for (int i = 0; i < N; i++)
	{
		cin >> nums[i];
	}

	sort(nums, nums + N);


	//평균
	double sum = 0;

	for (int i = 0; i < N; i++)
	{
		sum += nums[i];
	}

	average = round(sum / N);

	
	//중앙값
	int midNum = N / 2;
	middle = nums[midNum];


	//최빈값  잘 모르겠음
	int most[2] = { -9999, -9999 };
	int max = 0;
	int count = 1;
	int resultMost;
	
	nums[N] = -9999;

	for (int i = 0; i < N; i++)
	{
		if (nums[i] == nums[i + 1])
		{
			count++;
		}
		else
		{
			if (count > max)
			{
				max = count;
				most[0] = nums[i];
				most[1] = -9999 ;
			}
			else if (count == max)
			{
				if (most[1] == -9999)
				{
					most[1] = nums[i];
				}
			}
			count = 1;
		}
	}

	if (most[1] != -9999)
	{
		resultMost = most[1];
	}
	else
	{
		resultMost = most[0];
	}

	
	range = nums[N - 1] - nums[0];


	//출력
	cout << average << "\n" << middle << "\n" 
		<< resultMost << "\n" << range;
}

최빈값을 구하는 과정에서 아주 많이 헤맸다.

평균을 구할 때 쓰는 sum 변수는 float 형이 아닌 double 형으로 선언했어야 했다.

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

백준 4948번: 베르트랑 공준

초기 코드 (시간 초과)

#include <iostream>
using namespace std;

int main()
{
	int n;

	while (true)
	{
		cin >> n;

		if (n == 0)
		{
			break;
		}

		int count = 0; //소수 개수 카운트
		int temp = n;

		while (temp != 2*n)
		{
			bool check = true;

			for (int i = 2; i < temp; i++)
			{
				if (temp % i == 0)
				{
					check = false; //소수가 아니면 check=0
				}
			}

			if (check == true)
			{
				count++;
			}
			temp++;
		}
		cout << count << endl;	
	}
}

최종 코드

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
	int n;
	bool tempList[123456*2 + 1] = { 0, };

	while (true)
	{
		cin >> n;

		if (n == 0)
		{
			break;
		}

		int count = 0; //소수 개수 카운트
		int temp = n+1;
		
		while (temp <= 2*n)
		{
			bool check = true;

			if (tempList[temp] == 1)
			{
				count++;
				temp++;
				continue;
			}

			for (int i = 2; i <= sqrt(temp); i++)
			{
				if (temp % i == 0)
				{
					check = false; //소수가 아니면 check=0
					break; //이미 판정 끝나서 더 할 필요 없음
				}
			}

			if (check == true)
			{
				count++;
				tempList[temp] = 1;
			}
            
			temp++;
		}

		cout << count << endl;	
	}
}

에라토스테네스의 체의 원리를 활용해서 (아직 체를 정확히는 모름...)

: 제곱근까지만 for문을 돌아도 됨 (제곱근 위로는 어차피 제곱근 아래에 짝이 있어서 이미 소수가 아닌 것으로 판정)

그렇게 이미 구한 소수를 배열에 저장, 다음 번 판정에 활용하여 시간 단축

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

백준 1193번: 분수찾기

#include <iostream>
using namespace std;

int main()
{
	int X, Y = 0; //입력: X
	int a = 0; // X번째 수는 Y번째 줄의 a번째 수
	int b = 0; //Y를 찾기 위해 임시로 사용하는 값
	cin >> X;

	if (X == 1) { cout << "1/1"; }
	else if (X == 2) { cout << "1/2"; }
	else if (X == 3) { cout << "2/1"; }
	else
	{
		for (int i = 3; i; i++)
		{
			b = i * (i + 1) / 2;
			if (X <= b) { Y = i; break; }
		}

		a = X - Y * (Y - 1) / 2;

		if (Y % 2 == 0)
		{
			cout << a << '/' << Y - a + 1;
		}
		else
		{
			cout << Y - a + 1 << '/' << a;
		}
	}
}

1부터 n까지의 합을 구하는 식을 이용해 Y번째 줄까지의 총 개수를 구했다.

임시값 b가 X보다 커지면 Y를 찾은 것이었는데, b와 X가 같은 경우를 고려하지 않아서 한참 헤맸다.

백준 1018번: 체스판 다시 칠하기

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

#include <iostream>
using namespace std;

string WB[8] = { "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW" };
string BW[8] = { "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB" };
string board[50] = { ""  };

int Func_WB(int X, int Y)
{
	int countWB = 0;
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (board[X + i][Y + j] != WB[i][j])
			{ 
				countWB++;
			}
		}
	}
	return countWB;
}

int Func_BW(int X, int Y)
{
	int countBW = 0;
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (board[X + i][Y + j] != BW[i][j]) 
			{ 
				countBW++; 
			}
		}
	}
	return countBW;
}


int main()
{
	int M, N;
	int count = 32;
	cin >> N >> M;

	for (int i = 0; i < N; i++) 
	{ 
		cin >> board[i]; 
	}

	for (int i = 0; i <= N-8; i++)
	{
		for (int j = 0; j <= M-8; j++)
		{
			int black= Func_BW(i, j);
			int white= Func_WB(i, j);

			if (black < white && black < count) 
			{ 
				count = black; 
			}

			if (black > white && white < count) 
			{ 
				count = white; 
			}
		}
	}

	cout << count;
}

for문이 중복으로 네 개는 써지는 것 같아서

결국 함수로 뺐음

백준 7568번: 덩치

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

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;
	int height[50] = { 0, };
	int weight[50] = { 0, };
	int score[50] = { 0, };

	for (int i = 0; i < N; i++)
	{
		cin >> height[i] >> weight[i];
	}

	for (int i = 0; i < N; i++) //i번째 사람에 대해
	{
		int cnt = 0;

		for (int j = 0; j < N; j++) //나머지 모든 사람에 대해
		{
			if (height[i] < height[j] && weight[i] < weight[j])
			{
				cnt++;
			}
		}
		score[i] = cnt;
	}

	for (int i = 0; i < N; i++)
	{
		cout << score[i] + 1 << ' ';
	}
}

처음에는 점수 배열도 만들고 순위 배열도 만들어서 이상하게 꼬아서 하는 바람에 예제 출력은 제대로 나왔지만 통과하지 못했는데,

문제를 다시 잘 읽어보니

"자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다."

라고 써 있어서 그냥 점수에 +1 한 결과를 출력해주었다.

백준 10870번: 피보나치 수 5

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

#include <iostream>
using namespace std;

int fib(int n)
{
	if (n == 0) { return 0; }
	else if (n == 1) { return 1; }
	else { return (fib(n-1) + fib(n-2)); }
}

int main()
{
	int N;
	cin >> N;
	cout << fib(N);
}