본문 바로가기
728x90

우선순위큐

[백준] 2170 선 긋기 / 자바(Java) 문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 해설 입력값의 범위가 넓어 정렬이 필요하지만 양이 너무 많아 우선순위큐를 통해 문제를 해결한다. 우선순위큐에 넣을 때 NlogN번, 하나씩 빼면서 답을 계산할때 N번으로 총 O(NlonN)만큼의 시간복잡도로 해결이 가능하다. 주의점 입력 값의 범위가 너무커 Long타입을 사용한다. 코드 import java.io.BufferedReader; import jav.. 더보기
[프로그래머스] 디펜스 게임 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 dfs, dp등 여러 방법을 고려해봤지만 각 변수(n, k, enemy의 길이)가 너무 길어 시간초과가 걸렸습니다. 적들을 만나는데 순서가 있어 정렬을 사용하지 못하겠다고 생각했지만 조금 바꿔보면 가능했습니다. 처음부터 모든 적을 무적권없이 해결한다 가정하고 한계가 올 때마다 그동안 만난 적 중 가장 힘든 적(자동으로 계산하기 위해 우선순위큐를 사용)을 무적권으로 넘겨 다시 병사를 회.. 더보기
[프로그래머스] 호텔 대실 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/155651# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 예약시간이 주어질 때 시간이 겹치지 않기 위한 최소한의 방의 개수를 구하는 문제이다. 만약 Bruteforce로 해결하려 한다면 배열 book_time의 길이가 1000이므로 1000!이 되어 연산이 불가능할 정도로 커진다. 따라서 그리디방식을 사용하여 문제를 풀기로 했다. (1)시작시간을 기준으로 정렬해주어 시간순서대로 방에 들어가도록 해주고, (2)새로운 시간이 들어올 때마다 끝.. 더보기
728x90

티스토리툴바