전체 글

[BOJ/JAVA] 1541번: 잃어버린 괄호

1541번: 잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 키워드 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 구현 괄호를 적절히 친다는 것, 언제 최소가 되는지 확인해야 한다. 일단 -를 만나면 그 앞부터 -를 만나거나 끝날 때 까지 +연산을 계속 한뒤, 앞의 수와 -연산을 한다. 예를 들어 1-2+3+4-7 가 있다면 1 뒤에 - 를 만났으므로, 괄호 연산을 하여 -를 만나기 전 까지 즉 (2+3+4) 연산을 한 뒤 앞의 수(1)와 -연산을 한다. 숫..

[BOJ/JAVA] 5582번: 공통 부분 문자열

5582번: 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 키워드 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 구현 대표적인 LCS문제. 두 문자열 중 공통 부분 문자열을 찾는 것이다. DP를 통해 효율적으로 찾자 cache[][] 배열을 생성하여 [i][j]는 첫 문자열이 i에서 시작하고, 두번에 문자열이 j에서 시작하는 공통 부분 문자열의 길이를 저장한다. 현재 i의 문자와 j의 문자가 같으면 i, j 각각 + ..

[BOJ/JAVA] 2607번: 비슷한 단어

2607번: 비슷한 단어 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 키워드 두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 **한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우**에 이들 두 단어를 서로 비슷한 단어라고 한다. 구현 가장 처음 입력 받는 단어를 26개 배열에 각 알파벳의 갯수를 대입한다. 다음으로 입력 받는 데이터는 각 알파벳 배열에서 빼는 연산을 하고, 각 절댓값을 더한다. 만약 결과에서 음수라면 추가적으로 데이터를 가..

[JAVA/EXCEPTION] Class ConcurrentModificationException

ConcurrentModificationException (Java SE 19 & JDK 19) 발생 다음과 같은 코드가 있다고 하자. TreeSet을 사용하였으며, 값이 중복되지 않게 들어가며, item 값이 오름차순으로 출력된다. 원하는 출력은 중복이 포함되지 않으므로 2, 3, 5 순서대로 개행되면서 출력되는 것이다. import java.util.TreeSet; public class ExceptionTest { public static void main(String[] args) { TreeSet treeSet = new TreeSet(); treeSet.add(3); treeSet.add(3); treeSet.add(2); treeSet.add(5); for (int item : treeSet..

[BOJ/JAVA] 10800번: 컬러볼

10800번: 컬러볼 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 키워드 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000) 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000) 구현 공의 색깔의..

[BOJ/JAVA] 3020번: 개똥벌레

3020번: 개똥벌레 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 키워드 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 구현 동굴의 총 높이는 H이다. height 높이로 날아갈 때 부딪히는 석순의 수와, 종유석의 수를 저장을 한다. 석순[], 종유석[] 석순의 길이가 A 일 때 [A] 높이 까지 부딪히는 석순이 존재한다면 석순[A] += 1 연산을 한다. 종유석의 길이가 B 일 때 [H-B+1] 높이 부터 부딪히는 종유석이 존재한다면 종유석[H-B+1] += 1 연산을..

[BOJ/JAVA] 21318번: 피아노 체조

21318번: 피아노 체조 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 키워드 각 악보는 1 이상 10^9 이하의 정수로 표현되는 난이도 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주 시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. 구현 [x,y] 를 구하기 위해 다음 누적합을 구한다. 예시 [5, 4, 2, 8, 7] 의 악보 ..

[BOJ/JAVA] 17615번: 볼 모으기

17615번: 볼 모으기 [17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net](https://www.acmicpc.net/problem/17615) 키워드 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 옮길 수 있는 볼의 색깔은 한 가지이다. 구현 최종적인 형태는 한쪽에는 R만 있고, 한쪽에는 B만 있는 형태가 될 것이다. 옮기는 횟수 가장 좌측의 연속된 색깔의 볼이 R인 경우를 생각해보자 가장 좌측부터 색깔이 달라지기 시작했을 때 B의 갯수와 R의 갯수..

[BOJ/JAVA] 2457번: 공주님의 정원

2457번: 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 키워드 꽃은 모두 같은 해에 피어서 같은 해에 진다. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 구현 문제에서 월마다 며칠이 존재하는지 나와있지만, 사실 중요하지 않다. 꽃은 모두 같은 해에 피어서 같은 해에 진다. 이는 10월에 펴서 3월에 지는 꽃이 없다는 얘기다. 이를 구현하기 위해서..

[BOJ/JAVA] 1543번: 문서 검색

1543번: 문서 검색 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 키워드 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구현 단어의 길이는 50이고, 문서의 길이는 최대 2500이다. 따라서 단순 문자열 비교 알고리즘을 사용하여 구현해도 무방하다. 가장 앞부터 단어를 만족하는지 체크하고, 그 단어 길이 이후 인덱스 부터 다시 문자열 비교 알고리즘을 사용한다. 왜 가장 앞 부터 단어를 만족하는지 체크하는가? → 최대 몇 번 중복되지 않게 등장하는지 체크하기 위해서, 다음 예시를 보자 문서 : AAAAAAAA ..