본문 바로가기

전체 글1068

[ABC250] C - Adjacent Swaps (AtCoder Beginner Contest 250 with Java) 문제 : abc250_c 일단 단순히 swap만 하는 거였다면 별 문제가 없었을 것이다. 문제는 매번 swap해서 바뀌는 각 숫자의 위치를 유효한 시간 내에 찾아내야 한다는 점이다. 만약 매번 전체 배열을 순회하며 찾으려 한다면 O(N+QN)만큼(처음 N은 배열 입력받는 부분, QN은 각 쿼리마다 최대 N번 확인해야 하므로) 필요할 것이므로 시간내에 통과할 수 없다. 따라서 배열을 2개 써서 다음과 같이 한번 생각해보자. N이 5인 경우이다. 원래는 위의 저 '값 배열'만 가지고 해야했는데, '위치 기록용 배열'을 추가로 만들었다. B[z]는 값 z의 현재 idx를 나타낸다. 즉, A[B[z]] == z 이다. 이렇게 메모리를 더 써서 배열 하나를 더 두면 swap 시에 다음과 같이 해볼 수 있다. 현재.. 2022. 5. 9.
[ABC250] B - Enlarged Checker Board (AtCoder Beginner Contest 250 with Java) 문제 : abc250_b 패턴을 잘 살펴보면 결국 NxA행, NxB열의 문자열을 출력하면 된다. 그리고, 시작하는 문자가 '.'으로 시작하는게 A줄, 그 다음 '#'으로 시작하는게 A줄... 을 N줄동안 수행하면 된다. 단순 구현문제긴 한데 반복문에 익숙치 않다면 좀 어려울 수 있다. 4중 for문에서 처음 2중은 N과 A, 그 다음 2중은 N과 B라고 생각하면, 코드로는 4중 for문이지만 개념적으로는 2중 for문이 된다. 그럼 좀 더 쉽게 구해볼 수 있다. boolean값을 잘 설정해서 한번 구현해보자. 참고로 이하 코드에서 'i&1==0'은 i가 짝수라면 true, 홀수라면 false 이다(왜 그런지는 짝수와 홀수를 아무 숫자나 2진수로 바꿔보면 알 수 있다.). 'isWhite^swt'에서 '^.. 2022. 5. 9.
[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.
[자바] 백준 2480 - 주사위 세개 (boj java) 문제 : boj2480 셋 다 같은 눈인지, 셋 중 둘이 같은 눈인지, 모두 다른 눈인지 확인만 할 수 있다면 풀 수 있다. if문을 사용해 짜보자! 코드 : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffe.. 2022. 5. 9.
[자바] 백준 12981 - 공 포장하기 (boj java) 문제 : boj12981 당연히 3개씩 넣는게 가장 좋으며, 그게 안된다면 2개씩, 그것도 안된다면 1개씩이라도 넣으면 된다. 이건 당연한건데 문제는 박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다는 제약때문에 순서를 잘 정해야 한다. 내 경우 이하의 로직으로 풀었다. 1. 우선 가능한 만큼 모두 다른색으로 3개를 박스에 넣는다. (따라서 정렬 후, 가장 낮은 값을 나머지 2개에서 빼줬다.) 2. 이제 3개씩 넣을 수 있는 방법은 모두 같은 색으로 3개를 넣는 방법 뿐이다. 따라서 남은 2개의 색상은 각각 3개씩 가능한 만큼 넣어준다. 3. '2'에서 남은 공운 1개 아니면 2개일 것이다(3개씩 넣었으므로). 이 때 가능한 경우는 다음과 같다. 3.1 둘다 남은게 0개인 경우 -> 모두 3개.. 2022. 5. 8.
[자바] 백준 19939 - 박 터뜨리기 (boj java) 문제 : boj19939 우선 K개의 바구니에 N개의 공을 나눠 담을 수 있는지 여부부터 확인해보자. 이건 쉽게 1+2+...+k 가 n보다 큰지 확인하면 된다. 등차수열의 합 공식을 사용하면 합을 쉽게 구할 수 있다. 등차수열 합 공식은 다음과 같다(n이 수의 개수, a가 첫 항의 값, l이 n번째 항의 값) 그리고 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 차이가 최소가 되려면 어떻게 해야할지 생각해봐야 한다. 이 경우 직관적으로 k개를 1씩 차이를 내는게 최선임을 알 수 있다. 즉, 1. 1+2+...+K 2. 2+3+...+(K+1) 3. 3+4+...+(K+2) ... 과 같이 증가시키면서 N보다 커지는 순간을 찾으면 최소값을 어디서 구해봐야할지 알 수 있다. (합은 위의 등차수열 .. 2022. 5. 7.
[자바] 백준 22155 - Простая задача (boj java) 문제 : boj22155 구글 번역기를 쓸 수 있다면 풀 수 있다(?). 각 테스트케이스마다 a, b를 입력받는다고 할 때 a가2보다 작고 b가 1보다 작거나, b가 2보다 작고 a가 1보다 작으면 된다. 코드 : 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 InputStreamReader(System.in)); int n = Integer.parseInt(br.readLin.. 2022. 5. 6.
[자바] 백준 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.
[자바] 프로그래머스 - 프린터 (programmers java) 문제 : programmers-프린터 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 문제에서 제시된 대로 시뮬레이션을 돌려주면 된다. 이 때 서브 문제로 문제를 나눠서 생각해보자. 1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다. 2. 현재 꺼내지 않은 대기목록에서 중요도가 가장 높은 값을 알 수 있어야 한다. 3. location으로 지정된 문서의 위치를 항상 알 수 있어야 한다. 위의 3가지를 모두 할 수 있다면 이 문제를 풀 수 있다. 그럼 각각 어떻게 해야할지 생각해보자. 1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다. 사실 이걸 만족하는 자료구조는 엄청.. 2022. 5. 4.

티스토리툴바