https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 문제 설명 주어진 문자열의 모든 부분 문자열 중 중복을 제거한 개수를 구하면 된다. 풀이 방법 - HashSet 이중 반복문을 돌면서 HashSet에 substring한 문자열을 추가하고 나면 마지막엔 중복없는 문자열의 개수만 남게 된다. for (int i = 0; i < S.length(); i++) for (int j = i; j < S.length(); j++) set.add(S.substring(i, j + 1); 전체 코드는 다음과 같다. package ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램이다. 풀이 방법 1: 반복문 - 시간 초과 처음 문제를 보고 단순히 i부터 j까지 더하는 식으로 구하도록 프로그램을 작성했으나 시간 초과가 발생했다. for (int line = 0; line < M; line++) { int[] range = Arrays.stream(br.readLine..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 벽 3개를 모두 사용하여 안전 구역을 최대한 많이 만드는 문제이다. 풀이 방법 DFS와 BFS를 혼합하여 사용한다. 먼저 DFS로 벽을 세우고, BFS로는 바이러스를 전파한다. 그렇게 만들어진 안전 구역을 구해가면서 최댓값을 구한다. 먼저 DFS 코드부터 확인하자. private static void buildWall(int count) { if (count == 3) { processMainLog..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 설명 일련의 괄호 문자열이 주어지고 잘려진 쇠막대기 조각의 총 개수를 구하면 된다. 풀이 방법 괄호 문제의 대표적인 해결 방법인 스택을 활용하면 된다. 먼저 여는 괄호인 경우는 일단 스택에 넣는다. 그러다 닫는 괄호를 만나면 그 때 레이저인지 쇠막대인지를 판단한다. 만약 레이저라면 이때까지 넣어뒀던 쇠막대를 모두 자르게 되므로 결과값에 스택의 사이즈만큼 더해준다. 만약 쇠막대라면 그 쇠막대의 길이가 거..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 방법 1. Queue 먼저 모든 사람을 큐에 넣고 K - 1만큼 빼고 다시 큐에 넣는다. 그 후에 빼는 사람은 K 번째가 되므로 큐가 빌 때까지 이 과정을 반복하는 식으로 해결했다. 시간 복잡도는 O(N * K) 이다. while (!queue.isEmpty()) { IntStream.rangeClosed(1, K - 1).forEach(idx -> queue.add(queue.remove())); ans.add(queue.remove()); } 풀이 방법 2. ArrayList 지..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 설명 문자열 S와 T가 주어졌을 때, 주어진 규칙으로 S를 T로 만들 수 있는지 여부를 계산하는 문제이다. 풀이 방법 이 문제는 발상의 전환이 필요하다. S에서 T로 만들려면 모든 경우의 수를 따져야 한다. 하지만 T에서 S로 만드는 것은 'A와 'B' 중 한 가지만 고려하면 된다. T를 S로 만드는 방법은 다음과 같다. A로 끝나면 마지막 문자를 제거한..