2023. 7. 29. 21:26ㆍAlgorithm/with C++
0. 문제
문제
선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다.
호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다.
선영이는 한국에 두고 온 서버에 접속해서 디렉터리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.
어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.
패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.
파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, "abcd", "ad", "anestonestod"는 모두 패턴 "a*d"와 일치한다. 하지만, "bcd"는 일치하지 않는다.
패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.
다음 N개 줄에는 파일 이름이 주어진다. 파일 이름은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.
출력
총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다.
참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다.
예제 입력 1
3
a*d
abcd
anestonestod
facebook
예제 출력 1
DA
DA
NE
예제 입력 2
6
h*n
huhovdjestvarnomozedocisvastan
honijezakon
atila
je
bio
hun
예제 출력 2
DA
DA
NE
NE
NE
DA
1. 문제 이해
- N, 패턴, N개의 파일 이름을 입력받는다.
- 패턴을 *을 기준으로 split 한다.
- 파일의 앞과 뒤가 패턴에 속하는지 확인한다.
- NA, DE를 출력한다.
2. 제출
가. 런타임 에러
// 백준 9996번: 한국이 그리울 땐 서버에 접속하지
#include <iostream>
#include <vector>
using namespace std;
vector<string> ret;
int n;
string pattern, s;
void split(string input, string delimiter){
auto pos = 0;
while((pos = input.find(delimiter))!=string::npos){
string token = input.substr(0, pos);
ret.push_back(token);
input.erase(0, pos + delimiter.length());
}
ret.push_back(input);
return;
}
int main(){
cin >> n >> pattern;
split(pattern, "*");
for(int i=0; i<n; i++){
cin >> s;
if(ret[0] == s.substr(0,ret[0].length()) && ret[1] == s.substr(s.length()-ret[1].length(),ret[1].length())){
cout << "DA" << "\\n";
}else{
cout << "NE" << "\\n";
}
}
ret.clear();
return 0;
}
런타임 에러가 발생한다.
런타임 에러가 발생하는 이유는 여러 가지가 있을 수 있지만, 이 코드의 경우 아마도 문자열 인덱싱이 문제일 수 있다.
코드에서는 입력 문자열 s의 앞부분과 뒷부분을 substr 함수를 이용해 추출하고 있다.
이때, s.length()-ret[1].length()가 음수가 되는 경우에는 substr 함수가 예외를 발생시킬 수 있다.
예를 들어, 패턴이 "abc*defg"이고, 입력 문자열이 "ab"인 경우에는 s.length()-ret[1].length()가 음수가 된다.
이런 경우에 substr 함수는 예외를 발생시킨다.
나. 수정
// 백준 9996번: 한국이 그리울 땐 서버에 접속하지
#include <iostream>
#include <vector>
using namespace std;
vector<string> ret;
int n;
string pattern, s;
void split(string input, string delimiter){
auto pos = 0;
while((pos = input.find(delimiter))!=string::npos){
string token = input.substr(0, pos);
ret.push_back(token);
input.erase(0, pos + delimiter.length());
}
ret.push_back(input);
return;
}
int main(){
cin >> n >> pattern;
split(pattern, "*");
for(int i=0; i<n; i++){
cin >> s;
if(s.length() < ret[0].length() + ret[1].length()){
cout << "NE" << "\\n";
}else{
if(ret[0] == s.substr(0,ret[0].length()) && ret[1] == s.substr(s.length()-ret[1].length(),ret[1].length())){
cout << "DA" << "\\n";
}else{
cout << "NE" << "\\n";
}
}
}
ret.clear();
return 0;
}
모든 것에 앞서 최소한 주어진 패턴보다는 파일의 이름이 길어야 한다.
pattern보다 주어지는 파일 이름이 짧을 경우 NE를 출력하도록 조건문을 추가한다.
if(s.length() < ret[0].length() + ret[1].length()){
cout << "NE" << "\\n";
}else{ ... }
다. 다른 사람의 코드
#include<bits/stdc++.h>
using namespace std;
int n;
string s, ori_s, pre, suf;
int main(){
cin >> n;
cin >> ori_s;
int pos = ori_s.find('*');
pre = ori_s.substr(0, pos);
suf = ori_s.substr(pos + 1);
for(int i = 0; i < n; i++){
cin >> s;
if(pre.size() + suf.size() > s.size()){
cout << "NE\\n";
}else{
if(pre == s.substr(0, pre.size()) && suf == s.substr(s.size() - suf.size())) cout << "DA\\n";
else cout <<"NE\\n";
}
}
return 0;
}
해당 코드에 비하여 나의 코드는 지나치게 일반화했다.
특히 pre, suf을 구하는 방식이 나의 비해서 더 간단하다.
또한 substr(pos)처럼 입력하면 pos부터 끝까지 문자열을 반환한다.
'Algorithm > with C++' 카테고리의 다른 글
[알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 (0) | 2023.07.31 |
---|---|
[알고리즘] 2559번: 수열 (0) | 2023.07.31 |
[알고리즘] 11655번: ROT13 (0) | 2023.07.29 |
[알고리즘] 1159번: 농구 경기 (0) | 2023.07.29 |
[알고리즘] 10988번: 팰린드롬인지 확인하기 (0) | 2023.07.29 |