본문 바로가기

백준756

백준 17359 자바 - 전구 길만 걷자 (boj 17359 java) 문제 : boj17359 우선 브루트포스로 모든 경우를 본다면 10! 번을 봐야 한다. 사실 이건 360만번 정도로 충분히 가능한 횟수이다. 문제는 모든 경우를 이어본 후, 한땀한땀 바뀌는 부분을 구하려면 문자열의 길이가 최대 100 이므로 O(10!*100)이 필요하게 된다. 따라서 시간초과(사실 3억번정도에 중간에 추가 연산(세세한 덧셈 뺄셈 같은 것들)이 거의 없어 C나 C++이면 통과될것같긴하다 ㅋㅋ)가 날 것이다. 그럼 시간을 뺄 수 있는 아이디어를 생각해보자. 1. 각 묶음 내에서 바뀌는건 고정이다. 즉, 어떻게 배치하게 되던지, 각 묶음 내에서 바뀌는건 어쨌든 고정적으로 바껴야 한다. 따라서 입력을 받으면서 내부에서 바뀌는걸 미리 세두자. 내 경우엔 confirmedCnt가 해당 역할을 한다.. 2022. 4. 17.
백준 15492 자바 - 뒤집기 (boj 15492 java) 문제 : boj15492 바로 직전에 풀었던 19585번 '전설'의 경우 시도횟수가 18번이었는데, 이번엔 29번이었다 ㅂㄷㅂㄷ... 이번에 포기안하고 계속 시도해본 이유는, 테스트케이스 랜덤 생성기로 400만개를 돌려보니 괜찮은 시간이 나왔기 때문이었다. 결론적으로는 '1 2 3 1 2 3 1 2 3 ...'와 같은 케이스를 제대로 못잡아 내서 시도횟수가 많아졌다(랜덤 생성기라 그런 케이스가 안나오니까) 풀고 보니 다른 분들은 해싱과 KMP 등으로 풀었다는데, KMP까진 적용이 이해가 됬는데 해싱으로 푼다니 생소하다. 해싱은 'Lexicographically Minimal Cyclic Shift' 라는걸 쓰면 된다고 한다. 처음들어본다. 내 경우엔 실력이 부족하니 몸으로 때워서 해결했다. 시뮬레이션으로.. 2022. 4. 16.
백준 19585 자바 - 전설 (boj 19585 java) 문제 : boj19585 다른 의미로 전설이었다. 보통은 포기하고 넘어갔을텐데 이론상(?) 가능할 것 같아서 계속 하다보니 오기가 생겨서 끝까지 해보기로 했었다 ㅋㅋㅋ 풀고보니 자바한정으로 통과하기 어려운 문제였다. 시간초과난 로직으로 다른 언어론 통과가 되더라 ㅠ 시도한 내용들은 이하와 같다. 1. 이왜플(이게 왜 플래)을 외치며 모든쌍을 HashSet에 넣었다가 당연히 시간초과(이하 TLE). -> 색상과 닉네임이 둘 다 최대 4000개씩 이므로 모든 쌍을 만들면 O(4000^2) 이라고 대충 생각해서 해봤었다. 하지만 String이란 점을 간과했다. String + String이 결국 두 문자열 길이의 합 만큼 시간복잡도가 들어가므로, 실제론 O(4000^2 * (1000+1000)) 이다. Str.. 2022. 4. 15.
백준 11444 자바 - 피보나치 수 6 (boj 11444 java) 문제 : boj11444 분할 정복을 이용한 거듭제곱 최적화(이 글)을 보면 풀 수 있다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final long MOD = 1_000_000_007l; private long[][] matrixMult(long[][] a, long[][] b) { long[][] arr = new long[2][2]; arr[0][0] = (a[0][0]*b[0][0]%MOD + a[0][1]*b[1][0]%MOD)%MOD; arr[1][0] = (a[0][0]*b[0][1]%MOD + a[0][1]*b[1][1]%MOD)%.. 2022. 4. 13.
백준 24510 자바 - 시간복잡도를 배운 도도 (boj 24510 java) 문제 : boj24510 자바의 replaceAll을 사용해 입력으로 들어온 문자열에 포함된 for와 while을 전부 특정 문자로 변경(이하 코드에서는 ','로 변경)한다. 이후 해당 문자의 개수를 세면 문자열에 포함된 for와 while의 개수를 셀 수 있다. 특정 문자로 변경한 이유는 "foforr"과 같은 경우 1번으로 체크되야 하지만, 그냥 for를 제거만 할 경우엔 foforr -> for 이 되어 2번 세질 수 있기 때문이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Excepti.. 2022. 4. 13.
백준 11004 자바 - K번째 수 (boj 11004 java) 문제 : boj11004 정렬만 할 줄 안다면 바로 풀 수 있는 날먹문제. 정렬 후 K-1 인덱스에 있는 값을 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(.. 2022. 4. 11.
백준 14584 자바 - 암호 해독 (boj 14584 java) 문제 : boj14584 26번에 걸쳐 각 문자를 하나씩 증가시켜보면서, 입력으로 들어온 N개의 문자가 있는지 판단해보면 된다. 예를들어 처음에 'abcd' 였다면, 하나씩 증가시킨단 말은 'abcd' -> 'bcde' -> 'cdef' -> ... 와 같은걸 의미한다. 'arr[j] = (char)('a'+((arr[j]-'a'+1)%26));' 부분이 해당 역할을 한다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new Inpu.. 2022. 4. 10.
백준 9612 자바 - Maximum Word Frequency (boj 9612 java) 문제 : boj9612 String에 대해 카운팅을 해야 한다. 따라서 HashMap 등을 사용하면 쉽게 계산할 수 있다. 주의점은 동일한 횟수가 존재할 경우, 사전순으로 뒤에 있는걸 택해야 한다. 코드에서 이하의 부분이 해당 역할을 한다. maxStr.compareTo(cur) < 0 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in).. 2022. 4. 9.
백준 10090 자바 - Counting Inversions (boj 10090 java) 문제 : boj10090 n개를 입력받으면서 매번 입력받은 값이 k라 하면, 매번 이전까지 나온 수 중 k보다 큰 수가 몇 번 나왔는지만 알면 된다. 머지소트트리, 세그먼트트리, 제곱근 분할법이 이걸 알 수 있는 자료구조들이다(물론 더 있을 수 있다). 별다른 응용없이 해당 자료구조 중 아무꺼나 적용하면 풀리는 문제라 셋 중 맘에 드는걸로 검색해서 배워보자! 개인적으로 구현 난이도는 제곱근 분할법 < 머지소트트리 2022. 4. 8.
백준 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.

티스토리툴바