본문 바로가기

문자열

 (11)
[백준 / BOJ] 19585 전설 (cpp / Java) 문제 출처 : https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net C개의 색상, N개의 닉네임, Q개의 팀이 주어진다. 이때, Q개의 팀중 색상+닉네임 으로 이루어진 팀은 "Yes" 아닌경우 "No"를 출력하는 문제다. 풀이 Trie + 해싱 알고리즘으로 푼 문제다. 색상과 닉네임을 모두 Trie구조로 만들경우, 색상의 최대길이 * 닉네임의 최대길이 * 팀의 최대 갯수 = 1000 * 1000 * 20000이 되어서 TLE가 나온다...
[백준 / BOJ] 1195 킥다운 문제 출처 : https://www.acmicpc.net/problem/1195 1195번: 킥다운 첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 www.acmicpc.net 두개의 기어파트가 주어진다. 각 기어파트는 1과 2로 이루어져있는데, 1은 '홈(들어가있는 부분)' 2는 '이(나와있는 부분)'를 나타낸다 이 때, 두개의 기어파트를 적절히 조합하여 조합된 기어파트의 길이의 최솟값을 구하는 문제다. 풀이 기어의 길이가 최대 100이므로 완전탐색으로 풀리는 문제다. 문제에서 주어진 그대로 구현하면 되는데, 몇가지 주의할 점 이 있다. - 기어가 맞물린..
[백준 / BOJ] 12904 A와 B 문제 출처 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자 'A'와 'B'가 주어진다. 두 문자를 아래와 같은 규칙으로 연결해 문자열 T를 만든다. 1. 문자열 뒤에 A를 붙인다. 2. 문자열 을 뒤집고 뒤에 B를 붙인다. 이때, 문자열 S를 이용해 문자열 T를 만들 수 있는지 알아내는 프로그램을 만드는 문제다. 풀이 아이디어 문제다. 문자열 S를 이용해 문자열 T를 만들려면, 매 선택마다 2가지 ..
[백준 / BOJ] 1498 주기문 문제 출처 : https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 어떤 문자열 X를 n번 연달아 쓴 것을 X^n으로 나타낸다. 예를들어, 문자열, ababab는 ab^3이 된다. 문자열 X를 앞에서부터 i번째까지 주기문을 이룬다고 했을때, 해당 주기문의 n(n은 가능한 가장 크게)을 구하는 문제다. 예를들어, 문자열 abababab는 4 2 6 3 8 4 가 출력된다. 풀이 kmp로 푸는 문제였다. 주기를 찾는다는것은 ..
[백준 / BOJ] 1097 마법의 단어 문제 출처 : https://www.acmicpc.net/problem/1097 1097번: 마법의 단어 첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이다. 단어는 알파벳 대문자로만 이루어져 있다. 마 www.acmicpc.net N개의 단어가 있다. N개의 단어를 적절히 조합하여 (이때, N개의 단어를 전부 사용해 조합해야한다) 문자열 T를 만든다. 문자열 T의 시작지점을 i만큼 오른쪽으로 이동시켰을때 문자열을 T(i)라 한다. (문자열 ABCD를 오른쪽으로 2만큼 움직인후 문자열은 CDAB가 된다.) 이때, 문자열 T와 바뀐문자열 T(i)가 정확히 일치하게되는 i가 k개 있으면, 이 문자열을 "마법의..
[백준 / BOJ] 1747 소수 & 팰린드롬 문제 출처 : https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 숫자 N이 주어졌을때, N보다 크거나 같은수중 소수이면서 팰린드롬인 수중 가장 작은 수를 찾는문제다. 풀이 에라토스테네스의 채를 이용해 풀은문제다. 우선, 에라토스테네스의 채의 최대 범위를 지정해주기위해, N = 1,000,000일때, 소수이면서 팰린드롬인 수중 가장 작은수를 찾아보면, 1003001 이라는것을 알수있다. 따라서, 소수를 걸러주기..
[백준 / BOJ] 5430 AC 문제 출처 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 선영이는 AC라는 언어를 만들었다. AC정수배열에 연산을 하기위해 만든 언어이다. AC에는 R, D가 주어진다. R은 주어진 정수배열을 뒤집는 연산이고 D는 현재 정수배열의 가장앞 정수를 없애는 연산이다. 정수배열과 연산이 주어졌을때, 결과를 출력하는 문제였다. (지울수없는경우 error를 출력한다.) 풀이 구현 문제였다. 문자열 구현이 약한거같아서 일부러 찾아 푸는중인데, 역시나 구현이 쉽지는 않았다. 모든 연산에 대해 시뮬레이션을 수행..
[백준 / BOJ] 1701 Cubeditor 문제 출처 : www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net Cubelover는 텍스트 에디터 Cubeditor를 만들었다. 이 에디터가 다른 에디터와 다른점은, 찾을려하는 문자열이 2번이상 존재해야지 찾는것이다. 예를들어, ababac에서 aba를 찾을려하면 ababac 이렇게 찾을수있다. c를 찾을려하면 c는 한번밖에 나오지 못하므로 찾지못한다. 풀이 완전탐색으로 풀려할경우, 약 5000^3 반복할수있어서 시간초과가..

티스토리툴바