brute Force92 [ABC250] A - Adjacent Squares (AtCoder Beginner Contest 250 with Java) 문제 : abc250_a (1, 1)부터 (H, W) 까지의 모든 square 쌍 (h, w) 대해 이하가 만족하는 경우를 카운팅하면 된다. 코드 : github ... private void solution() throws Exception { int h = nextInt(); int w = nextInt(); int r = nextInt(); int c = nextInt(); int cnt = 0; for (int i = 1; i 2022. 5. 9. [자바] 백준 8892 - 팰린드롬 (boj java) 문제 : boj8892 각 테스트케이스마다 k가 최대 100개이므로, 모든 쌍을 보더라도 O(T x 100^2)번에 가능하다. 또한 모든 단어의 길이의 합은 10,000이하라고 했으므로, 단어 길이의 합을 L이라 할 때 팰린드롬인지 확인하는 로직이 O(L)짜리 로직이라 하더라도 O(TL x 100^2)으로 가능하다. 또한 팰린드롬인 값이 하나라도 있다면 거기서 종료하면 되므로, 대강 모든 경우를 봐도 시간내에 통과 가능할 것임을 예상할 수 있다. 우선 문자열 S가 팰린드롬인지 확인하는 가장 간단한 방법은, |S/2|까지 인덱스를 증가하면서 앞과 뒤의 문자를 확인하는 것이다. isPalindrome() 함수를 확인해보면 알 수 있다. 그리고 모든 경우를 보는 것은 모든 문자쌍을 만들어보면 된다. 코드의 2.. 2022. 5. 9. [자바] 백준 24586 - Code Guessing (boj java) 문제 : boj24586 문제의 조건을 만족하는 경우를 직접 생각해보며 (신중히) 찾아보면 된다. 우선 입력으로 들어올 수 있는 문자열의 모든 경우를 살펴보면 아래와 같다. 그럼 각각의 경우에 A가 어떤 값이어야 'uniquely determine the two digits on Bob’s cards'라는 조건에 부합하는지 확인해보면 다음과 같다. 이유는 잘 생각해보면 알 수 있다! 저 경우에만 B를 확정적으로 예상할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static boolean ch.. 2022. 5. 5. [자바] 백준 1388 - 바닥 장식 (boj java) 문제 : boj1388 문제에 제시된대로 구현을 하면 된다. 좀 더 편하게 하려면 어차피 n, m이 수치가 매우 낮으므로 가로와 세로를 따로 세면 편하다. 가로로 세면서 '|' 을 만나면 세던걸 초기화 하는 식으로, 세로로 세면서 '-'을 만나면 세던걸 초기화 하는 식으로 진행하면 좀 더 로직을 세우기 편하다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2022. 5. 4. [자바] 백준 2246 - 콘도 선정 (boj java) 문제 : boj2246 각 N개에 대해 모든 N-1개의 다른 지점들을 전부 확인해봐도 O(N^2)으로 시간 제한인 2초 내에 가능하다. 따라서 모든 경우를 봐주면 된다. 문제에 제시된 조건을 if문으로 잘 표현만 할 수 있다면 어렵지 않게 풀 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { class Condo { int d, c; public Condo(int d, int c) { this.d = d; this.c = c; } } private void solution() throws Exception { B.. 2022. 5. 3. [자바] 백준 10469 - 사이 나쁜 여왕들 (boj java) 문제 : boj10469 '*'이 나온 모든 위치에서 상하좌우, 대각선으로 퀸이 없으면 valid, 있다면 invalid인 간단한 구현 문제이다. 매번 '*' 위치에서 판의 끝까지 위,아래,좌우,대각선으로 탐색하면서 '*'이 있는지 확인하면 풀 수 있다. 하지만 그냥 매번 '*'의 위치에서 brute force로 직접 탐색하며 확인하긴 심심하니 난 내 수준에서 생각할 수 있는 가장 간단하게(짧게) 찾는 방법을 사용해 풀어봤다. 설명은 코드에 주석으로 달아두었다. 그리고 맞왜틀 나기 아주 좋은 함정이 있다. '사이나쁜 여왕 퀴즈는 여덟 여왕을 8x8 체스판 위에 배치' 여덟 여왕이랬으므로 '*'의 개수가 8개가 아니면 invalid이다. 코드 : github import java.io.BufferedRea.. 2022. 4. 27. [자바] 백준 11170 - 0의 개수 (boj java) 문제 : boj11170 최악의 경우가 N=0, M=1,000,000 일 경우이다. 이 때 0부터 1000000까지 하나씩 전부 0의 개수를 확인하더라도 O(1000000*8) 이면 된다(8은 자리수의 최대치). 따라서 그냥 N부터 M까지 하나씩 증가시켜보면서, 10으로 나눠가면서 1의자리가 0인 경우를 직접 세주면 된다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new.. 2022. 4. 26. [자바] 백준 14721 - 성적표 문제 : boj14721 뭔가 무서워 보이는 공식이 있지만, 그냥 문제에서 제시된 대로 구현만 해보면 된다. a와 b가 100 이하이므로 a를 1~100, b를 1~100 범위 내에서 모든 쌍을 확인하면서 rss를 계산하면 된다. 즉, 입력으로 x와 y가 주어지니, 모든 a,b 쌍에 대해 (y-(a*x+b))^2의 합의 최소치를 찾으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new Buffere.. 2022. 4. 24. [자바] 프로그래머스 - 타겟 넘버 (코딩테스트 연습 Lv2) 문제 : Programmers-타겟넘버 결국 주어진 numbers를 순서대로 + 한번, - 한번씩 모든 경우를 구해보면 된다. 이 경우 O(2^n)이 된다(+,-의 2가지 경우를 n번 봐야 하므로). 예를들어 numbers가 [1, 2, 3]일 경우 다음과 같이 진행된다. 이 중 target과 동일한 경우를 세서 return해주면 된다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges */ class Solution { int cnt = 0; private void rec(int[] numbers, int target, int idx, int sum) { if (idx == numbers.length.. 2022. 4. 18. 백준 17550 자바 - Inquiry I (boj 17550 java) 문제 : boj17550 prefix sum (누적합)을 안다면 쉽게 풀 수 있다. 누적합 배열을 하나는 n개를 원래 값 대로, 하나는 n개를 제곱해서 합한 누적합 배열을 만든다. 전자를 a, 후자를 b라고 하겠다. 그럼 이후 특정 범위의 합을 O(1)로 알 수 있으므로, b[i] * (a[n]-a[i])에 대해 i를 1부터 n까지 진행하면서 가장 큰 값을 찾으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2022. 4. 18. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
