처음에 들어온 문자열을 문자로 쪼개서 문자들을 sort해서 next_permutation을 돌렸다. 돌리면서 한 문자에 어떤 숫자가 들어가는 지 결정하고, 또 문자열을 쪼개서 다 합한 것을 계산했다. 뭐라 설명해야할 지 모르겠고, 그냥 미친 짓이였다.
올바른 접근
받은 스트링이 ABCDE가 있다면, 이를 10000 * A + 1000 * B + 100 * C + 10 * D + 1 * E처럼 해석 하는 것이다.
나는 map<char, int> m을 선언해서 char에는 문자를, int에는 숫자를 넣어줬다.
map에 다 넣은 뒤, map의 int 기준으로 내림차순 정렬을 하려고 했다. 그래서 새 구조체를 선언했고, map을 vector로 변환하는 과정을 거쳤다.
// 구조체
struct Le{
char letter;
int value;
Le(char a, int b){
letter = a;
value = b;
}
bool operator < (const Le & b) const {
return value > b.value;
}
};
// 벡터로 변환하는 과정
for(auto & i : m){
if(i.second != 0){
exist.push_back(Le(i.first, i.second));
}
}
내림차순 정렬을 하고, 정렬한 원소 순서대로 9, 8, 7, ...을 넣어서 계산해주면 된다.
int cnt = 9;
sort(exist.begin(), exist.end());
for(auto i : exist){
answer += (cnt * i.value);
cnt--;
}
코드
#include <bits/stdc++.h>
using namespace std;
struct Le{
char letter;
int value;
Le(char a, int b){
letter = a;
value = b;
}
bool operator < (const Le & b) const {
return value > b.value;
}
};
int n, answer;
string temp;
map<char, int> m;
vector<Le> exist;
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> temp;
for(int i = 0; i < temp.length(); i++){
m[temp[i]] += pow(10, temp.length() - i - 1);
}
}
for(auto & i : m){
if(i.second != 0){
exist.push_back(Le(i.first, i.second));
}
}
int cnt = 9;
sort(exist.begin(), exist.end());
for(auto i : exist){
answer += (cnt * i.value);
cnt--;
}
cout << answer;
}
처음 문제에 접근할 때 단순히 문제의 조건대로 1년씩 늘려서 x와 y를 늘려주는 식으로 했다. 역시나 시간 초과. 결국 띄엄띄엄 검사하는 생각해야 했다.
개선한 생각
문제의 조건에 의해 <1, 1>이 <m, n>이 되면 카잉 달력은 끝나게 된다. 그렇다면 <m, n>이 되려면 몇 년이 지나야 할까. 결론부터 말하면 m과 n의 최소공배수가 되면 끝난다 . 그 이유는 왼쪽 수가 m이 되는 경우는 카잉년이 m의 배수가 될 때이고, 오른쪽 수가 n이 되는 경우는 카잉년이 n의 배수가 될 때이기 때문이다. 그래서, limit이라는 변수를 선언해서 카잉년을 몇 년까지 검사를 해야할 지 담아 놓았다. 최소공배수를 구하기 위해, 간단히 함수도 구현해 주었다.
int gcd(int a, int b){
while(b != 0){
int r = a % b;
a = b;
b = r;
}
return a;
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
문제에서 요구하는 것은 _<x, y>는 몇 년째인가?_ 이다. 위와 같이 배수적인 표현으로 생각해보면, 왼쪽 좌표는 카잉년에서 m으로 나눈 나머지 가 되고, 오른쪽 좌표는 카이년에서 n으로 나눈 나머지 가 된다. 숫자를 하나씩 늘려가면서 생각해보면 쉽게 나오는 결론이였다.
현재 카잉년을 tar이라고 했을 때,
tar % m = x이고
tar % n = y인 tar는 <x, y>의 카잉년이 된다. 만일 찾은 카잉년이 limit 이상으로 넘어가게 된다면, 답이 될 수 없다.
위의 조건으로 코드를 구현해보았다.
cin >> m >> n >> x >> y;
flag = 0;
limit = lcm(m, n);
for(int j = x; j <= limit ; j += m){
if(j % n == y % n){
flag = 1;
cout << j << endl;
break;
}
}
if(flag == 0){
cout << "-1" << endl;
}
for문에서 나타나는 j가 위에서 설명한 tar이 된다. j는 for문을 돌면서 왼쪽 좌표가 x가 되는 케이스 를 찾는다. 그 j에서 오른쪽 좌표가 y가 되는 케이스 를 찾으면 그 값이 출력해야 하는 값이 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
while(b != 0){
int r = a % b;
a = b;
b = r;
}
return a;
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
int sit, m, n, x, y, limit, flag;
int main(){
ios_base::sync_with_stdio(false);
cin >> sit;
for(int i = 1; i <= sit; i++){
cin >> m >> n >> x >> y;
flag = 0;
limit = lcm(m, n);
for(int j = x; j <= limit ; j += m){
if(j % n == y % n){
flag = 1;
cout << j << endl;
break;
}
}
if(flag == 0){
cout << "-1" << endl;
}
}
}
server 분야라서 모든 언어가 사용 가능했지만, 백준이나 프로그래머스에 있는 문제처럼 문제가 친절하지는 않았다. 예로 들어, 숫자가 주어질 때 -1을 입력하면 입력을 그만두게 하는 문제들이 백준에는 있지만, 토스 코테에는 그러한 문항이 존재하지 않아 모든 input을 string으로 받아 데이터를 내 입맛대로 분류를 해야해서 매우 불편했다. string을 잘 다루는 것을 코테의 목적이 투영되는 것으로 보아 머지 않은 미래에 모든 코테의 언어는 python으로 바뀔지 모른다.
비교적 쉬운 문제(카카오 코테로 치면 1번이나 2번 문제들)들을 얼마나 빨리 푸는 가를 코테의 목적을 둔 것 같았다.
코테가 시작되었을 때 긴장된 탓인지 손이 떨려 오타가 많이 났고, 원래 쓰던 함수도 잘 생각나지 않았다. 다음 코테에서는 마인드 컨트롤을 하고 코테를 보아야 겠다.
server-2 : background investigation
CS 지식을 묻는 문제였다.
필자의 전공은 컴공이지만, 4년간 대학을 다니면서 모든 지식을 까먹은 것 같았고, 나중에 기술 면접이나 이러한 investigation을 치룰 때 CS 지식이 필요할 것으로 보여 조만간 스터디를 등록해야겠다고 마음 먹었다.
