본문 바로가기
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/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 문제에서 귤의 크기와 상관없이 크기의 종류가 최소일 때 담으려는 귤의 수를 원하기 때문에 같은 크기인 귤의 수를 구하고 내림차순 정렬해주어 k개만큼 귤을 넣었을때 종류의 수를 return 으로 해결할 수 있는 문제입니다. tangerine의 원소의 범위가 길어 배열의 정렬은 시간초과가 날 수 있어 Map을 사용해 특정 크기의 귤 수를 구하고 해당 값으로 List를 만들어 정렬 후 fo.. 더보기
[프로그래머스] 테이블 해시 함수 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/147354 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 중요하게 볼 부분이 2개 있습니다. 2차원 배열의 조건이 여러개인 정렬 XOR 1. 2차원 배열의 조건이 여러개인 정렬 주어진 2차원 배열을 정렬하기 위해 Arrays.sort와 람다식, 삼항연산자를 이용하였습니다. Arrays.sort(data, (a,b)-> a[col-1]==b[col-1] ? b[0]-a[0] : a[col-1]-b[col-1] ); 이때 col은 1부터 시작하.. 더보기
[프로그래머스] 호텔 대실 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/155651# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 예약시간이 주어질 때 시간이 겹치지 않기 위한 최소한의 방의 개수를 구하는 문제이다. 만약 Bruteforce로 해결하려 한다면 배열 book_time의 길이가 1000이므로 1000!이 되어 연산이 불가능할 정도로 커진다. 따라서 그리디방식을 사용하여 문제를 풀기로 했다. (1)시작시간을 기준으로 정렬해주어 시간순서대로 방에 들어가도록 해주고, (2)새로운 시간이 들어올 때마다 끝.. 더보기
728x90

티스토리툴바