string10 [Problem Solving] BOJ 1431 : 시리얼 번호 문제 링크 : https://www.acmicpc.net/problem/1431 다음과 같은 기준으로 문자열 리스트를 정렬하는 문제이다.1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 우선 serealList = sorted(serealList, key=len)으로 짧은 문자열을 앞쪽으로 오게 한다.그 다음 compare 함수를 기준으로 Bubble Sort를 수행한다. compare(A, B) 함수는 다음과 같이 동작한다.1. 문자열의 길이가 .. 2025. 2. 7. [Problem Solving] BOJ 5052 : 전화번호 목록 문제 링크 : https://www.acmicpc.net/problem/5052 입력받은 문자열에서 한 문자열이 다른 문자열의 접두어라면 NO를 출력, 그런 경우가 없다면 YES를 출력하는 문제이다.위와 같은 자료구조를 Trie라고 한다.우선 입력받은 문자열을 모두 Trie 구조에 삽입한다.각각의 노드는 값과 자식 노드를 담는 리스트를 가지고 있다. Trie 구조에 문자열 number를 삽입하는 과정은 다음과 같다.1) 현재 노드의 자식 노드 중에서 number[0]와 같은 값을 가진 노드가 있다면, 그 노드에 number[1:]을 삽입한다.2) 현재 노드의 자식 노드 중에서 number[0]와 같은 값을 가진 노드가 없다면 값이 number[0]인 새로운 노드를 만들어서 현재 노드의 자식 노드 리스트에.. 2025. 1. 31. [Problem Solving] BOJ 5525 : IOIOI 문제링크 : https://www.acmicpc.net/problem/5525 패턴을 선형적으로 찾으면 100점을 받을 수 없는 문제이다. 슬라이딩 윈도우의 방식으로 문제를 해결해야한다. 우선 cnt는 패턴에서 O의 개수이다.1. S_0부터 S_M-2 까지 IO로 시작하는 부분이 있는지 찾는다. (S_i == I and S_i == O)2. 그 시작하는 부분의 뒷부분이 IOI로 이어진다면(j = i + 1일 때, S_j = O and S_j+1 = I), cnt를 1 증가시키고, j를 2만큼 증가시킨다.3. cnt가 N과 같다면, 즉 P_N과 일치하는 패턴이 하나 발견되었다면, and를 1증가시키고, 가장 찾은 지 오래 된 IO를 cnt에서 제외시키기 위해 cnt를 1감소시킨다.4. 더이상 IOIOI의 .. 2025. 1. 19. [Problem Solving] BOJ 17413 : 단어 뒤집기 2 문제 링크 : https://www.acmicpc.net/problem/17413 안에 있는 것은 포함해서 그대로 출력하고, 아닌 것은 공백 단위로 끊어서 거꾸로 뒤집어서 출력한다. 1. 공백이 아닌 문자를 만난 경우스택에 문자를 추가한다.2. 공백 또는 i가 마지막 인덱스인 경우스택에 있는 것을 모두 출력하고 공백 출력3. 스택 top을 순서대로 모두 출력하고, 를 그대로 출력 #include #include #include #include #include #include #include #include #include #include #define endl '\n'using namespace std;string S;void input(){ getline(cin, S);}void solution(.. 2025. 1. 11. 이전 1 2 다음
