문자열9 [백준] 1593: 문자 해독 - JAVA https://www.acmicpc.net/problem/1593 풀이문자열 W와 S가 주어진다. S를 W의 길이만큼 잘라 그 안의 문자 순서를 바꿨을 때 W로 만들 수 있는 개수를 세는 문제이다. map을 두개 선언하여 하나에는 W에 들어있는 문자와 개수를 담았다. 또 다른 하나는 W의 길이만큼 S를 잘라 개수를 담았다. 슬라이딩 윈도우를 이용해 S를 탐색하면서 map의 개수를 조정하여 map 두 개가 같은지 비교하여 같을 경우 답을 하나 증가시켰다. 메모리: 149420KB시간: 900ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOE.. 2024. 5. 19. [백준] 16120: PPAP - JAVA https://www.acmicpc.net/problem/16120 풀이문자열을 앞에서부터 보면서 'PPAP'가 되면 'P'로 바꿔준다. 최종적으로 'P'가 되면 성공. P가 들어오면 cnt를 1 늘려준다. A가 들어올 때 cnt가 2보다 작다면 PPAP를 만들수 없으므로 실패. cnt가 2이상이고, 다음 글자가 P라면 PPAP를 만들 수 있으므로, cnt를 1 줄여준다(P가 2개 빠지고 새로운 P가 들어오기 때문). 메모리: 20080KB시간: 260ms언어: Java 11import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new .. 2024. 5. 18. [백준] 2179: 비슷한 단어 - JAVA https://www.acmicpc.net/problem/2179 풀이영단어들이 주어지고 두 단어를 앞에서부터 비교하여 공통적으로 나타나는 부분의 길이가 긴 두 단어를 출력해야한다. 한글자씩 비교하기 위해 트라이 알고리즘을 생각했으나, 시간이 충분하고 메모리 제한이 작아서 트라이를 사용하지 않았다. 길이가 같을 경우 주어진 순서대로 앞쪽에 있는 단어가 답이되므로 순서 유지가 되는 ArrayList를 선택했다. ArrayList에 단어를 담고 앞에서 부터 순서대로 비교하여 접두사의 길이와 인덱스를 저장했다. 메모리: 19328KB시간: 2008ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void .. 2024. 5. 17. [백준] 7490: 0 만들기 - JAVA https://www.acmicpc.net/problem/7490 풀이1부터 N까지의 수 사이에 +, -, 공백을 넣어서 수식을 만들고 그 수식을 계산하여 0이 되는 경우 출력해야 한다. 출력할 때 ASCII 순서에 따라 출력하라는 제한이 있어서 공백, +, - 순서로 dfs탐색을 통해 수식을 만들었다. N까지 진행하면 수식을 계산하는 메서드를 통해 0이 나오면 값을 출력한다. 메모리: 17200KB시간: 168ms언어: Java 11import java.io.*;public class Main { static int N; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws.. 2024. 5. 17. [백준] 2607: 비슷한 단어 - JAVA https://www.acmicpc.net/problem/2607 풀이단어가 주어지고, 다음에 주어지는 단어들이 첫번째 단어와 비슷한 단어인지 체크하는 문제이다. 비슷한 단어란 다음과 같이 판별한다. 1. 길이가 같을 경우, 알파벳의 구성이 같다. 2. 길이가 다를 경우 알파벳 하나를 더하거나 빼서 같은 구성으로 만들 수 있다. 첫 번째 단어를 길이 26의 int배열로 받아 비교해주었다. 비교할 단어를 위의 int배열과 비교하여 구성이 같은지 판단하여 cnt라는 개수로 체크한다. 두 단어의 길이가 같을 경우 cnt가 첫 단어의 길이와 같거나 cnt가 첫 단어의 길이보다 1 작다면 만족한다. 비교하는 단어가 1만큼 작을 경우, 첫 단어에 존재하는 알파벳과 다른 알파벳을 가지고 있으면 안된다. 즉, cnt가.. 2024. 5. 17. [백준] 9081: 단어 맞추기 - JAVA https://www.acmicpc.net/problem/9081 풀이C++에 있는 next permutation 함수를 구현하는 문제이다. 어떤 문자가 주어지면 그 문자의 알파벳들로 만들 수 있는 문자들 중 처음 주어진 문자의 다음에 올 문자를 찾는 문제였다. 조합으로 모든 경우를 만들어 set에 넣는 방식으로 구현하였는데 메모리초과로 실패했다. next permutaion이란 방법을 찾아 구현해보았다.1. 뒤에서부터 탐색하여 증가하지 않는 첫번째 인덱스를 찾는다.2. 다시 뒤에서부터 탐색하여 찾은 인덱스의 값보다 처음으로 큰 값이 나오는 인덱스를 찾는다.3. 두 인덱스의 값을 바꾸고 인덱스 뒤 부분을 정렬하여 붙인다.따라서, 주어진 단어를 int배열로 만들어 구현했다. 뒤에서부터 탐색해 값이 감소하는.. 2024. 5. 14. [백준] 2800: 괄호 제거 - JAVA https://www.acmicpc.net/problem/2800 풀이브루트포스 문제. 괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다. 서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다. 서로의 짝의 번호를 배열에 저장했다. 짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여 출력할지 안 할지를 저장했다. 중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다. 메모리: 24900KB시간: 280ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12. [백준] 12919: A와 B 2 - JAVA https://www.acmicpc.net/problem/12919 풀이문자열, 브루트포스 문제이다. A와 B로만 이루어진 단어들이 있는데 첫번째 주어지는 단어(S)로 두번째 단어(T)를 만들 수 있는지 확인하는 문제이다. 문자열을 바꿀 때는 "문자열의 뒤에 A를 추가한다", "문자열의 뒤에 B를 추가하고 문자열을 뒤집는다" 이 두가지의 연산이 가능하다. S에서 T를 만드려면 두 가지 연산을 모두 시도해야 하지만 T에서 S를 만들 때는 문자열의 뒤에 A가 있는지, 문자열의 앞에 B가 있는지 확인하여 그 경우에만 연산을 하면 된다. 문자열을 뒤집는 방법으로는 for문을 이용한 방법과 StringBuilder의 reverse를 이용한 방법이 있다. String reverse = "";for (int i = .. 2024. 5. 12. [백준] 28070: 유니의 편지 쓰기 - JAVA https://www.acmicpc.net/problem/28070 풀이누적합으로 풀 수 있는 문제이다. (입대 월)에는 배열에 +1을 해주고 (전역 월 + 1)에는 배열에 -1을 해준다. 2000년 1월부터 9999년 12월까지 돌면서 이전 배열의 것을 더해준다. 메모리: 81920KB시간: 824ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = I.. 2024. 5. 11. 이전 1 다음