본문 바로가기

BOJ749

백준 14911 자바 - 궁합 쌍 찾기 (BOJ 14911 JAVA) 문제 : boj14911 1. 주어지는 수의 개수가 주어지지 않으므로 입력받기 전에 총 배열의 크기를 알 수 없다. 미리 최대 개수 배열을 만들어 입력받은 후 처리하거나, 자바의 split 합수를 사용해 처리하면 된다. 2. 최대 개수가 10개밖에 안되므로 모든 경우의 수를 보면 된다. 다만 주의점은 사전 순으로 출력해야 한다는 부분인데, 이를 위해 정렬 후 모든 경우를 보면 된다. 또한 문제에 명시적으로 나타나진 않았으나, '사전 순으로 앞서는 기준은 a < c이거나, a == c 이면서, b < d 인 것' 에 따라 a==c이면서 b==d인 경우는 정의되지 않은 것을 알 수 있다. 따라서 서로 다른 쌍이라 할지라도, 동일한 출력값은 출력하면 안된다. 예를들어 입력이 1 1 1 1 1 2 와 같을 경우.. 2021. 12. 15.
백준 23716 자바 - Transform the String (BOJ 23716 JAVA) 문제 : boj23716 로직 자체는 별게 없다. S의 모든 문자열에 대해 각각 F의 각 문자열을 순회하며 가장 차이가 작은 문자를 고르면 된다. O(|S||F|) 다만 자바 한정으로 난이도가 급상승하는데, String으로 받는 순간 메모리 초과가 된다 ㅋㅋㅋㅋ (String은 char 배열형태이고, char은 2byte가 필요하다. byte 자료형은 1byte이다. -128~127까지 표현 가능하지만 어쨌든 소문자 표현은 가능하다.) C++이나 파이썬의 겨우엔 그냥 받아진다. 자바는 그래서 어떻게 해야 하냐면, character 배열인 String을 쓰면 안되고 모든 문자를 byte단위로 처리해야 한다. 따라서 byte 단위로 한 문자씩 입력받아 처리해야 한다. 아마 차후 자바의 경우 추가 메모리가 주.. 2021. 12. 14.
백준 9327 자바 - 용량 확보 (BOJ 9327 JAVA) 문제 : boj9327 음주코딩이 더 코딩이 잘된다는게 사실인것같다. 평소엔 시간 꽤나 걸리던 골1과 플5 문제가 둘다 한방에 해결됬다. 뭐지.. 이상하다. 아무래도 이것저것 복잡도 계산 해볼 정신머리가 없어서 무지성으로 짜보다 보니 오히려 빨리 해결하는 것 같다 ㅋㅋㅋ 결국 입력으로 주어진 n개의 용량x2에 대해 존재 가능한 모든 합의 경우의 수 중, 확보하려는 용량 e보다 같거나 큰 것 중 가장 가까운걸 출력하면 된다. 예를들어 n개가 400 600 700 일 경우 존재 가능한 모든 합의 경우의 수는 다음과 같다. 400 1000 1100 600 1300 700 이걸 정렬하면 400 600 700 1000 1100 1300 이 되고, 이 중 만약 e가 1050이라면 1050보다 같거나 큰 수중 가장 .. 2021. 12. 13.
백준 9213 자바 - 꽤 좋은 수 (BOJ 9213 JAVA) 문제 : boj9213 골드1 치곤 좀 쉬웠으나, 확실히 아이디어를 생각하긴 어려울수도 있을 것 같다. 우선 약수의 합을 구해보자. 소수판정 때 쓰던 에라토스테네스의 체를 쓰던 방식을 응용해서 소수를 구하는 것이 아니라, 약수를 구해 더해주면 각 수의 약수 의 합을 구할 수 있다. (코드 initBadness() 참고) 약수의 합을 구하는 것이므로, 에라토스테네스의 체의 최적화 방식인 sqrt(N) 까지가 아니라, N/2 까지 봐야 한다ㅇ 그럼 이후 [start, stop] 구간에 대해 미리 구해둔 약수의 합을 참고하여 i-arr[i]의 절대값이 badness 이하라면 카운팅하면 된다. 여기서 offline query + mo's algorithm까지 사용한다면 더 효율적으로 가능하겠으나 위의 방식으로 .. 2021. 12. 13.
백준 2143 자바 - 두 배열의 합 (BOJ 2143 JAVA) 문제 : boj2143 1. 부 배열을 이따 생각하고, 일단 X랑 Y라는 두 배열이 있는데 두 배열의 각 원소를 하나씩 더한 합이 T가 되는 경우부터 생각해보자. 아래와 같은 X, Y 배열이 있다. 1.1 가장 간단히 X[i] + Y[j] 가 T가 되는걸 찾는 방법은 모든 X의 원소에 대해 Y의 모든 경우의 수를 전부 확인해보면 된다. X[0]+Y[0] 확인, X[0]+Y[1] 확인, ... , X[1]+Y[0] 확인, X[1]+Y[1]확인, ... X[2]+Y[3] 확인. 이 경우 X의 개수 * Y의 개수 만큼 봐야 한다. O(XY) 1.2 1.1보다 더 빠르게 할 수 있는 방법이 있다. Y를 정렬한 후 O(YlogY), 각 X에 대해 T-X[i]가 Y에 있는지를 이분탐색으로 찾는 방식이다. 이 경우 .. 2021. 12. 13.
백준 2014 자바 - 소수의 곱 (BOJ 2014 JAVA) 문제 : boj2014 1. 문제 이해 문제를 다소 이해하기 힘들 수 있는데 문제를 이해하기 쉽게 써보면 다음과 같다. 예를들어 2,5,7이 입력으로 주어졌다면 이하의 수식으로 나온 결과 중 N번째로 작은 수를 구하면 되는 것이다. (단, i,j,k가 모두 0이면 안됨. 그리고 K(k와 다름. 문제에서 주어진 K) 가 늘어나면 물론 i,j,k 외에도 더 추가해주면 됨.) 2. 해결 로직 생각해보기 근데 i, j, k를 임의로 정해서 작은 수를 찾기에는 뭐부터 해야지 작은수부터 차례대로 나올지 알 수 없다. 또한 무한정 i, j, k를 늘려나가기엔 당연히 무리가 있다. 따라서 처음에 주어진 K개를 모두 넣어두고 작은 수부터 차례대로 K개의 소수를 곱해 넣고, 그 결과중에서도 다시 작은 수부터 차례대로 K개.. 2021. 12. 12.
백준 14413 자바 - Poklon (BOJ 14413 JAVA) 문제 : boj14413 1. update가 없는 쿼리 문제로, 오프라인 쿼리로 처리해도 된다. 또한 각 쿼리마다 범위가 계속 변경되는 와중에 원하는 답을 구하는 쿼리 문제이다. 따라서 mo's algorithm을 사용할 경우 효율적으로 풀 수 있다. 모스 알고리즘은 쿼리의 수가 n이고 각 쿼리 qi = (a, b)라 할 때(문제에선 l, r이었음. l이 헷갈려서 a, b로 변경하여 설명함), 모든 쿼리를 (a/sqrt(n), b) 순서로 정렬하게 된다(a/sqrt(n)은 소수점 버리고 정수로). 이 경우 각 쿼리를 정렬 후 수행 시 모든 경우에 대해 a와 b의 변화량이 최대 N*sqrt(N) 정도로 고정되고, 효율적으로 직전에 구해둔 쿼리의 데이터 중 중복되는 부분을 재사용할 수 있다. 예를들어 q1=.. 2021. 12. 11.
백준 7585 자바 - Brackets (BOJ 7585 JAVA) 문제 : boj7585 괄호를 제외한 나머지 문자는 모두 쓸모없다. 예를들어 '예제 입력1'은 다음과 동일한 데이터이다. 이제 올바른 괄호쌍인지만 판단하면 되는데, 스택을 사용하면 간단하다. 1. 여는 괄호 (, {, [ 를 만날 시 스택에 해당 괄호를 넣는다. 2. 닫는 괄호 ), }, ] 를 만날 시 스택에서 하나를 pop한다. pop한 결과가 동일한 형태의 여는 괄호가 아닐 경우 (예를들어 ']'에서 pop을 하니 '('가 나온 경우) Illegal이다. 3. 최종적으로 1, 2의 과정을 문자열 끝까지 진행하고 스택에 남은게 아무것도 없다면 Legal, 뭐라도 남아있다면 쌍이 안맞는 것이니 Illegal이다. 코드 : github import java.io.BufferedReader; import .. 2021. 12. 11.
백준 14382 자바 - 숫자세는 양 (Large) (BOJ 14382 JAVA) 문제 : boj14382 INSOMNIA인 경우부터 생각해보자. 일단 각 자리 중 1~9중 어느 수라도 들어가면 배수에서 모든 수가 나타날 수 있다. 따라서 INSOMNIA인 경우는 n이 0인 경우 하나 뿐이다. 그 외의 경우는 실제로 n, 2n, 3n, ...을 해보면서 각 자리수에 포함된 숫자들을 찾아내어 모든 수를 찾았는지 확인하면 된다. 모든 수를 찾는 것은 미리 0~9까지를 넣은 해시를 준비해두고 찾을 때 마다 remove 후 size를 확인해봐도 될테고, 내 경우엔 remain=10 과 boolean 배열을 두고 새로운 수를 찾으면 remain을 감소시켜서 remain이 0이 되면 모두 찾은것으로 판단했다. 코드 : github import java.io.DataInputStream; impo.. 2021. 12. 10.
백준 1011 자바 - Fly me to the Alpha Centauri (BOJ 1011 JAVA) 문제 : boj1011 다른 사람 코드들을 보니 규칙을 찾아 수식으로 해결한 경우가 많은 것 같다. 내 경우엔 그리디로 해결했다. x에서 y로 가면서 '최소값'을 구해야 한다. 이 경우, 최선의 선택은 x에서 1로 시작해 무조건 +1로만 진행하는 것이다. 점점 가속해야 가장 최선의 선택임이 자명하다. 하지만 문제는 y에서 도착할 때도 1이어야 한다. 그렇다면 최선의 선택은 다음과 같다. x에서 계속 +1씩 증가하면서 진행하고, y까지도 계속 -1씩 감소시키면서 감속시키는 것이다. 그럼 반대로 바꿔서 저 '?' 부분을 향해 x와 y에서 동일한 속도로 진행해서 만난다고 생각해보자. 그럼 x쪽에서1, y쪽에서1 -> x쪽에서2, y쪽에서2 -> x쪽에서3, y쪽에서3 이동.. 이런식으로 보면 되겠다. 이 때 .. 2021. 12. 8.

티스토리툴바