레벨업 일지

문제 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://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Longest Increasing Subsequence - Given an integer array nums, return the length of the longest strictly increasing subsequence. Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], ther leetcode.com 문제 가장 최장으로 증가하는 부분 수열의 길이를 ..

문제 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] =..

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/ Minimum Number of Arrows to Burst Balloons - LeetCode Minimum Number of Arrows to Burst Balloons - There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizonta l..

문제 https://leetcode.com/problems/3sum-smaller/description/ 3Sum Smaller - LeetCode 3Sum Smaller - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 int: nums.sort() ans = 0 for i in range..

문제 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://school.programmers.co.kr/learn/courses/30/lessons/42891 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시간이 주어졌을때 무지가 다음에 먹을 음식 번호를 리턴 풀이 푸는 방법은 알았는데 효율성 2에서 틀린 문제. 효율성 테스트 제한 사항 food_times 의 길이는 1 이상 200,000 이하이다. food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다. k는 1 이상 2 x 10^13 이하의 자연수이다 k 가 long 형으로 잡혀있다. 자바에서 int 의 최대 크기는..

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개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은..