백준: Silver⑩ - 1269, 1283, 1326, 1334
</br>
이제 또 실버 3에서 풀이
</br>
1269: 대칭 차집합
https://www.acmicpc.net/problem/1269
집합 두 개 받으면 대칭 차집합의 크기 구하기
for(int i = 0; i < a; i++){
int t;
cin >> t;
as.insert(t);
}
for(int i = 0; i < b; i++){
int t;
cin >> t;
if( as.count(t) ) as.erase(t);
else as.insert(t);
}
cout << as.size() << endl;
set을 사용해서…
한 셋에 A의 원소들을 다 넣고, 나중에 B의 원소들을 넣을 때 셋에 그게 이미 있으면 지워주면 된다.
그럼 셋 자체가 대칭 차집합이 됨
</br>
1283: 단축키 지정
https://www.acmcpc.net/problem/1283
주어진 규칙에 따라 단축키 지정하기
vector<string> v;
string s;
getline(cin, s);
string temp = "";
for(int j = 0; j < s.size(); j++){
if( s[j] != ' ' ){
temp.append(1, s[j]);
}
else if( temp.size() ){
v.push_back(temp);
temp = "";
}
}
if( temp.size() ){
v.push_back(temp);
}
int j = 0;
for( ; j < v.size(); j++){
char c = tolower(v[j][0]);
if( !alphabet[c-'a'] ){
alphabet[c-'a'] = 1;
for(int k = 0; k < j; k++){
cout << v[k] << ' ';
}
cout << '[' << v[j][0] << ']' << v[j].substr(1, v[j].size()-1) << ' ';
for(int k = j+1; k < v.size(); k++){
cout << v[k] << ' ';
}
cout << '\n';
break;
}
}
if( j == v.size() ){
int jj = 0, kk = 0;
for(j = 0; j < v.size(); j++){
for(int k = 0; k < v[j].size(); k++){
char c = tolower(v[j][k]);
if( !alphabet[c-'a'] ){
alphabet[c-'a'] = 1;
kk = k;
jj = j;
break;
}
}
if( kk ) break;
}
if( kk ){
for(int k = 0; k < jj; k++){
cout << v[k] << ' ';
}
for(int k = 0; k < v[jj].size(); k++){
if( k == kk ){
cout << '[' << v[jj][k] << ']';
}
else cout << v[jj][k];
}
cout << ' ';
for(int k = jj+1; k < v.size(); k++){
cout << v[k] << ' ';
}
cout << '\n';
}
else{
for(int k = 0; k < v.size(); k++){
cout << v[k] << ' ';
}
cout << '\n';
}
}
구현 문제다
단축키 등록은 tolower()로 대소문자 구분없이 하면 된다
일단 푸는 거니까 무지성 복붙했는데 프린트는 함수로 따로 빼면 더 나을 거 같긴 함ㅋㅋ
c++에는 split이 없어서 좀 귀찮긴 했던 문제
</br>
1326: 폴짝폴짝
https://www.acmcpc.net/problem/1326
징검다리 건너기
if( step[a] == 1 ){
cout << 1 << endl;
return 0;
}
if( a == b ){
cout << 0 << endl;
return 0;
}
unsigned int ans = -1;
check[a] = 1;
int chk = 0;
queue< pair<int, int> > q;
q.push(make_pair(a, 0));
while( !q.empty() ){
int now = q.front().first;
int d = q.front().second;
if( now == b ){
ans = d;
chk++;
break;
}
q.pop();
for(int i = 1; i < n+1; i++){
if( !check[i] && (i-now) % step[now] == 0 ){
check[i] = 1;
q.push(make_pair(i, d + 1));
}
}
}
if( chk == 0 ) cout << -1 << endl;
else cout << ans << endl;
bfs를 통해서 얻을 수 있다
나는 dfs를 좋아해서 처음에 dfs로 제출했는데 시간 초과 나더라…
for문으로 갈 수 있는 곳인지 확인하고 가면 된다
</br>
1334: 다음 팰린드롬 수
https://www.acmicpc.net/problem/1334
n 초과로 팰린드롬 수 찾기
string add1(string num){
string s = num;
int a = 1;
for(int i = s.size()-1; i >= 0; i--){
if( s[i] == '9' ){
s[i] = '0';
a = 1;
}
else{
if( a ) s[i]++;
a = 0;
break;
}
}
if( a ) s = '1' + s;
return s;
}
// in main()
int i = 0;
for( ; i < s.size(); i++){
if( s[i] != '9' ) break;
}
if( i == s.size() ){
s = add1(s);
s = add1(s);
cout << s << endl;
return 0;
}
if( s.size() % 2 ){
string left = s.substr(0, s.size()/2);
string right = s.substr(s.size()/2+1, s.size()/2);
string rev = left;
reverse(rev.begin(), rev.end());
if( rev <= right ){
left.append(1, s[s.size()/2]);
left = add1(left);
string rev = left.substr(0, left.size()-1);
reverse(rev.begin(), rev.end());
cout << left + rev << endl;
}
else{
left.append(1, s[s.size()/2]);
cout << left + rev << endl;
}
}
else{
string left = s.substr(0, s.size()/2);
string right = s.substr(s.size()/2, s.size()/2);
string rev = left;
reverse(rev.begin(), rev.end());
if( rev <= right ){
left = add1(left);
string rev = left.substr(0, left.size());
reverse(rev.begin(), rev.end());
cout << left + rev << endl;
}
else{
cout << left + rev << endl;
}
}
n이 50자리라서 짱 큰 수다
그래서 반 갈라도 25자리라서 문자열을 수로 변환했다가 다시 문자열로 변환하기 좀 그래서 문자열 채로 1 더하는 함수를 따로 만들었다
ex) 1211
12 11 -> 21 > 11 이므로 그냥 그대로 뒤집은 거 붙여주기
>> 1221
ex) 12345
12 3 45 -> 21 <= 45 이므로 123에 1 더해 줘야 함
>> 12421
그리고, n이 9999…9 같은 경우 한 자리 더 늘어 1000…0이 되므로, 거기 1만 더한 걸 출력해서 예외 처리했다
</br>
좀 틀려서 정답률이 여전히 44퍼 대다
다음 4문제에서 45퍼 찍어야지
</br>
댓글남기기