알고리즘 문제풀이
-
[C++] 백준 5052 - 전화번호 목록(문자열)알고리즘 문제풀이/백준 2022. 5. 2. 00:06
문제 링크 5052번: 전화번호 목록 (acmicpc.net) 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 알고리즘 문자열 배열을 선언해 입력받은 값들을 오름차순으로 정리한다. 오름차순으로 정리했을 때, 앞에 있는 값이 뒤에 있는 값보다 문자열 길이가 길다면 절대 뒤에 값에 포함될 수 없기 때문에 continue로 즉시 연산을 종료해준다. ex) 12345 1345 2345 235... substr()을 이용해 시작 부분과 원하는 만큼의 길이를 인자로 넣어서 부분 문자열을 반환하도록..
-
[C++] 백준 9935 - 문자열 폭발(문자열)알고리즘 문제풀이/백준 2022. 4. 30. 17:17
문제 링크 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 알고리즘 find()와 substr()를 사용해서 while문 무한루프를 돌며 문자열을 찾고 그 앞뒤를 이어 붙이는 방식으로 했는데 2%에서 시간 초과가 나버렸다. find함수를 썼을 때 시간 복잡도가 최대 O(n^2)까지 늘어나니 문자열 한 번만 돌면서 폭탄을 지워줘야 했고, 그렇기 때문에 stack 방식을 활용했다. 문자열을 앞에서부터 돌면서 하나씩 빈 문자열(temp)에 추가한다. ..
-
[C++] 백준 11656 - 접미사배열(문자열)알고리즘 문제풀이/백준 2022. 4. 25. 00:52
https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net substr() - C++ string헤더에 들어있는 부분 문자열 추출 함수. - 시작 지점과 길이를 전달하면 인덱스 시작 지점부터 길이만큼 문자열 반환. string.substr(시작 지점, 길이) - 기본값으로 시작 지점은 0, 길이는 문자열 보다 더 긴 길이가 들어오면 마지막 문자까지만 리턴. - 파라미터를 입력하지 않으면 기본적으로 전체 문자열 리턴 #include #include #include using namespace std; int main(){ ios_bas..
-
[C++] 백준 10610 - 30(문자열)알고리즘 문제풀이/백준 2022. 4. 23. 01:23
문제 링크 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 알고리즘 문자열 형태로 받은 수를 먼저 내림차순으로 정리를 해버리고 30의 배수가 되는지 안되는지 판별 후에 전자의 경우 그대로 출력하고 후자의 경우 -1을 출력한다. 30의 배수 판별법 1. 0으로 끝나야 한다. 2. 각 자리 숫자의 합이 3의 배수여야 한다. 예전에 수학 문제 풀 때 써먹던 기억이 어렴풋이 나면서 어렵지 않게 떠올릴 수 있었다. 30 배수 판별법만 잘 정리해주면 코드 ..