본문 바로가기

구현182

백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA) 문제 : boj17162 mod가 최대 10^2라서 뭐 복잡한 알고리즘 필요없이 풀 수 있다. 결국 나누었을 때 0, ..., mod-1인 수가 어느 idx 위치에 있냐가 중요하다. 이걸 빨리 알 수 있으면 되는건데, mod가 10^2이니깐 대충 O(Q * mod) 정도의 시간복잡도만 가져도 풀 수 있다. 그럼 해볼만한게 많이 있다. 내 경우엔 어차피 맨 뒤에서만 수가 추가되고 빠지니 스택을 사용했다. 그리고 mod개 만큼의 스택을 마련했다. 스택배열을 arr이라고 하고, 현재 넣을 위치를 idx라고 하겠다. 그럼 각 쿼리에 대해 다음과 같이 대응할 수 있다. --- [ 쿼리 : 1 num ] arr[num % mod]에 num을 추가하고 idx++ -> O(1) [ 쿼리 : 2 ] 최대 10^2개인 a.. 2022. 3. 18.
백준 11637 자바 - 인기 투표 (BOJ 11637 JAVA) 문제 : boj11637 우선 직관적으로 생각하기엔 아주 간단하다. 각 테스트 케이스에 대해 n명의 득표 수 합계(이하 sum)를 구하고, 그 n명 중 가장 큰 값(이하 max)을 기준으로 다음과 같이 나뉜다. 1. max값을 가졌던 인원이 2명 이상인 경우 : no winner 2. sum/2+1 0) { int n = nextInt(); int max = 0; int maxIdx = -1; int sum = 0; int idx = 0; boolean chk = true; while (idx++ 2022. 3. 17.
백준 6550 자바 - 부분 문자열 (BOJ 6550 JAVA) 문제 : boj6550 s쪽에 포인터를 하나 두고, t쪽에도 포인터를 하나 둔다. 이후 s쪽 포인터를 하나씩 증가시키면서, 해당 포인터가 가르키는 문자가 나올 때 까지 t 포인터를 증가시키면서 찾는다. 최종적으로 t포인터가 t를 전부 찾기 전까지 s쪽 포인터가 끝까지 도달한다면 Yes가 된다. 이하 '예제 입력 1'의 3번째 테스트 케이스를 찾는 과정을 그려봤다. s쪽 포인터가 si, t쪽 포인터가 ti 이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exce.. 2022. 3. 13.
백준 14719 자바 - 빗물 (BOJ 14719 JAVA) 문제 : boj14719 '문제'에 나온 이미지를 다시 그려봤다. 이 때 물이 차는 높이를 어떻게 알 수 있을까? 우선 3D로 생각해서 좌측에서 블록들을 본다고 생각해보자. 이 때 물은 좌측에서 시선에 닿는 만큼 차오를 수 있다. 즉 좌측에서 봤을 때 눈에 보이는 부분들에 들어찰 것이다. 좌측에서만 보면 아래와 같이 생각할 수 있다. 이 때 우측은 당연히 저렇게 들어차면 안된다. 따라서 우측에서도 확인해야 한다. 이번엔 우측에서 한번 봐본다고 생각해보자. 그럼 이렇게 생각될 수 있다. 그럼 이제 좌측에서 본 것과, 우측에서 본 것을 합쳐서 각 블록마다 좌측에서 봤을때와 우측에서 봤을 때 보였던 높이 중 작은 쪽을 선택하면 아래와 같이 된다. 좀 더 구체적으로 정의하자면 다음과 같다. 좌측부터 w방향으로 .. 2022. 3. 10.
백준 2312 자바 - 수 복원하기 (BOJ 2312 JAVA) 문제 : boj2312 오랜만에 1분컷으로 푼 것 같다. 소인수분해의 결과는 결국 전부 소수가 될테니 미리 에라토스테네스의 체로 소수를 구해두고 수행하면 더 효율적이긴 하다. 하지만 N이 최대 100000이므로 2부터 N까지의 모든 수로 직접 나눠봐도 O(100000)밖에 안나온다. 따라서 그냥 brute force로 직접 나눠보면 쉽게 답을 구할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamRe.. 2022. 3. 3.
백준 3711 자바 - 학번 (BOJ 3711 JAVA) 문제 : boj3711 g가 최대 300밖에 안되므로 모든 경우를 살펴봐도 O(G^2) 수준이라 브루트포스로 진행해도 무리없이 풀 수 있다. 즉, 1부터 시작해서 수를 점차 키워가면서 모든 값들을 실제로 나눠보고 그 나머지를 체크하면 된다. 이 때 주의점은 중복 체크라고 하면 일반적으로 해시셋을 쉽게 떠올릴텐데, 자바 한정으로 이 문제에서는 해시셋 사용 시 메모리 초과가 날 수 있다. 따라서 배열을 이용해 체크해주면 쉽게 통과할 수 있다. 내 경우엔 각 TC마다 체크용 배열을 초기화하고, 현재 나눠볼 값을 K라 할 때 메모리를 최대한 아끼기 위해 K에 따라서는 매번 초기화하지 않고 해당 K값을 기입했다. 코드 : github import java.io.BufferedReader; import java.i.. 2022. 3. 2.
백준 2729 자바 - 이진수 덧셈 (BOJ 2729 JAVA) 문제 : boj2729 문제에 제시된대로 실제로 덧셈을 진행해주면 된다! 즉 문제에 나온대로 구현하면 풀 수 있다. 주의점은 입력은 0으로 시작할 수 있는데, 출력은 앞에 0이 붙으면 안된다는 점이다. 즉, '000001 00010' 이런 입력이 들어올 수 있고, 답은 '11' 로 앞의 0들을 출력하면 안된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = n.. 2022. 2. 28.
백준 2947 자바 - 나무 조각 (BOJ 2947 JAVA) 문제 : boj2947 문제에 나온대로 구현만 하면 되는 문제이다. 혹시 구현이 힘들다면 논리적으로 생각하며 어떻게 짜야 주어진 동작이 수행 가능할지 공책에 그려보거나 하면서 구현해 보자. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] arr = new in.. 2022. 2. 27.
백준 11468 자바 - Concatenation (BOJ 11468 JAVA) 문제 : boj11468 1. 우선 모든 경우의 수를 생각해보자. 예제 입력 1의 cat과 dog를 봐보자. 나올 수 있는 모든 경우는 다음과 같다. (cg, cog, cdog, cag, caog, cadog, catg, catog, catdog의 9가지) 이와같이 A와 B가 입력으로 들어온다면, 모든 경우의 수는 [A의 문자 수 x B의 문자 수] 임을 알 수 있다. 2. 그럼 언제 중복된 경우가 발생할까? bbb와 bzz를 확인해보자. 이와 같이 동일한 문자가 존재하는 경우 중복값이 발생한다. 다만 이 때, A 단어의 맨 앞 문자는 무조건 들어가야 하고(non-empty prefix), B 문자의 맨 뒤 글자도 무조건 들어가야 하므로(non-empty suffix) A 문자의 맨 첫문자와, B 문자의.. 2022. 2. 21.
백준 18917 자바 - 수열과 쿼리 38 (BOJ 18917 JAVA) 문제 : boj18917 제거 연산이 '항상 A에 x가 있는 쿼리만 주어진다' 라는 조건이 있으므로 상당히 간단해지는 문제이다. 애초에 뭐 가장 앞에 있는걸 제거한다는 부분도 딱히 의미가 없다. 아무튼 있는 값에 대해서만 제거가 되므로 편하게 할 수 있다. 1. 모든 원소를 더한 값 sum과 같이 변수를 하나 두고 1 x 형태의 연산이 들어올 때 더해두고, 2 x 형태의 연산이 들어올 때 빼두면 된다. 2. 모든 원소를 XOR한 값 이게 좀 어려울 수 있다. 일단 1 x 형태의 연산은 그냥 XOR을 하면 된다. ('^' 연산)2 x 형태가 문제인데, 사실 이것도 그냥 XOR을 하면 된다. 왜냐면 어떠한 수 n에 대해 n^n = 0 이다. 즉 자기 자신을 빼내는 것 역시 XOR로 동일한 수를 진행하면 되는.. 2022. 2. 20.

티스토리툴바