본문 바로가기

PS/BOJ764

백준 11008 자바 - 복붙의 달인 (boj 11008 java) 문제 : boj11008 문제가 명확하지 않아 별로인 문제였다. 예를들어 p가 'bana'이고, s가 'babanana' 일 경우, 이 문제는 'babanana' 중간의 bana 하나만 복붙하고, 나머지 4개는 별도로 출력하여 5가 답이다. 하지만 bana를 복붙 후, 중간에서 bana를 또 붙여넣기하면 2번인걸! 이런 부분에 대한 조건이 제시되어 있지 않았고 그냥 대충 이런거 처리 안하는걸로 제출하니 통과됐다. 좀 아쉽다. 아무튼 그냥 s에서 p가 나온 부분을 세주고, 나머지 부분을 세면 된다. 좀 간단하게 처리하려면 이하 코드처럼 s에서 p를 replaceAll로 전부 문제에 제시될 수 없는 character로 변경해 준 뒤 s의 길이를 출력해주면 된다. 코드 : github import java.i.. 2022. 4. 21.
백준 15738 자바 - 뒤집기 (boj 15738 java) 문제 : boj15738 풀이 첫 줄에 강력한 스포가 있다. 혹시 아직 못 풀어서 이걸 어떻게 풀지? 생각되어 풀이를 봤다면, 이하 풀이를 보면 많이 짜증날 수 있으니 다시 한번 문제를 잘 읽어보고 직접 도전해보는걸 추천한다. ------- 풀이 : 애초에 배열 A가 아무런 의미가 없다 ㅋㅋㅋ 그냥 입력받은 n과 k만 가지고 각 m개의 연산에 따라 사칙연산으로 k의 위치만 바꿔주면 된다. A. i가 양수일 때 i 그리고 i-k+1로 k를 변경해주면 된다. B. i가 음수일 때 n+i+1 까지 영향을 끼치므로, 그보다 k가 작다면 무시하면 된다. -> 그리고 2*n-k+i+1로 k를 변경해주면 된다! 따라서 시간복잡도는 O(M)이다. N은 아무런 영향을 끼치지 않는다. 이.. 2022. 4. 20.
백준 1940 자바 - 주몽 (boj 1940 java) 문제 : boj1940 고유한 번호를 a라고 할 때, 결국 알아야 하는 것은 n개의 a에 대해 현재 보고 있는 a값을 기준으로 m-a가 n개 중에 존재하는지만 알 수 있으면 된다. 따라서 HashSet을 사용하면 쉽게 풀 수 있다. 이 때, 만약 '고유한 번호'가 아니라 중복되는 것이었다면 HashMap으로 개수도 체크해야 했을 것이다. 로직은 그럼 다음과 같다. A. N개를 입력받으면서 HashSet에 넣는다. B. N개를 순회하면서 m-a가 HashSet에 존재하는지 확인한다. 존재한다면 카운트를 +1 시킨다. C. 이 때 m이 짝수이고 m/2인 값이 존재한다면 m-a == a 이므로 이 경우는 빼야하니 카운트 -1 시킨다. D. 최종적으로 중복된 경우를 빼기 위해 카운트/2를 해서 출력해주면 된다... 2022. 4. 19.
백준 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.
백준 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.

티스토리툴바