문제http://boj.ma/25393요약구간의 시작과 끝이 동일한 교집합 구간을 만들기 위해, 사용된 구간의 최소 수를 구하자.N ≤ 300,000 , Q ≤ 300,000풀이 과정아이디어단순히 구간 내의 교집합이 아닌, 구간의 시작과 끝이 일치하면서 교집합인 구간을 찾아한다.질의 구간 $[ l, r ]$은 주어진 구간 $[ l, r ]$과 일치할 수 있다.질의 구간 $[ l, r ]$은 주어진 구간 $[ l, R ] (R > r), [ L, r ] (L 그 외에는 질의 구간을 만족하는 구간은 존재하지 않는다.(1)은 주어진 구간을 그대로 Set에 저장하고, 질의 구간과 비교하면 된다.// 구간 저장String in = br.readLine();set.add(in);// 구간 탐색if (set.cont..

문제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/10546 10546번: 배부른 마라토너 boj.ma 풀이문제 요약N명의 참가자 이름과, N - 1명의 완주자 이름을 비교해 마라톤을 완주하지 못한 사람의 이름을 출력하자.아이디어참가자 이름이 중복되는 경우가 있다. Map에 동명이인의 수를 누적해 참가자를 세주고, N - 1명의 완주자 만큼 값을 빼고나면 최종적으로 Map에는 미완주자만 남는다. for (int i = 0; i cur + 1); } for (int i = 1; i cur - 1 == 0 ? null : cur - 1); }풀이시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/..

문제http://boj.ma/3000 3000번: 직각 삼각형 boj.ma 풀이문제 요약좌표축에 평행한 직각삼강형의 수를 구하자.아이디어임의의 직각 삼각형의 꼭짓점(x, y)에 대해 x 또는 y좌표가 평행한 점의 수의 곱은 만들어지는 직각 삼각형의 수와 같다. 전체 빈도에서 꼭짓점을 제외한 후 곱한 결과를 누적하자. // Solve xCnt.put(x[i], xCnt.getOrDefault(x[i], 0) + 1); yCnt.put(y[i], yCnt.getOrDefault(y[i], 0) + 1); } long cnt = 0; for (int i = 0; i 풀이 시간10분소스코드https://github...

문제http://boj.ma/25624 25624번: SNUPTI boj.ma 풀이문제 요약길이가 N이고, 서로 다른 척도로 구성된 결과 M개를 만들기 위해 각 자리 별 척도 집합을 구하자.아이디어주어진 문자열을 바탕으로 척도를 구하고, 결과를 만들어 낼 수 있는지 확인하는 조건은 다음과 같다.입력받은 결과 중 중복되는 결과가 있는지하나의 결과에 척도가 중복되지 않는지 (ex: AA, BCB )척도로 만들어지는 결과 수가 입력과 일치하는지이를 다음과 같이 구현하면 된다.입력받은 결과 중 중복되는 결과가 있는지 확인하자. private static boolean solve(Set[] set, String[] input) { Set words = new HashSet(); fo..

문제http://boj.ma/11067 11067번: 모노톤길 boj.ma 풀이문제 요약N개의 카페를 왼쪽에서 오른쪽 방향으로 주어진 규칙대로 이동할 때, 카페의 좌표를 통해 방문 순서를 정하자.아이디어왼쪽에서 오른쪽으로 향하며 코너에 위치한 카페에서만 회전 할 수 있고, 그 외에는 직진만 가능하다. 현재 카페 좌표와 이전에 지나온 카페 좌표의 x가 다르다면, y가 동일한 카페로만 이동할 수 있다. 따라서 동일한 x좌표에 대해 y좌표가 적절히 정렬되어 있어야 한다. 매번 y좌표의 동일 여부에 따라 오름차순/내림차순 정렬을 수행하기보다는 이미 정렬된 요소들의 순서를 뒤집으면 된다. // Solve for (List yList : cafe.values()) { ..

문제1270번: 전쟁 - 땅따먹기 1270번: 전쟁 - 땅따먹기 boj.ma 풀이병사들의 번호가 주어질 때, 과반수를 넘는 병사가 존재하는지 검사하는 문제다.Boyer-Moore Voting으로 과반수가 넘는 병사를 빠르게 찾는 방법으로 풀이했다.병사의 번호가 int 범위보다 크므로 long을 사용하자. long candidate = -1, virtualCnt = 0; for (int i = 0; i 가상의 병사 번호 빈도가 실제로 절반을 초과하는지 검사 후 병사의 번호 또는 “SYJKGW”을 출력하자. long actualCnt = 0; for (long a : A) { if (a == candi..

문제https://www.acmicpc.net/problem/14402 풀이동명이인을 고려한 전체 출퇴근 기록에 대해 출근 기록과 퇴근 기록이 일치하지 않는 경우를 전부 야근이라 가정하고, 전체 야근 인원을 구하는 문제다.만약 동명이인이 출근을 했다면, 출근한 동명이인의 수를 세주자. // Solve Map map = new HashMap(); int res = 0; while (N-- > 0) { st = new StringTokenizer(br.readLine()); String name = st.nextToken(); String op = st.nextToken(); if..

문제https://www.acmicpc.net/problem/1354 풀이주어지는 N에 대해 $A_N$을 구하는 문제다.단 N은 최대 $10^{13}$이며, 중복되는 계산을 최소화 해야한다.범위가 넓기 때문에 Map을 사용해서 중간 계산을 기록하면 된다. private static long getA(long i) { if (i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01354.java

풀이이번 달 까지의 선물을 주고받은 기록과 선물 지수를 토대로 다음달에 선물을 많이 받는 사람을 예측하는 문제다.문제에서 주어진 조건은 다음과 같다.1. 선물 기록이 있다면 더 많은 선물을 준 사람이 선물을 받는다.2. 선물 기록이 없거나 같다면, 선물 지수가 더 큰사람이 받는다.선물 지수는 이번 까지 자신이 친구들에게 준 선물 수에서 받은 선물 수를 뺀 값이다.즉, 받은것보다 준 횟수가 더 많다면 선물 지수는 높아진다.먼저 3개의 dict을 만들어 주자.각각 선물을 주고받은 기록( gift_history ), 선물 지수( gift_level ), 다음 달에 받을 선물 수( give )이다.gift_history의 경우 여러명으로부터 여러개의 선물을 받기 때문에 중첩 구조로 구성하자.참고로 문제에서 자기..