본문 바로가기

BOJ749

백준 1644 자바 - 소수의 연속합 (boj 1644 java) 문제 : boj1644 소수의 연속합인걸 일단 생각 안하고 그냥 어떠한 자연수로 이루어진 배열이 있고, 연속한 배열의 부분합이 N인걸 찾는다고 생각해보자. 일단 단순히 모든 범위를 보려면 O(N^2) 이므로 통과할 수 없다. 그렇다고 DP로 풀자니 식이 잘 떠오르지 않았다. 보통 이런류의 연속합은 투포인터를 활용하면 쉽게 찾을 수 있다(원래는 통과할 방법 찾기 전에 대충 어떠한 수가 소수의 연속합으로 몇 번 정도 나오는지 궁금해서 대충 짜보고 돌린건데 통과했다 ㅋㅋ). 투포인터 전략만 잘 세우면 된다. st와 ed라는 두 포인터를 두고 [st, ed] 구간에 포함된 합을 계속 계산하고 있다고 해보자. 시작은 st와 ed 둘 다 배열의 첫번째에 둔다. 이 경우 ed가 증가(다음 칸으로 전진)되면 합이 늘어.. 2022. 4. 5.
백준 15927 자바 - 회문은 회문아니야!! (boj 15927 java) 문제 : boj15927 혹시 고민을 많이 했다면, 풀이를 볼 시 상당히 짜증날 수 있다. 스포성이 다분한 풀이 이므로 최대한 직접 풀어보는걸 추천한다. ------ 입력으로 들어온 문자열은 이하의 3가지 경우가 존재한다. A. 애초에 팰린드롬이 아님 (e.g. 'abcd') B. 팰린드롬이긴한데, 모든 문자열이 동일함 (e.g. 'aaa') C. 모든 문자열이 동일한게 아닌 팰린드롬 (e.g. 'aabaa') 각각 어떻게 처리할지 살펴보면 된다. A -> 처음부터 팰린드롬이 아니므로 가장 긴 팰린드롬이 아닌 부분문자열은 자기 자신이다. 따라서 입력 문자열의 길이를 출력하면 된다. B -> 이 경우 부분문자열 중 팰린드롬이 아닌게 존재할 수 없다. 따라서 -1을 출력하면 된다. 참고로 'a' 와 같이 문.. 2022. 4. 4.
백준 1337 자바 - 올바른 배열 (boj 1337 java) 문제 : boj1337 문제 분류는 정렬과 투 포인터 있긴한데, 내 경우엔 그냥 정렬 없이 그리디로 풀었다. 어떠한 수를 추가할 생각을 하는 것 보다는 그냥 추가해야될게 있던 없던 있다고 치고 해봤을 때, 원래 존재하던게 몇 개 있었는지 확인해 보는 것이 더 간단한 방식일 것이다. 그러니깐 그냥 해당 배열에 있는 값을 HashSet에 모두 넣어서 O(1)로 원하는 수를 찾을 수 있도록 해두고, N개의 수에서 현재 보고 있는 원소의 값을 a라고 하자. 그럼 모든 N개의 a값에 대해 a, a+1, a+2, a+3, a+4를 해시셋에서 확인한다. 그럼 존재하지 않는게 몇갠지 알 수 있다. 그 값 중 가장 작은게 답이다. 예를들어 '예제 입력 4'를 보자. 7 6 1 9 5 7 15 8 이걸 다음과 같이 구해볼.. 2022. 4. 3.
백준 18868 자바 - 멀티버스 Ⅰ(boj 18868 java) 문제 : boj18868 주어진 대로 구현하면 되긴 한다. 내 경우엔 입력받은 값을 전처리해서 좀 더 쉽게 만들었다. 각 우주에 있는 모든 행성의 모든 쌍에 대해 순서대로 규칙을 만들어 하나의 String으로 만들었다. 예를들어 어떤 우주에 4개의 행성이 있었다면 1-2, 1-3, 1-4, 2-3, 2-4, 3- 4 순서대로 모든 쌍을 비교한다. 그래서 "+-+=++"와 같은 형태의 해당 우주의 모든 행성의 크기 규칙에 대한 String을 만드는 것이다. 그럼 최종적으로 M개의 String에 대해 모든 쌍을 확인 했을 때 동일한 String을 가진 행성이 몇 쌍 존재하는지만 확인하면 되는 문제로 변경된다. 즉 모든 쌍에 대한 단순 비교 로직 2개만 있으면 풀 수 있으므로 구현의 복잡도가 많이 줄어든다. .. 2022. 4. 2.
백준 3029 자바 - 경고 (boj 3029 java) 문제 : boj3029 H시간은 H*60*60초 이다. M분은 M*60초이다. S초는 S초이다. 따라서 입력으로 주어진 hh:mm:ss 두 개는 간단히 둘 다 00:00:00부터 몇 초 후인지로 변경할 수 있다. 예를들어 다음의 예시를 보자. (예제 입력 2에서 위아래를 바꾼 예시이다.) 14:36:22 12:34:56 이 때 현재 시간인 14:36:22는 52582초, 나트륨을 던질 시간인 12:34:56은 45296초가 된다. 전자를 st, 후자를 ed라고 해보겠다. 이 때 ed-st를 한다면 기다리는 시간을 알 수 있을 것이다. ed-st = -7286이 된다. 그 말인 즉, 나트륨을 던질 시간은 하루 뒤였다는 얘기이니 (현재 시간의 다음날 12:34:56) 24시간을 더해주면 된다. 즉, ed가 .. 2022. 4. 2.
백준 1187 자바, C++ - 숫자 놀이 (boj 1187 java c++) 문제 : boj1187 감을 제대로 못잡고 있었는데, '수학귀신' 책을 추천해줬던 수학 잘하는 선배같은 동생의 도움으로 풀 수 있었다. 1. 귀납법(귀납 추론)으로 풀 수 있는 문제이다. 1.1 k=1 k를 1부터 증가시켜 나가면서 생각해보자. 우선 k=1일 때, N은 2가 된다. 이 때 2*2-1 = 3개 중 합이 2로 나누어 떨어지는 2개를 뽑는 문제가 된다. 그럼 2*2-1개의 수가 어떻게 나와야 2로 나눌 수 있는 2개를 뽑을 수 있을까? 이 때 모든 경우를 나타내보면 다음과 같다. A. 3개의 수가 모두 짝수일 경우 -> 아무거나 2개 뽑으면 된다. B. 3개의 수가 모두 홀수일 경우 -> 아무거나 2개 뽑으면 된다. C. 3개의 수가 짝수2개, 홀수1개인 경우 -> 짝수 2개를 뽑으면 된다. .. 2022. 4. 1.
백준 5419 자바 - 북서풍 (boj 5419 java) 문제 : boj5419 1. 일단 모든 쌍을 직접 확인해보자! (brute force) n개의 정점 모두에 대해 모든 쌍을 확인하면서 조건을 만족하는지 확인해보면 된다. 이 경우 코드는 아래와 같이 될 것이다. 물론 이대론 O(N^2)이 되므로 시간 내에 통과할 수 없다! 어쨌든 어떠한 점이 자신보다 x가 작거나 같고, y가 크거나 같은지 확인하면 될 것임을 알 수 있다. ArrayList arr = new ArrayList(); void add(Island island) { arr.add(island); } long getAnswer() { long cnt = 0; for (int i = 0; i < arr.size(); i++) { for (int j = i+1; j < arr.size(); j++).. 2022. 3. 31.
백준 1918 자바 - 후위 표기식 (boj 1918 java) 문제 : boj1918 전공자라면 과제로 한 번씩 해봤을 그 녀석이다. 후위 표기식으로 변환하는건 스택을 활용하면 된다. 실제 계산을 할 필요가 없고, 단순히 중위 표기식을 후위 표기식으로 바꾸기면 하면 되므로 실제 연산 결과를 유지하지 않아도 되서 더 쉽게 짤 수 있다(원래대로라면 'A'~'Z'도 스택에 넣어서 연산자에 따라 실제 연산이 진행되야 하지만, 이 문제의 경우 단순히 화면상에 출력만 하면 되므로). 이 문제와는 관계없지만 후위 표기식을 활용해 실제 계산해서 공학 계산기처럼 동작하는 자바 코드는 여기(깃헙)에 있다(오래전에 짠거라 좀 코드가 안이쁘긴하다). 다음과 같이 동작한다. INPUT : 23.3 * (sin3+ 2.5)/ 43.2 OUTPUT : 1.3766071245476987 INP.. 2022. 3. 31.
백준 2170 자바 - 선 긋기 (boj 2170 java) 문제 : boj2170 당연히 전체 위치를 보게되면 -10억부터 +10억까지 봐야하므로 시간초과가 뜬다. 최대 100만개인 N을 기준으로 동작할 방법을 찾아야 한다. 문제에서 제시된 '예제 입력 1'은 이미 그렇게 정렬된 데이터긴 하지만, N개를 전부 x를 기준으로 오름차순으로 정렬했다고 생각하고 어떻게 풀지 한번 생각해보자. 4 1 3 2 5 3 5 6 7 그렇다면 위와 같이 x값 기준 오름차순으로 차례대로 확인할 경우(x값이 동일할 경우 y값 순서는 상관 없음. 그나마 내림차순으로 하면 아주 약간의 대입연산 정도는 줄여볼 수 있는데 의미 없음), 이전 y 값보다 현재의 x값이 작거나 같다면 이어진 항목으로 생각해볼 수 있다. 1-3을 본 후, 2-5를 보자. 현재 보고 있는 x인 2는 이전의 y값인 .. 2022. 3. 30.
백준 16496 자바 - 큰 수 만들기 (boj 16496 java) 문제 : boj16496 당연한거지만 앞에 올수록 더 전체값이 커질만한 순서대로 정렬한 후, 출력해주면 되는 문제이다. 그 정렬 규칙만 잘 정하면 된다. 케이스1 - 예를들어 9와 89999999가 있다. 직관적으로 자리수와 정렬 규칙은 관계가 없음을 알 수 있다. 둘 중 작은 길이의 숫자까지 비교해서 그 중 다른 숫자가 있다면 쉽게 규칙을 정할 수 있다. 이 경우 9를 먼저 놓는것이 당연히 이득이다. 케이스2 - 그럼 98와 98999이 있다면 어떨까? 직관적으로 98999를 먼저 두는 것이 이득임을 알 수 있다. 이 경우는 '케이스1'로는 판단할 수 없는 경우이다. 그렇다면 자리수가 다르면서, 둘 중 작은 자리수까지 비교해도 비교가 안되는 경우를 어떻게 판단할지가 관건임을 알 수 있다. 내 경우 규칙.. 2022. 3. 30.

티스토리툴바