본문 바로가기

Algorithm/문자열 처리

Baekjoon 5525 IOIOI 2019. 11. 11. Link https://www.acmicpc.net/problem/5525 결과 2844KB / 12 ms 언어 C++ 17 풀이 Hash를 이용하여 문제를 해결 string을 이용한 방법으로도 해결 가능할 듯 보인다. I를 1 O를 0인 2진수로 생각해 해시를 구성한다. 매 순간 특정 지점에서 해시를 구하면 string과 같은 복잡도가 나오거나 더 나오기 때문에 슬라이딩 윈도우처럼 값을 빼고 더하면서 해시를 구하면 O(n) 시간에 해시를 구할 수 있다. 비교할 해시랑 매 순간 구해지는 해시를 비교하면서 일치하는 개수를 구하면 된다. 소스코드 #include using namespace std; const int MAX = 1000000; const int MOD = 100000007; int targe..
Baekjoon 2870 수학숙제 2019. 8. 23. Link https://www.acmicpc.net/problem/2870 소스결과 2128 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 문자열 처리, 정렬 설명 문자와 숫자가 섞여있는 문자열에서 숫자만 뽑아 오름차순으로 출력하자. 문자열 파싱할 때 자주 볼법한 문제 굳이 숫자로 안바꿔도 문제가 없다. 파싱 알고리즘만 잘짜면 쉬운 문제다. 소스코드 #include #include #include #include using namespace std; string converting(string& str) { string res; if (str.length() == 1) res = str; else { int zeroCounting = 0; while (str[zeroCounting] ==..
Baekjoon 9536 여우는 어떻게 울지? 2019. 8. 23. Link https://www.acmicpc.net/problem/9536 소스결과 2124 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 문자열 처리 설명 숨겨진 여우의 울음소리를 찾아라 이 문제는 개인적으로 자바로 풀면 쉬울 듯 하다. 문제 난이도에 비해 입출력 때문인지 정답률이 낮다. 알고리즘 1. 첫 라인의 모든 값을 입력 받아 토큰화하여 벡터에 저장한다. 2. 동물 울음소를 입력받아 토큰화 시켜 저장한다. 3. 비교해서 일치하지 않는 울음소리를 출력한다. 소스코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int tcc; cin >>..
Baekjoon 1919 애너그램 만들기 2019. 8. 21. Link https://www.acmicpc.net/problem/1919 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 문자열처리 설명 두 문장이 애너그램이 되기 위해서 지워야 하는 문자의 개수를 출력하자 알고리즘 1. 첫번째 문자열의 각 문자 개수를 배열에 저장한다. 2. 두번째 문자열의 각 문자 개수를 배열에 저장한다. 3. a ~ z 까지 큰 수 - 작은 수를 합해 출력한다. 소스코드 #include #include #include using namespace std; int main() { int alphaTop[26] = {}, alphaBot[26] = {}, res = 0; string top, bot; cin >> top >> bot; for (int i..
Baekjoon 10988 팰린드롬인지 확인하기 2019. 8. 21. Link https://www.acmicpc.net/problem/10988 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 문자열처리 설명 입력받은 문자인지 앞으로 뒤로 읽어도 똑같은 문자인지 출력하자 알고리즘 절반 나눠서 앞뒤로 확인하면 된다. 소스코드 #include #include using namespace std; int main() { string input; cin >> input; bool res = true; for (int left = 0, right = input.length() - 1; left
Baekjoon 1032 명령 프롬프트 2019. 8. 21. Link https://www.acmicpc.net/problem/1032 소스결과 1988 KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 문자열처리 설명 파일 이름들이 주어질 때 알맞은 패턴을 출력한다. N이 최대 50, 글자길이도 최대 50, 최악의 경우 탐색 횟수는 50 * 50으로 한정된다. 첫번째 파일 이름의 각 자리를 기준으로 나머지 파일을 탐색해 패턴을 찾아내면 되는 문제다. 알고리즘 1. 첫번째 파일의 i번째 문자를 기준 문자로 삼는다. 2. 파일을 순서대로 기준문자와 비교해 패턴을 제작한다. 소스코드 #include using namespace std; const short MAX = 50; int main() { int cnt; cin >> cnt; char fileLi..
Baekjoon 1100 하얀 칸 2019. 8. 21. Link https://www.acmicpc.net/problem/1100 소스결과 1984 KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 문자열 처리, 탐색 소스코드 #include using namespace std; const short MAX = 8; int main() { char board[MAX][MAX+1] = {}; int res = 0; for (int i = 0; i > board[i]; for (int i = 0; i < MAX; i++) { // Odd if (i % 2) { for (int j = 1; j < MAX; j += 2) if (board[i][j] == 'F') res++; } // Even else { for (int ..
Baekjoon 2902 KMP는 왜 KMP인가? 2019. 8. 21. Link https://www.acmicpc.net/problem/2902 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 문자열처리 소스코드 #include using namespace std; const short MAX = 100; int main() { char input[MAX + 1] = {}; char res[MAX + 1] = {}; cin >> input; bool trigger = true; int pos = 0; for (int i = 0; input[i] != '\0'; i++) { if (trigger) { if ('A'

티스토리툴바