0과 1의 쉼터

[백준 15658] 연산자 끼워넣기 (2) [Java]

문제https://www.acmicpc.net/problem/15658 풀이배열 A에 대해 주어진 연산자를 활용해 만들어지는 모든 식의 결과 중 최대/최소값을 구하는 문제다.중간값과, 다음에 계산할 요소의 인덱스를 넘겨주는 방식으로 풀이했다.만약 인덱스가 A의 길이와 같다면 더 이상 연산할 요소가 없기 때문에 연산을 중단하고 결과를 갱신했다. private static void bt(int temp, int nextIdx) { if (nextIdx == A.length) { max = Math.max(max, temp); min = Math.min(min, temp); return; }아직 연산할 요소가 남아있는 경..

[백준 23827] 수열 (Easy) [Java]

문제https://www.acmicpc.net/problem/23827 풀이주어진 수열에 대해 1 ≤ i 수가 너무 커질 수 있으니 1e9 + 7로 나눈 나머지를 출력해야 한다.문제를 만족하는 정수쌍 곱의 합은 i와 i + 1 ~ j의 합의 곱과 같다.최대 길이가 50만인 수열에 대해 누적합을 미리 구해 // Solve final int MOD = (int) (1e9 + 7); long[] prefixSum = new long[N]; prefixSum[0] = A[0]; for (int i = 1; i 모든 i에 대한 A[i] * ( prefixSum[N] - prefixSum[i] )을 구하면 된다. long res = 0; ..

문제https://www.acmicpc.net/problem/30979 풀이F의 합이 T이상인지 확인하는 문제다.T이상일 때 파댕이가 울지않기 때문이다. final int fSum = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).sum(); // Solve & Output System.out.println(T 풀이 시간≤ 2m소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/30979.java problem-solving/baekjoon-online-judge/practice/309..

문제https://www.acmicpc.net/problem/32335 풀이주어진 문자열 S의 각 자릿수를 회전시켜 가장 작은 수를 만드는 문제다.총 M번 회전 시켜야 하며 수는 증가하는 방향으로 회전해야 한다.맨 앞자리부터 시작해서 0으로 만들 수 있을 만큼 M이 크다면 돌려주고, 아니면 다음 수로 넘어가면 된다. // Solve for (int i = 0; i '0') { final int num = S[i] - '0'; if (num + M >= 10) { S[i] = '0'; M -= (10 - num); } ..

문제https://www.acmicpc.net/problem/1639풀이주어진 문자열 S에 대해 2N자리의 부분 문자열의 각 자리를 더했을 때 왼쪽과 오른쪽 N자리의 합이 동일한 부분 문자열의 최대 길이를 구하는 문제다.우선 S의 길이에 따라 가능한 최대 크기를 정해주자.홀수면 1을 빼고, 짝수면 원래 크기 그대로 최대 크기가 될 수 있다. // Solve int GAP = nums.length % 2 == 0 ? nums.length : nums.length - 1;길이가 홀수인 정답은 없으므로 GAP이 0이 될 때 까지 2씩 감소시키며 문제의 조건을 만족시키는 부분 문자열을 찾으면 된다. while (GAP > 0) { for (int i = ..

문제https://www.acmicpc.net/problem/25594 풀이문자열 S가 사전에 주어진 매핑표의 문자열들로 구성되어있는지 확인하는 문제다.직관적인 매핑을 위해 Map으로 매핑 테이블을 만들었다.단순히 문자열 배열로 만든 후 아스키코드값을 인덱스처럼 활용하는 방법도 있다. // Solve Map map = new HashMap(); map.put('a', "aespa"); map.put('b', "baekjoon"); map.put('c', "cau"); map.put('d', "debug"); map.put('e', "edge"); map.put('f', "firefox"); m..

문제https://www.acmicpc.net/problem/1408 풀이두 시간대가 주어졌을 때 시간의 차를 계산하는 문제다.시작 시간과 종료 시간은 최대 48시간 차이가 날 수 있다. 이는 LocalTime.parse로 충분하다. // Input LocalTime start = LocalTime.parse(br.readLine()); LocalTime end = LocalTime.parse(br.readLine());시작 시간과 종료 시간의 차가 음수라면, 종료 시간은 시작 시간의 다음 날을 의미한다.24시간을 더한 후 올바른 차를 계산해서 출력하자. // Solve int totalSec = (int) Duration.between(st..

문제https://www.acmicpc.net/problem/14335 풀이문자열 S에 대해 순서를 고려한 서로 다른 부분 수열의 수를 구하는 문제다.문자열의 길이가 최대 1,000으로 모든 부분 수열들을 구하고 중복을 제거한다면 시간 초과가 발생한다.순서를 고려하므로 중복되는 문자에 대한 부분 수열을 제거해야 한다.dp[i] : i번까지 문자들로 만들어진 서로 다른 부분 수열의 수중복을 고려하지 않고 부분 수열의 수를 기록하자. long[] dp = new long[N + 1]; dp[0] = 1; for (int i = 1; i 이제 중복되는 요소를 제거해보자.이전에 마지막으로 등장한 S[i - 1]의 위치를 j라고 하자..

문제https://www.acmicpc.net/problem/32184 풀이페이지 A ~ B를 전부 촬영한다고 할 때 최소 촬영 횟수를 구하는 문제다.A가 짝수이고, B가 홀수일 때, 양 끝을 분리해서 촬영해야 하므로 필요한 최소 촬영 횟수는 $\frac{B - A}{2} + 2$이다. 이 외에는 겹쳐서 촬영이 되기 때문에 $\frac{B-A}{2} + 1$이 된다. // Solve & Output if (A % 2 == 0 && B % 2 == 1) { System.out.println((B - A) / 2 + 2); } else { System.out.println((B - A) / 2 + 1); } }}소..

문제https://www.acmicpc.net/problem/1388 풀이주어진 보드에서 ‘|’ 또는 ‘-’ 모양의 타일을 각각 세로와 가로로 전부 연결해서 만들어지는 판자들이 몇개 인지 구하는 문제다.판자가 아닌 타일들을 방문하면서 규칙에 따라 하나의 판자로 만들어주는 횟수를 세면 된다. // Solve int cnt = 0; for (int i = 0; i 현재 타일의 종류에 따라 가로 또는 세로로 연결된 동일한 종류의 타일들을 모두 방문해주자.만약 다른 종류의 타일이 나온다면 더 이상 연결할 수 없으므로 탐색을 중단해야 한다. private static void connect(int x, int y, char type) { if (type ==..