문제http://boj.ma/28070 28070번: 유니의 편지 쓰기 boj.ma 요약N개의 기간이 가장 많이 겹치는 기간 중 가장 앞선 시기를 구하자.풀이 과정아이디어주어진 N개의 기간에서 동시에 군 복무 중인 친구 수가 가장 많은 시점을 찾아야 한다.N ≤ 1e5이며, 기간의 범위는 1e4 * 12이므로, 단순히 모든 월을 순회하며 각 기간마다 포함 여부를 확인하면 시간 초과가 발생한다.따라서 구간의 시작과 끝만을 이용하는 누적합(스위핑) 방식을 사용한다. 1. 날짜를 인덱스로 변환YYYY-MM 형식을 배열 인덱스로 다루기 위해 다음과 같이 연도 × 12 + 월 형태로 변환한다.private static int toIndex(String s) { int year = Integer.parseInt(s..

문제http://boj.ma/11944요약주어진 N을 N번 출력하자.완성된 문자열이 M보다 길다면, 앞 M자리만 출력하자.풀이 과정아이디어N번 만큼 반복한 문자열을 만들고, 길이가 M보다 크다면 앞 M자리까지 잘라서 출력하면 된다.// SolveString ori = in[0].repeat(N);if (ori.length() > M) { ori = ori.substring(0, M);}최적화N번 만큼 반복한 문자열의 최대 길이는 $2^{13}$이다.M은 최대 $2^{11}$이므로, 불필요한 문자열을 생성 후 자르게 된다.반복한 문자열의 길이가 M보다 클 때, 필요한 최소 반복 횟수만큼 생성 후 문자열을 잘라도 된다.final int len = in[0].length();final int oriLen = ..

문제http://boj.ma/16719요약주어진 문자열을 만들기 위해, 문자를 추가해 만들어진 문자열들의 순서가 사전순이 되도록 만들자.문자열의 길이 ≤ 100풀이 과정아이디어만들어지는 문자열들의 순서가 사전순이 되기 위해서는, 사용하지 않은 문자 중 적절한 문자를 선택하는 기준은 아래와 같다.전체 문자 중 사전순으로 가장 앞서는 문자사전 순으로 동일한 문자 중 문자열의 앞에 위치한 문자int idx = left;for (int i = left + 1; i 이전에 선택한 문자보다 뒤에 있는 문자이전에 선택한 문자보다 앞에 있는 문자recursive(idx + 1, right);recursive(left, idx - 1);문자열의 길이는 최대 100이므로, 완전 탐색이 가능하다. 재귀를 통해 이전에 선택한..

문제http://boj.ma/15927 15927번: 회문은 회문아니야!! boj.ma 풀이문제 요약문자열 S의 팰린드롬이 아닌 가장 긴 부분 문자열의 길이를 구하자.아이디어팰린드롬이 아닌 가장 긴 부분 문자열의 길이는 아래와 같이 구할 수 있다.S가 팰린드롬이고, 모두 동일한 문자라면, -1S가 팰린드롬이고, 모두 동일한 문자가 아니라면, N - 1S가 팰린드롬이 아니라면, Npublic class Main { private static int solve(char[] S) { boolean isPalindrome = true; for (int i = 0; i > 1); ++i) { if (S[i] != S[S.length - 1 - i]) { isPalindrome = false; b..

문제http://boj.ma/24725 풀이문제 요약NM 배열에서 상하좌우, 대각선의 여러 방향에서 만들어지는 MBTI의 총 개수를 구하자.아이디어배열의 모든 위치를 돌아보며 8개의 방향에 대해 MBTI가 만들어지는지 확인하면 된다. MBTI를 Map 또는 bool 배열로 만들어두어 문자를 쉽게 비교할 수 있다.import java.io.*;import java.util.*;public class Main { static int[] di = {-1, -1, 0, 1, 1, 1, 0, -1}; static int[] dj = {0, 1, 1, 1, 0, -1, -1, -1}; public static void main(String[] args) throws Exception { ...

문제http://boj.ma/10384 10384번: 팬그램 boj.ma 풀이문제 요약문자열에 모든 알파벳이 등장하는 최소 횟수를 구해 적절한 문구를 출력하자.아이디어알파벳에 대한 빈도를 모두 기록 후 최소 빈도를 찾으면 된다.import java.io.*;public class Main { private static final String[] MSG = { "Not a pangram\\n", "Pangram!\\n", "Double pangram!!\\n", "Triple pangram!!!\\n" }; public static void main(String[] args) throws Exception { . . . ..

문제http://boj.ma/4446 4446번: ROT13 boj.ma 풀이문제요약주어진 문장 중 알파벳에 대해 규칙대로 변환하자.아이디어주어진 규칙을 구현하면 된다. 대문자/소문자도 처리할 수 있어야 하며, 알파벳이 아니라면 변환없이 넘어가면 된다. if (!Character.isLetter(chr)) { sb.append(chr); continue; } boolean isUpper = Character.isUpperCase(chr); char lowerChr = Character.toLowerCase(chr); ..

문제http://boj.ma/09324 9324번: 진짜 메시지 boj.ma 풀이문제 요약문자열에 각 문자가 세 번째 등장할 때 한 번 더 문자가 추가되야 하는 규칙을 준수하는지 확인하자.아이디어각 문자의 빈도를 세며 3번 째로 등장할 때 마다 다음 문자가 없거나, 있는데 다른 문자라면 규칙을 준수하지 않은 문자열이다. private static String solve(char[] S) { int[] alpha = new int[26]; for (int i = 0; i 풀이시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/09324.java problem-solv..

문제http://boj.ma/26264 26264번: 빅데이터? 정보보호! boj.ma 풀이문제 요약bigdata 또는 security로만 구성된 문자열에서 각 단어의 빈도에 따라 적절한 결과를 출력하자아이디어문자열은 두 단어로만 구성되어 있으며, 두 단어의 빈도는 ‘b’와 ‘s’의 빈도로 쉽게 알 수 있다. // Solve int moreSecurity = 0; for (int i = 0; i 풀이시간3분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/26264.java problem-solving/baekjoon-online-judge/practice/..

문제http://boj.ma/1622 1622번: 공통 순열 boj.ma 풀이문제 요약두 문자열의 가장 긴 공통 부분 수열의 순열이면서, 사전순으로 정렬된 문자열을 구하자.아이디어어떤 문자열이 두 문자열의 부분 수열의 순열이 되기 위해선, 공통으로 등장하는 문자이여야 하며, 두 문자열에서의 빈도가 가장 적은 갯수로 구성될 수 있다.즉 두 문자열의 알파벳 빈도를 세고, 사전 순으로 만들어질 수 있는 가장 긴 공통 부분 수열의 순열을 생성하면 된다. private static int[] getCnt(String s) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { ++cnt[c - 'a']; ..