L.O.K

20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net ◎ 문제풀이 문자열 안의 부분문자열 중에서 특정 문자로 시작해서 끝나는 문자열 중 해당 문자가 K개 있는 경우의 최소길이와 최대길이를 구하는 문제이다. 문자열 안의 특정문자 K개를 찾아야 하므로 반복문이 중첩될 수 밖에 없는데, 문자열의 길이는 최대 10,000이다. 그러므로 시간초과가 발생하지 않도록, 가지치기를 할 필요가 있다. 1. 문자열 내 알파벳 별 개수 파악하기 알파벳 개수를 파악하여 K개보다 작으면 반복을 하지 않는다. 2. 문자열 탐색 문자열 앞..

12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net ◎ 문제풀이 문제를 보고 DFS 알고리즘을 잘 떠올렸으나 시간초과가 발생하였다. Source를 Target으로 만들기 위해 DFS로 모든 경우를 탐색하였다. 문제를 풀면서도 시간초과를 예상하기는 했다. Source 끝에 A를 추가하거나 Source 끝에 B를 추가하거 뒤집어야 한다. Source와 Target의 길이 차이만큼 경우의 수는 2ⁿ 으로 늘어난다. Target의 최대길이가 50이므로 경우의 수는 2의 49승까지 ..

9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net ◎ 문제풀이 사전 순서로 할 때, 주어진 단어의 알파벳으로 구성된 주어진 단어의 다음 단어를 찾는 문제이다. 처음에는 DFS로 풀었다. DFS로 사전순서대로 탐색하다가 주어진 단어의 다음 단어를 찾는 식이었다. 그런데 이는 메모리 초과가 발생했다. DFS를 하려면 방문처리를 위한 배열도 생성해야 하는데, 그런거 없이 오로지 문자열만을 조작하여 문제를 풀어야 했다. 어떠한 알고리즘이 필요한 거였는데, 잘 몰라서 구글링을 하였다. 원리는 생각보다 복잡했다..

17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net ◎ 문제풀이 앞뒤 방향으로 문자열이 같으면 회문, 한 문자만 다르면 유사회문이라고 한다. 회문이면 0, 유사회문이면 1, 그외 문자열은 2를 출력하는 문제이다. 투포인터를 떠올리기는 했으나 재귀호출을 발상하지 못해 문제풀이가 어려웠다. LEFT , RIGHT를 하나씩 비교하며 나갈 것이다. 그럼 이렇게 서로 다른 부분을 만날 수 있다. 경우는 2가지가 있다. 1) LEFT 포인터 문자를 제거하는 경우 2) RIGHT 포인터 문자를 제거하는 경우 1)인 경우와 2)인 경우를 재귀호출을 활용하여 ..

2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net ◎ 문제풀이 문제가 복잡해 보이나 이해를 하면 어려운 문제는 아니다. 복잡한 개념이 들어가 있지는 않으나 구현력이 필요한 문제였다. 크게 두 가지 과정이 있다. 1) 로마 숫자를 십진법 숫자로 만들기 2) 십진법 숫자를 로마숫자로 만들기 - 로마 숫자를 십진법 숫자로 만들기 1) 로마문자와 십집법 숫자가 매핑된 Map 자료구조를 만든다. 2) 로마숫자를 좌측부터 한 문자씩 읽어온다. 3) 현재 문자는 이전 문자보다 작아야 한다. 4) 현재 문자가 이전 문자보다 크다면 XL, XC , CD ,CM ... 이런 문자..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net ◎문제 풀이 문자열 s가 주어질 때, 주어진 여러 개의 문자열 조합으로 s를 만들 수 있는지를 묻는 문제이다. 조합을 만드는 문제는 재귀호출로 풀면된다. 적절한 가지치기 조건을 두어 DFS 탐색을 하면 문제를 풀 수 있다. ◎코드 import java.util.Scanner; //BOJ165000 문자열 판별 ( 백트래킹 ) public class Main { public s..

17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net ◎ 문제풀이 문자열을 조작하는 문제이다. 파이썬은 다양한 문자열 조작 함수를 제공하기에 간편하게 풀 수 있다. 문제의 목적은 태그(특수문자), 공백(특수문자)로 구분되는 문자열을 뒤집기이다. 문자열을 뒤집는 함수인 reverse()와 특수문자를 구분하는 isalnum()을 이용하면 문제에 쉽게 접근할 수 있다. 1) Pointer 하나를 만들고 문자열을 탐색한다. 2) 태그를 만나면 태그가 끝날때 까지 Pointer를 1씩 증가한다..

1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 1. 문제 추상화 "666"이 들어간 수를 작은 순서대로 시리즈 넘버로 한다. N번째 시리즈의 번호를 구하라. 2. 알고리즘 API를 이용하면 굉장히 쉽게 풀 수 있는 문제다. String 객체의 contains() 메소드를 이용하여, 작은 수부터 666이 들어간 모든 경우의 수를 조사하면 된다. [ 브루트 포스 ] 그러나 나는 규칙성을 찾는 도중 재귀함수 냄새를 맡았고 재귀함수로 풀려다가 실패했다. contains() 메소드를 알고 있었지만 기억하지 못했다...

2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 1. 문제 추상화 입력받은 문자열에서 크로아티아 문자가 사용된 횟수를 구하시오. 2. 알고리즘 첫 번째 방법 String API 이용하기 ( replaceAll 메소드 ) 두 번째 방법 if- else if 문으로 탐색하기 3. 풀이 첫 번째 방법 import java.util.Scanner; public class Main { public static void main(String[] args) { String[] croa..

2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net 1. 문제 추상화 입력된 두 개 정수를 역순으로 변환 후 크기가 큰 정수를 출력하라. 2. 알고리즘 첫 번째 방법 정수 % 10 연산을 사용하여, 1의 자리 수부터 역순으로 String 변수에 붙이기 두 번째 방법 API 이용하기 (StringBuilder 클래스) 3. 풀이 첫 번째 방법 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io..