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

문제https://boj.ma/1022 1022번: 소용돌이 예쁘게 출력하기 boj.ma 요약중심지(0, 0)에서부터 반시계방향으로 숫자가 증가하면서 채워진 10,001칸인 모눈 종이에서, (r1, c1) ~ (r2, c2)의 영역을 예쁘게 출력하자.제한 시간 ≤ 2s, 메모리 제한 128 MB풀이 과정아이디어모든 칸에 숫자를 채워 넣는것은 시간적으로 가능하지만, 공간적으로는 불가능하다. 따라서 모든 칸을 계산하지 않고도 주어진 영역의 값을 구해야 한다.이를 위해서는 소용돌이의 규칙을 찾아야 한다. 우선 주어진 입력은 왼쪽 상단 좌표, 오른쪽 하단 좌표인데 오른쪽 하단 좌표가 $1^2, 3^2, 5^2, 7^2...$로 규칙성을 띈다.임의의 좌표 $(x, y)$가 속한 소용돌이의 정사각형 경계선(leve..

문제http://boj.ma/23350 23350번: K 물류창고 boj.ma 풀이문제 요약우선순위가 낮은 박스들을 무거운 순서대로 놓도록 박스를 돌려보내거나, 나머지 공간에 쌓았다가 다시 쌓는 비용을 계산하자.아이디어레일에 존재하는 박스 중 우선순위가 가장 낮은 박스먼저 쌓아야 한다.가장 낮은 우선순위가 아니라면 뒤로 보내자.현재 처리해야 하는 우선순위의 박스에 대해, 이미 쌓여있는 동일한 우선순위의 박스의 무게와 비교해 무거운 박스가 먼저 쌓이도록 가벼운 박드를 나머지 공간으로 이동 후 쌓아주자.1 ~ M의 우선순위에 대해 박스는 적어도 하나 존재하므로 별도의 예외 검증없이, 우선 순위 빈도만큼 박스를 쌓았다면, 다음 우선 순위는 현재 우선순위 - 1이 된다. private static int mov..

문제http://boj.ma/16927 16927번: 배열 돌리기 2 boj.ma 풀이문제 요약배열을 반시계방향으로 R번 회전하자.아이디어R을 회전하려는 부분 배열의 전체 길이로 나눈 만큼만 회전해도 된다.어차피 제자리로 되돌아오기 때문이다. Max(N, M)개의 부분 배열에 대해 각각 회전을 해주자.처음 풀어보는 유형이라면 구현에 시간이 좀 걸린다. private static void rotate(int start, final int LEN) { int r = R % LEN; while (r-- > 0) { final int temp = board[start][start]; int x = start, y = start; int d = 0; while (d 풀이 시간40분소스코드http..

문제http://boj.ma/27941 27941번: 하이퍼 가지 따기 boj.ma 풀이문제 요약11차원 큐브의 2048개 꼭짓점 중 누락된 한 꼭짓점의 좌표를 구하자.아이디어11차원 큐브의 각 꼭짓점 좌표는 해당 차원의 양 끝값인 L과 R중 하나의 값을 가진다.주어지는 입력에는 L과 R이 1024, 1023개로 어느 한 좌표가 한 개 부족하게 주어진다.따라서 2047개의 좌표의 각 차원에 대한 XOR연산을 수행한다면, 교환 법칙과 자기 자신과의 연산에 의해 결국 필요한 좌표를 얻을 수 있다. int line = 2047; while (line-- > 0) { st = new StringTokenizer(br.readLine()); for (int i = 0; i 풀이 시간10분소스코드http..

문제http://boj.ma/20165 20165번: 인내의 도미노 장인 호석 boj.ma 풀이문제 요약주어진 보드에서 도미노를 넘어뜨리고 세우고를 반복했을 때, 몇 개의 도미노가 넘어졌었는지 출력하자.아이디어요구 사항을 되짚어보자.도미노를 넘어뜨리려는 위치에 이미 넘어져 있다면 아무 일도 일어나지 않는다.넘어뜨린 도미노의 번호 K에 대해 동일한 방향으로 K - 1개 넘어뜨릴 수 있으며, 이는 다음 도미노에 의해 갱신될 수 있다.넘어뜨린 도미노는 다시 세울 수 있다. 이 때 도미노 번호 K를 다시 복구해야 한다.넘어뜨린 도미노는 음수로 표현했으며, 현재 쓰러트린 도미노의 번호에 의해 쓰러트릴 수 있는 도미노의 최대 길이를 갱신해주면서 시뮬레이션을 반복하면 된다. private static int atta..

문제http://boj.ma/13414 13414번: 수강신청 boj.ma 풀이문제 요약수강 신청 버튼을 클릭한 기록 L개 중 문제의 조건에 맞게 최대 K명의 수강 신청을 처리하자.아이디어수강 신청 버튼을 처음에 누른 후 또 눌렀다면 순서가 밀려야 한다. Map을 이용해 학번과 버튼을 누른 순서를 저장하고, 이미 저장이 되있더라도 새로 버튼을 눌렀다면 순서만 업데이트해주자.Map은 순서가 보장되지 않으므로, 리스트에 담아준 후 버튼을 누른 순서를 기준으로 정렬 후 최대 K명을 뽑으면 된다. // Solve Map map = new HashMap(); for (int i = 0; i > list = new ArrayList(map.entrySet()); list.sort((a, b) -> a.get..

문제http://boj.ma/16924 16924번: 십자가 찾기 boj.ma 풀이문제 요약주어진 격자판이, 문제의 규칙대로 만들어지는 십자가에 의해서만 만들어질 수 있는지 알아보자.아이디어격자판의 크기가 작으므로 모든 위치에 대해 십자가가 만들어질 수 있는지 전부 확인하면 된다. 단 문제의 규칙대로만 만들어지는 십자가에 의해서만 만들어지는 경우에만 방문 표시를 해주자.모든 위치에 대한 확인이 끝난 후 ‘*’인데 방문 표시가 안되었다면 십자가만을 이용해서 격자판을 만들 수 없는 경우로 -1을 출력하자.필요한 십자가의 수가 0일 수 있으니, ‘*’이 존재하지 않는다면 0을 출력해야 한다. private static int isCross(int x, int y, int size) { for..

문제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/19843 19843번: 수면 패턴 boj.ma 풀이문제 요약민티의 수면 기록이 주어졌을 때, 주말에 몇 시간을 더 자야 한 주에 T시간을 잘 수 있는지 구하자.아이디어잠든/일어난 요일이 다르다면, 두 요일의 차 * 24 시간과 두 시간의 차를 빼주자. 요일이 같다면 두 시간의 차만 빼면 된다.만약 모든 수면 기록이 48시간 보다 크다면 주말 내내 자도 부족하다. 평일에 이미 T보다 많이 잤다면, 주말에는 잠을 자지 않아야 한다 List days = List.of(new String[]{"Mon", "Tue", "Wed", "Thu", "Fri"}); while (N-- > 0) { st = new StringTokenizer(br..