본문 바로가기

brute Force92

백준 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.
백준 12001 자바 - Load Balancing (Bronze) (BOJ 12001 JAVA) 문제 : boj12001 일단 B를 기준으로 모두 살펴보게 되면 O(1,000,000^2)이 되므로 시간초과가 나게 된다. N이 100개밖에 안되므로, N을 기준으로 살펴보면 된다. 처음엔 N개를 입력받고 fence가 교차하는 지점을 모든 N개 지점의 (x+1, y+1)에 있다고 보고 그로 인해 나눠지는 4사분면을 카운팅하면 될꺼라고 생각했다. 예를들어 cow가 주황색 지점에 있는 다음과 같은 상태를 생각해보자. 그럼 다음과 같이 모든 지점의 (x+1, y+1) 지점을 기준으로 나눠보면 답을 찾을 수 있을꺼라 생각했다. 하지만 제출해보니 틀렸고, 반례를 찾아보니 다음과 같은 경우 불가하다. 위의 경우 다음과 같이 나누어야 한다. 어찌되었든 기존 아이디어인 각 지점의 (x+1, y+1)은 분명 맞는 아이디.. 2021. 12. 2.
LeetCode 5 - Longest Palindromic Substring - Medium (Java) LeetCode도 자주 들어봤는데 한번도 해본적은 없어서 한번 풀어봤다. 일단 시간 제한이 안써있으면서 TLE(시간초과)는 뜨는게 상당히 거슬린다. 시간제한 알려주든가! 프로그래머스도 그게 좀 불만인경우가 많은데.. 그리고 남의 코드를 못본다는 점이 상당히 아쉬워서 메인 OJ(Online Judge)로는 별론 것 같다. 그래도 유명한 사이트니 간간히 생각날 때 하나씩 풀어보게 될 것 같다. 처음 해보는 사이트라 여기저기 눌러보다보니 DP 태그가 붙어있는걸 봤다. 이미 태그를 봐버린 이상 태그대로 푸는건 자존심 상하기도 하고 어차피 Brute Force(이하 BF)로도 가능할 것 같아서 BF(하지만 Back Tracking을 좀 끼얹은)로 풀어봤다. 1. 단순히 모든 경우를 보도록 짜게되면 다음과 같이 짜.. 2021. 11. 30.
백준 1515 자바 - 수 이어 쓰기 (BOJ 1515 JAVA) 문제 : boj 1515 입력으로 주어지는 수는 최대 3000자리이고, 0~9까지는 10개이다. 그러므로 대충 생각해봐도 아무리 최악의 케이스라 할지라도 3000 * 10 = 30000 이내에서 모두 찾아질 것임을 알 수 있다. 그러므로 brute force로 입력받은 값을 첫 자리부터 확인하며 1부터 30000까지 입력으로 받은 값에 대입해보며 하나씩 찾아나가면 된다. 예를들어 290119을 보자. 첫 자리수부터 확인한다. 여기서 base라는걸 1로 두고, base를 1씩 증가시키며 쭉 매칭시키자. 우선 'base=1'은 현재 pointer가 보고있는 2와 겹치는게 없으니 다음으로 넘어간다. 'base=2'는 pointer와 동일하므로 찾은거다. pointer를 전진한다. 그리고 base가 현재 1자리.. 2021. 11. 28.
CodeForces 1569A - Balanced Substring (Java) 문제 : https://codeforces.com/contest/1569/problem/A 1. 입력을 받은 값에 대해 a와 b가 나온 횟수를 prefix sum으로 계산해둔다. -> 범위 내의 a와 b의 개수를 빠르게 구하기 위해 2. 그 후 모든 substring에 대해 누적합 배열에서 범위합이 동일한 경우가 있는지 확인한다. 코드 : github import java.io.DataInputStream; import java.io.IOException; public class Main { public static void main(String[] args) throws Exception { initFI(); int tc = nextInt(); StringBuilder sb = new StringBui.. 2021. 11. 27.
백준 5966 자바 - Cow Cotillion (BOJ 5966 JAVA) 문제 : https://www.acmicpc.net/problem/5966 '>'와 ''를 넣고, ''와 ''와 '') cnt1++; else cnt2++; if (cnt2>cnt1) return false; } if (cnt1!=cnt2) return false; return true; } private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while (n-->0) { StringTokenizer st =.. 2021. 11. 23.
백준 21187 자바 - Pulling Their Weight (BOJ 21187 JAVA) 문제 : https://www.acmicpc.net/problem/21187 뭔가 복잡해보이는데, 좀 정리해보면 그냥 brute force로 해결 가능한 문제이다. 1 최대 10^5개의 동물의 무게가 주어진다. 그리고 각 무게는 2만 이하이므로, 전부 더해도 20억 이하로 Integer로 표현 가능한 수치이다. 2 사실 동물이 몇마리가 주어지든 상관없고 중요한 데이터는 결국 '1~20,000 사이의 각 무게를 가진 동물이 각 몇마리씩 존재하는지' 이다. 3 정렬이 필요할것같이 생겼지만, 사실 무게가 2만 이하라서 배열에 카운팅한다면 정렬은 따로 필요 없다. 다음의 입력을 보자. 6 5 7 5 5 3 4 위 입력을 배열로 카운팅해보면 다음과 같다. 4 그럼 이제 index 기준으로 1부터 20000까지를 .. 2021. 11. 22.
백준 3273 자바 - 두 수의 합 (BOJ 3273 JAVA) 문제 : https://www.acmicpc.net/problem/3273 보통 풀고보면 풀이 방법이 비슷비슷한 경우가 많은데, 아무래도 입력값 n이 10만개 밖에 안되다보니 재밌게도 풀이방법이 매우 다양한 문제이다. 일단, 단순히 2중 반복문으로 모든 쌍을 더해보면 O(N^2)이므로 시간초과다. 그럼 그 외에 시간 내에 가능한 풀이법에 대해 보자. 일반적으로 사람들이 많이 사용한 풀이 방법은 2가지 정도 있었다. 1. 정렬 후, 모든 값을 확인하며 x-a_i가 존재하는지 이분탐색으로 확인 : 정렬 O(NlogN) + N개에 대한 이분탐색 O(NlogN) 2. 정렬 후, 투 포인터 알고리즘으로 맨앞과 맨뒤에서 시작한 포인터를 움직이며 더해봄 : 정렬 O(NlogN) + 탐색 O(N) --- 내 경우엔 b.. 2021. 11. 13.
백준 9421 자바 - 소수상근수 (BOJ 9421 JAVA) 문제 : https://www.acmicpc.net/problem/9421 일단 이 문제를 풀기 위해 필요한 부분을 살펴보자. 1. 1000000이하의 모든 소수를 알 수 있어야 한다. -> 소수판정의 경우 간단히 에라토스테네스의 체를 사용해서 100만 이하의 모든 수에 대해 미리 소수를 구해두면 된다. 2. 상근수를 구할 수 있어야 한다. 이 때 '1'이 아예 안나오는 경우가 존재하므로 무한루프로 빠지지 않도록 하는 로직이 필요하다. -> 1이 나오거나, 이미 나왔던 수가 다시 나올 때 까지(순환) '각 자리수의 제곱의 합'을 구해준다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/09400/BOJ_9421.java import.. 2021. 11. 13.
백준 2811 자바 - 상범이의 우울 (BOJ 2811 JAVA) 문제 : https://www.acmicpc.net/problem/2811 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02800/BOJ_2811.java 정리하자면 결국 다음과 같다. 1. 연속된 음수 날의 개수(우울 기간)를 센다. 2. 해당 우울 기간 * 2 배 이전부터 꽃을 준다. 3. 그 중 가장 우울 기간이 긴 날들을 살펴보면서, 3배 이전부터 선물을 줬을 때 가장 많은 꽃을 사줘야 하는 경우를 고르면 된다. 그럼 내가 푼 로직은 다음과 같다. 1. 배열로 값들을 입력받는다. 2. 연속된 음수값에 대해 해당 음수값이 시작한 위치에 '우울 기간(T)'을 기입한다. 다음의 경우를 보자. 15 -4 2 5 -1 -3 4 -5.. 2021. 11. 12.

티스토리툴바