레벨업 일지

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 자 단순하게 O(N) 탐색으로 풀수있다. 쭈루룩 훑어가면서 현재 min 보다 낮은게 나오면 min을 업데이트 해주고 거리 x min 누적합을 구해주면 OK. 참고 자바의 long type을 명시 안하면 int overflow 발생함으로 주의 코드 import java.io.*; import java.util.*; public class Main { int n, k; int..

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 최대한 적게 멀티플러그를 빼는 문제. 게시판 반례 참고해서 코드 수정 하였다. 풀이는 다음과 같다. 1. 현재 멀티탭이 구멍보다 작을 때 플러그를 꽃는다. 2. 멀티탭 남는 구멍이 없어 플러그를 빼야 하면, 다음 등장하는 인덱스가 가장 큰 것을 플러그에서 제거한다. 3. 이미 멀티탭에 있는 번호가 나왔으면, 다음 등장 인덱스를 업데이트 해준다. 먼저 해시맵을 사용해서 현재 기준 cur ..

문제 https://www.acmicpc.net/problem/25947 25947번: 선물할인 입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 www.acmicpc.net 조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다. 풀이 풀이는 다음과 같다. int left, right 를 선언해주어 left .. right 범위 내의 윈도우 슬라이드에 담긴 물건들을 "할인해서 구매한 물건들" 로 정의하였다. 1. 주어진 배열 오름차순 정렬 2. 먼저 할인 가능하면 가능한 만큼 일단 구매한다. 3. 더 이상 할인 할 수 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 풀이 원리는 투포인터를 이용한 윈도우 슬라이더를 유지하면서 풀었다. 리트코드에서 풀었던 최대 빈도수와 원리는 같다. https://0713k.tistory.com/11 [java/python3]leetcode 1838. Frequency of the Most Frequent Element Frequency of the Most Frequent Element - LeetCode Frequ..

문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 풀이 현재 위치 i 에서 0..i-1 중에 자신의 실력보다 낮은 개수를 센 다음, 차를 구하는 문제. 분할 정복으로 정렬해서 O(N log N) 풀이하였다. 알고리즘은 다음과 같다. 1. 분할 정복 소트 기법을 사용한다. 2. 두 배열을 병합할때 RIght 배열 원소를 삽입 할때 자기 Left 배열에서 현재숫자보다 낮은 개수를 누적합한다. 3. 자기 자신의 인덱스 - 자신 실력보다 낮은..

문제 https://www.acmicpc.net/problem/15975 15975번: 화살표 그리기 직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 www.acmicpc.net 풀이 우선 색깔 별로 정렬을 한다. 같은 색깔이면, 좌표순 오름차순 정렬. 그 다음 O(N)으로 탐색 하면서, 현재 위치 i 에서 left = i-1 , right = i+1 을 꺼내서 비교를 해준다. ArrayList Info = new ArrayList(); // 이런식으로 2차원 리스트를 받는다. Collections.sort(Info, (a,b)->a[1] =..

문제 2212번: 센서 (acmicpc.net) 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 이해를 잘 해야한다. 처음에 센서들의 거리 누적합을 구하는줄 알고 잘못된 접근을 하였다. 센서의 개수 N , 집중국의 개수 K 가 주어진다. 먄약 K == N 이면 각 집중국마다 센서가 있음으로 거리합이 0 이 된다 . 만약 K == 1 이면, 집중국은 센서의 거리 범위 ( i.. j ) 안에 놓기만 하면 j - i 거리합이 된다. K > 1 이면, 이때부터 잘 봐야한다. 1. 센서의..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은..