본문 바로가기
반응형

분류 전체보기163

[Java] 프로그래머스 - 단속카메라 프로그래머스 단속카메라 문제는 모든 차량이 단속 카메라를 만나게 할 수 있는 카메라의 최소 개수를 구하는 문제다. 난이도는 레벨3이며 그리디 알고리즘를 통해 해결할 수 있다. 프로그래머스 - 단속카메라 문제 정보 알고리즘 분류 - 그리디 난이도 - Level 3 문제 요약 각 차량의 고속도로 진입/진출 지점이 주어진다. 모든 차량이 적어도 하나의 단속 카메라를 만나게 하려면 필요한 단속카메라의 최소 개수는? 문제 풀이 과정 진출 지점 기준으로 오름차순 정렬 앞에꺼부터, 가장 마지막 카메라 지나면 패스, 안지나면 현재 차의 진출 지점에 카메라 추가 코드 public int solution(int[][] routes) { Arrays.sort(routes, (o1, o2) -> { if (o1[1] < o2.. 2023. 11. 9.
[Java] 프로그래머스 - 숫자 게임 프로그래머스 숫자 게임 문제는 두 팀이 숫자 게임을 해서 한 팀이 얻을 수 있는 최대 승점을 구하는 문제다. 난이도는 레벨3이며 그리디 알고리즘를 통해 해결할 수 있다. 프로그래머스 - 숫자 게임 문제 정보 알고리즘 분류 - 그리디 난이도 - Level 3 문제 요약 A팀 N명 vs B팀 N명 숫자 게임 모든 사원은 임의의 숫자를 하나씩 부여받는다. (1~10억) 모든 사원은 딱 한번씩만 경기한다. 경기 A 1명, B 1명이 나와서 숫자 비교를 한다. 큰 팀이 1점. 비기면 점수 없음. Q. A팀의 출전 순서가 공개되었을 때, B팀이 얻을 수 있는 최대 승점은? 문제 풀이 과정 N이 10000 이하니까 O(NlogN)까지 가능함 → 정렬 가능 무조건 A팀과 차이가 적게 이겨야 한다. A팀과 B팀 모두 내.. 2023. 11. 9.
[Java] 프로그래머스 - 야근 지수 프로그래머스 야근 지수 문제는 퇴근까지 N시간 남은 회사원 Demi의 야근 피로도를 최소화하는 문제다. 난이도는 레벨3이며 우선순위큐를 활용해 해결할 수 있다. 프로그래머스 - 야근 지수 문제 정보 알고리즘 분류 - 그리디 알고리즘 난이도 - Level 3 문제 요약 (야근 피로도) = sum( (남은 작업량) ^ 2 ) 1시간에 작업량이 1이며, 퇴근까지 N시간 남았다. 가능한 야근 피로도의 최소값은? 문제 풀이 과정 1 핵심 아이디어 제곱들의 합을 최소화시키기 위해서는 숫자들간의 편차를 최소화해야 한다. 따라서 매번 제일 큰 수를 줄여나간다. 작업량 배열을 내림차순으로 정렬 후 앞에서부터 단계별로 줄이기 [4,3,3] → [3,3,3] → [2,2,2] 코드 public static long solu.. 2023. 11. 9.
[Python] 프로그래머스 - 최고의 집합 프로그래머스 최고의 집합 문제는 자연수 n개로 이루어진 중복 집합 중에서 각 원소의 합이 S가 되고 각 원소의 곱이 최대가 되는 집합을 구하는 문제다. 난이도는 레벨3이며 그리디한 방식으로 해결할 수 있다. 프로그래머스 - 최고의 집합 문제 정보 알고리즘 분류 - 그리디 난이도 - Level 3 문제 요약 자연수 n개로 이루어진 중복 집합 중에서 각 원소의 합이 S가 되고 각 원소의 곱이 최대가 되는 집합을 최고의 집합이라고 한다. n, S가 주어졌을 때 최고의 집합을 구하라. 문제 풀이 과정 집합 내의 두 숫자의 차의 최댓값이 1인 경우에 곱이 최대가 된다. ex) n=3, S=8 → {2,3,3} S를 n으로 나누었을 때의 몫과 나머지를 이용하여 최고의 집합을 구할 수 있다. 몫이 0이면 최고의 집합.. 2023. 3. 29.
반응형

티스토리툴바