x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.
※ 나의 풀이
일단 피타고라스 정리를 이용하여 접근하면 편하다.
먼저 x축과 y축에 있는 점들은 제외하고 4분면으로 나누어서 각 면에 있는 점들을 구하여 곱하기 4를 해준다.
그 후, x축과 y축에 있는 점들을 더해주면 된다!
int r1 = 2, r2 = 3;
vector<pair<int, int>> points;
long long answer = 0;
double r2y = 0, r1y = 0;
int side = 0;
for (int i = 1; i < r2; i++)
{
r2y = sqrt(pow(r2, 2) - pow(i, 2));
if (r1 > i) r1y = sqrt(pow(r1, 2) - pow(i, 2));
else r1y = 0;
if (r1y - (int)r1y == 0 && r1y != 0)
side++;
answer += ((int)r2y - (int)r1y);
}
answer = (answer + side + r2 - r1 + 1) * 4;
A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다. 각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
※ 나의 풀이
먼저 targets의 좌표들을 정렬 해주었습니다.
그리고 cur, next를 이용하여 문제풀이를 진행했습니다.
cur의 second 값이 next의 first 값보다 크다면, next의 위치를 + 해주었습니다.
반대로 cur의 second 값이 next의 first 값보다 작다면, 겹치는 부분이 없기 때문에 cur의 위치를 next로 변경 해주었습니다.
그리고 cnt++ 진행.
그런데 35점이 나왔다...
이유를 생각해보니
cur의 second 값이 next의 first 값보다 크다면, next의 위치를 + 해주는 상황에서
cur의 second 값이 next의 second 값보다 크다면 문제가 발생한다. cur = next를 해주지 않게 되면
예를 들어, cur = [1, 6], next = [2, 4] 가 된다면 2 ~ 6 사이에 요격을 진행하게 된다.
그런데 그 다음 오는 좌표가 [5, 7]이면 5 ~6 의 범위로 줄어들게 된다.
여기서 생각을 해보면 [2, 4]와 [5, 7]은 겹치지 않는다.
즉, cur = next를 해주어야 한다.
vector<vector<int>> targets =
{ {4, 5}, {4, 8}, {10, 14}, {11, 13}, {5, 12}, {3, 7}, {1, 4} };
sort(targets.begin(), targets.end(), cmp);
for (vector<int> t : targets)
{
cout << t[0] << " " << t[1] << endl;
}
int cnt = 1;
int cur = 0;
int next = 1;
while (cur < targets.size() && next < targets.size())
{
if (targets[cur][1] > targets[next][0])
{
// 여기가 중요! 값 바꿔주기
if (targets[cur][1] > targets[next][1])
cur = next;
next++;
}
else
{
cur = next;
next++;
cnt++;
}
}
사진들을 보며 추억에 젖어 있던 루는 사진별로 추억 점수를 매길려고 합니다. 사진 속에 나오는 인물의 그리움 점수를 모두 합산한 값이 해당 사진의 추억 점수가 됩니다. 예를 들어 사진 속 인물의 이름이 ["may", "kein", "kain"]이고 각 인물의 그리움 점수가 [5점, 10점, 1점]일 때 해당 사진의 추억 점수는 16(5 + 10 + 1)점이 됩니다. 다른 사진 속 인물의 이름이 ["kali", "mari", "don", "tony"]이고 ["kali", "mari", "don"]의 그리움 점수가 각각 [11점, 1점, 55점]]이고, "tony"는 그리움 점수가 없을 때, 이 사진의 추억 점수는 3명의 그리움 점수를 합한 67(11 + 1 + 55)점입니다.
그리워하는 사람의 이름을 담은 문자열 배열 name, 각 사람별 그리움 점수를 담은 정수 배열 yearning, 각 사진에 찍힌 인물의 이름을 담은 이차원 문자열 배열 photo가 매개변수로 주어질 때, 사진들의 추억 점수를 photo에 주어진 순서대로 배열에 담아 return하는 solution 함수를 완성해주세요.
※ 나의 풀이
이건 솔직히 어렵지 않았다.
각 이름별로 각자 고유의 점수가 있기 때문에 map을 이용하기로 했다.
vector<string> name = { "may", "kein", "kain", "radi" };
vector<int> point = { 5, 10, 1, 3 };
vector<vector<string>> ar =
{ {"may", "kein", "kain", "radi"},
{"may", "kein", "brin", "deny"},
{"kon", "kain", "may", "coni"} };
// unordered_map이 map보다 빠르다고 한다.
unordered_map<string, int> name_point;
for (int i = 0; i < name.size(); i++)
{
name_point.insert(make_pair(name[i], point[i]));
}
vector<int> answer;
for (int i = 0; i < ar.size(); i++)
{
int res = 0;
for (int j = 0; j < ar[i].size(); j++)
{
res += name_point[ar[i][j]];
}
answer.push_back(res);
}
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
부분 수열의 합은 k입니다. - 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. - 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
※ 나의 풀이
먼저 주어지는 vector는 정렬되어 있으므로 굉장히 마음이 놓인다.
처음에는 DFS로 접근을 했지만, 시간초과가 발생했다.
누적합이라는 것을 알게 돼서 이용하기로 했다.
그리고 투포인트를 이용하여 값을 찾기로 했다.
int l = 0, r = 0, s = 0, e = 0;
int length = 2147000000;
int n = sequence.size(); // 5
int sum = sequence[0];
while (true)
{
// 합이 k와 같다면 기존에 저장되어 있는 길이와 비교하여 s, e 값 업데이트
if (sum == k)
{
int tmp = r - l + 1;
if (tmp < length)
{
s = l;
e = r;
length = tmp;
}
}
// l, r이 vector의 끝에 위치하면 break;
if (r >= n && l >= n) break;
// sum이 k보다 작으면 r을 오른쪽으로 옮긴다.
// 그 반대의 경우 l을 오른쪽으로 옮긴다.
// r < n을 해주지 않으면 r값만 +돼서 while문이 끝나지 않을 수 있다.
if (sum <= k && r < n)
{
r++;
if (r < n) sum += sequence[r];
}
else
{
if (l < n) sum -= sequence[l];
l++;
}
}
얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.
선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.
※ 나의 풀이
처음에는 그냥 for문을 돌려서 find 함수를 이용했지만 시간 초과가 발생했다.
생각해보니 각 Key에 맞는 등수는 중복되는 것이 없기 때문에 map을 이용하여 Key, Value를 이용하기로 했다.
그래서 map을 이용하여 바로바로 값에 접근할 수 있게 변경해주었다.
vector<string> players = { "mumu", "soe", "poe", "kai", "mine" };
vector<string> callings = { "kai", "kai", "mine", "mine" };
int idx = -1;
string tmp;
// 이름, 등수를 이용한 map 선언
map<string, int> name_rank;
map<int, string> rank_name;
// map 채워주기
for (int i = 0; i < players.size(); i++)
{
string name = players[i];
int rank = i + 1;
name_rank.insert(make_pair(name, rank));
rank_name.insert(make_pair(rank, name));
}
// callings에서 값을 꺼내와 map에 등록되어 있는 값 바꿔주기
for (int i = 0; i < callings.size(); i++)
{
string call = callings[i];
int call_rank = name_rank[call];
string front_player = rank_name[call_rank - 1];
name_rank[call]--;
name_rank[front_player]++;
rank_name[call_rank] = front_player;
rank_name[call_rank - 1] = call;
}
vector<string> answer;
for (int i = 1; i <= players.size(); i++)
{
answer.push_back(rank_name[i]);
}
