본문 바로가기

구현181

백준 4659 자바 - 비밀번호 발음하기 (boj 4659 java) 문제 : boj4659 풀이가 딱히 필요없다. 주어진 대로 구현할 수 있는 구현력(?)만 있으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private int type(char c) { switch (c) { case'a': case'e': case'i': case'o': case'u' : return 1; default: return -1; } } private boolean checkIt(String s) { for (int i = 0; i < s.length(); i++) { if (type(s.charAt(i)) == 1) break; if (i == s.le.. 2022. 4. 8.
백준 18868 자바 - 멀티버스 Ⅰ(boj 18868 java) 문제 : boj18868 주어진 대로 구현하면 되긴 한다. 내 경우엔 입력받은 값을 전처리해서 좀 더 쉽게 만들었다. 각 우주에 있는 모든 행성의 모든 쌍에 대해 순서대로 규칙을 만들어 하나의 String으로 만들었다. 예를들어 어떤 우주에 4개의 행성이 있었다면 1-2, 1-3, 1-4, 2-3, 2-4, 3- 4 순서대로 모든 쌍을 비교한다. 그래서 "+-+=++"와 같은 형태의 해당 우주의 모든 행성의 크기 규칙에 대한 String을 만드는 것이다. 그럼 최종적으로 M개의 String에 대해 모든 쌍을 확인 했을 때 동일한 String을 가진 행성이 몇 쌍 존재하는지만 확인하면 되는 문제로 변경된다. 즉 모든 쌍에 대한 단순 비교 로직 2개만 있으면 풀 수 있으므로 구현의 복잡도가 많이 줄어든다. .. 2022. 4. 2.
백준 3029 자바 - 경고 (boj 3029 java) 문제 : boj3029 H시간은 H*60*60초 이다. M분은 M*60초이다. S초는 S초이다. 따라서 입력으로 주어진 hh:mm:ss 두 개는 간단히 둘 다 00:00:00부터 몇 초 후인지로 변경할 수 있다. 예를들어 다음의 예시를 보자. (예제 입력 2에서 위아래를 바꾼 예시이다.) 14:36:22 12:34:56 이 때 현재 시간인 14:36:22는 52582초, 나트륨을 던질 시간인 12:34:56은 45296초가 된다. 전자를 st, 후자를 ed라고 해보겠다. 이 때 ed-st를 한다면 기다리는 시간을 알 수 있을 것이다. ed-st = -7286이 된다. 그 말인 즉, 나트륨을 던질 시간은 하루 뒤였다는 얘기이니 (현재 시간의 다음날 12:34:56) 24시간을 더해주면 된다. 즉, ed가 .. 2022. 4. 2.
백준 24927 자바 - Is It Even? (boj 24927 java) 문제 : boj24927 ※ 2K로 나누어 떨어지는지 구하면 안되고, 2^K(2의 K승)로 나누어 떨어지는지 구해야 한다. 문제에 오류가 있다. 이걸 직접 계산해서 실제로 나누어 보려고 한다면 무려 90만1자리의 엄청난 수가 나온다 ㅋㅋ. 그러니 생각을 좀 바꿔보자. 어차피 2^K으로 나누어 떨어지는지만 확인하면 되므로, 단순히 2^K 성분만 확인하면 된다. 다른 소수는 생각할 것도 없다! 무슨말이냐면, 소인수 분해를 생각해보자. 위와 같이 어떠한 수를 소인수분해 했을 때 2가 몇개 있는지만 알면 된다. 240의 경우 2가 4개 존재한다. 3이랑 5는 상관이 없다. 2가 4개인 수를 나눌 수 있는 2^K는 K개 4이하일 때 가능하다. 즉, 주어진 x_i을 2로 나누어지지 않을 때 까지 계속 나누면서 2로.. 2022. 3. 30.
백준 2713 자바 - 규현이의 사랑을 담은 문자메시지 (boj 2713 java) 문제 : boj2713 실버치고 구현이 상당히 빡쌘 문제이다. 아마 곧 골드까지 올라갈 것 같다. 이정도면 아무리 별다른 알고리즘 필요없는 구현문제라도 골드5정도가 맞다. 내 경우엔 최대한 원툴(?)로 구현을 하고 싶었다. 따라서 약간의 아이디어를 써서 좀 쉽게 진행했다. 다음의 입력을 확인해보자. 1 4 4 ACM 4x4일 경우, 그보다 2칸씩 크게 미리 배열을 만든다. 즉 6x6으로 만들고, 외곽을 1칸씩 띄운 상태로 중앙의 4x4에 '-1'과 같이 나올 수 없는 수를 쓴다. 해당 위치에 들어가야하는데 아직 값이 안들어갔다는 의미로 사용했다. 그리고 (1,0) 지점에서 시작하고, 처음 진행하는 방향은 항상 우측방향이다. 그리고 방향은 우측:0, 아래:1, 좌측:2, 위:3 으로 정한다. 소용돌이가 진.. 2022. 3. 29.
백준 5698 자바 - Tautogram (boj 5698 java) 문제 : boj5698 원랜 브론즈는 해설을 작성하지 않으려 했으나, 블로그 유입인원 늘릴려면 아무래도 골플 문제보단 브론즈 문제가 더 이득인 것 같다. 문자열을 잘라내는 방법만 안다면 풀 수 있다. 자바의 경우 String에 대한 split함수 또는 StringTokenizer를 사용해서 자를 수 있는데, 결론적으로 후자가 더 빠르다. 이제 자를수만 있다면, 모든 잘라진 토큰에 대해 첫 character만 확인하면 된다. String에 대해 charAt(0)을 하면 첫 번째 character가 나온다. 이 때 소문자 혹은 대문자로 맞춰서 확인하는 것이 좋을 것이다. 그럼 해당 String에 대해 toLowerCase 후에 charAt(0) 으로 보면 바로 소문자가 나온다. 하지만 당연히 더 느리다. 따.. 2022. 3. 28.
백준 14381 자바 - 숫자세는 양 (Small) (boj 14381 java) 문제 : boj14381 0부터 9까지의 모든 숫자를 체크하는건 HashSet을 사용하거나(size()가 10이 된다면 모두 찾은 것), 10칸짜리 배열을 사용하면 할 수 있다. 이제 시뮬레이션을 만들면 된다. 어떤 시뮬레이션이냐면, N을 입력받은 후 1N, 2N, 3N, ... 하고 적당히 100N 까지 각 숫자를 만들면서 각 자리수를 HashSet이나 배열에 담는다. 중간에 10개의 숫자가 모두 나왔다면 중지하고, 그렇지 않다면 적당히 큰 수 까지 직접 가보면 된다. 예를들어 다음과 같다. N이 11이었다면 다음과 같은 숫자가 체크될 것이다. 1N = 11 -> 1 2N = 22 -> 2 ... 9N = 99 -> 9 10N = 110 -> 0 최종적으로 10N일 때 10개의 수를 모두 찾았고, 11.. 2022. 3. 27.
백준 16955 자바 - 오목, 이길 수 있을까? (boj 16955 java) 문제 : boj16955 '.'인 곳 중 한 곳을 'X'로 바꾸었을 때, 'X'가 가로, 세로 혹은 대각선으로 연속으로 5개 이상인지 체크해보면 된다. 10x10의 입력값에서 '.'인 곳 모두를 한번씩 'X'로 바꿔보면서 위의 사항을 체크해보면 된다! 대략 O(10x10x5x4) 정도 될 것으로, 매우 널널하다(10x10은 오목판의 크기, 4는 가로 확인, 세로 확인, '↗'형태의 대각선, '↘' 형태의 대각선이다. 5는 대강 5 이상 됬으면 답일테니 5 미만으로만 갈테니 5이다 ㅋㅋ) 이 때 매번 전체 오목판을 모두 확인하면서 5개가 연속인지 확인하면 비효율적이다. 그러니 현재 '.'을 'X'로 변경한 위치부터 다음과 같이 가로, 세로, 대각선을 각각 확인하면 된다. 위의 경우 가로로는 4개, 세로로는.. 2022. 3. 26.
백준 9242 자바 - 폭탄 해체 (BOJ 9242 JAVA) 문제 : boj9242 입력받은 문자열을 숫자로 변경만 할 수 있다면 6의 배수인지는 n%6==0 과 같이 쉽게 알 수 있다. 또한 코드는 8자리 이하라고 했으므로 최대 10^8-1의 값이므로 정수로 표현하는데에도 문제가 없다. 따라서 주어진 문자가 잘못된 문자인지 여부를 알 수 있고, 주어진 문자가 숫자로 무엇과 대응되는지만 알면 풀 수 있다. 그럼 주어진 문자를 주어진 기준문자(아래와 같은)와 비교만 잘 하면 된다. 이 때 주의점은 각 문자의 특징을 잡아서, 예를들어 마지막 열에 5개의 별표가 있다면 1 혹은 7일테니 첫번째 열에 *이 있다면 7, 아니면 1 이런방식은 틀린 입력값을 제대로 잡아낼 수 없다. 따라서 문자의 모든 위치(5x3)을 모두 비교하는게 맞다. 내 경우엔 우선 기준 데이터를 파싱.. 2022. 3. 21.
백준 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.

티스토리툴바