Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- Deep Dive
- 파일 url
- Dev-Matching
- 우아한테크코스
- redis
- invalid_grant
- 우아한 테크코스
- 프로그래머스
- NestJS
- compateto
- api 요청 수 제한
- 딥다이브
- this
- 음악 url 파일 다운로드
- AWS
- 프론트엔드 과제
- 스프링부트
- concurrency limit
- 프리코스
- 타입스크립트
- TypeORM
- 검색
- 유효시간 설정 url
- 모던 자바스크립트
- 프론트엔드
- 자바스크립트
- bucket4j
- api 비동기처리
- oauth
- 코멘토 #코멘토실무PT #실무PT후기 #실무강의 #리액트강의 #웹프로그래밍 #react #웹개발실무
Archives
- Today
- Total
개발 알다가도 모르겠네요
삼성 SDS 대학생 알고리즘 특강 2일차 - 정렬 본문
728x90
Compare 함수의 이해
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
Item item1 = new Item(1,3,1);
Item item2 = new Item(1,2,3);
Item item3 = new Item(1,1,2);
List<Item> list = new ArrayList<>();
list.add(item1);
list.add(item2);
list.add(item3);
System.out.println(list);
Collections.sort(list);
System.out.println(list);
}
}
class Item implements Comparable<Item> {
int a;
int b;
int c;
public Item(int a, int b, int c){
this.a = a;
this.b =b;
this.c = c;
}
@Override
public String toString() {
return "{" +
"a=" + a +
", b=" + b +
", c=" + c +
'}';
}
@Override
public int compareTo(Item o) {
//음수 -> 원래 순서
//0
//양수 -> SWAP
if(b < o.b){
return -1;
} else if(b==o.b){
return 0;
} else {
return 1;
}
//return o.b - b;
//내림차순시 b - o.b;
}
}
//실행 결과
// [{a=1, b=3, c=1}, {a=1, b=2, c=3}, {a=1, b=1, c=2}]
// [{a=1, b=1, c=2}, {a=1, b=2, c=3}, {a=1, b=3, c=1}]
but 순서가 헷갈릴 수 있다.
따라서 아래의 compare을 쓰면 수월.
//기본은 오름차순
return Integer.compare(o.b, b);
//내림차순
return Integer.compare(b, o.b);
Comparator 사용시 기존의 compareTo 덮어씌움.
Comparator<Item> comp = new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
return o1.c - o2.c;
}
};
Collections.sort(list, comp);
System.out.println(list);
getter 추가 후 Comparator.comparingInt(o::get~) 형식으로 해도 정렬 가능.
Collections.sort(list, Comparator.comparingInt(Item::getB));
System.out.println(list);
class Item implements Comparable<Item> {
int a;
int b;
int c;
public int getA() {
return a;
}
public int getB() {
return b;
}
public int getC() {
return c;
}
public Item(int a, int b, int c){
this.a = a;
this.b =b;
this.c = c;
}
@Override
public String toString() {
return "{" +
"a=" + a +
", b=" + b +
", c=" + c +
'}';
}
}
그러면 Comparable과 Comparator의 역할은 비슷한 것 같은데 무슨 차이인 것일까?
왜 Comparable의 compareTo(T o) 메소드는 파라미터(매개변수)가 한 개이고, Comparator의 compare(T o1, T o2) 메소드는 파라미터가 왜 두 개인 것일까?
일단, 두 인터페이스를 구체적으로 알아보기에 앞서 먼저 정답부터 말하자면, Comparable은 "자기 자신과 매개변수 객체를 비교"하는 것이고, Comparator는 "두 매개변수 객체를 비교"한다는 것이다.
쉽게 말하자면, Comparable은 자기 자신과 파라미터로 들어오는 객체를 비교하는 것이고, Comparator는 자기 자신의 상태가 어떻던 상관없이 파라미터로 들어오는 두 객체를 비교하는 것이다. 즉, 본질적으로 비교한다는 것 자체는 같지만, 비교 대상이 다르다는 것이다.
1713: 후보 추천하기
import java.util.*;
public class Main {
static class Student implements Comparable<Student> {
int num;
int time;
int like;
boolean isIn; //사진틀에 이 사람이 있는지 없는지 확인
public Student(int num, int like, int time, boolean isIn){
this.time = time;
this.like = like;
this.num = num;
this.isIn = isIn;
}
public int compareTo(Student s){
//1. 추천수, 2. 시간
int comp = Integer.compare(like, s.like);
if(comp == 0){
return Integer.compare(time, s.time);
} else
return comp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Student[] students = new Student[101];
int n = sc.nextInt();
int allLike = sc.nextInt();
//1.학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
ArrayList<Student> picture = new ArrayList<>();
//2.어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
for(int i=0; i<allLike; i++){
int num = sc.nextInt();
//해당 후보가 최초 호출 시
if(students[num] ==null){
students[num] = new Student(num, 0, 0, false);
}
//해당 후보가 사진틀에 있을 경우
if(students[num].isIn == true){
students[num].like++;
}
//해당 후보가 사진 틀에 없음
else {
//사진들이 가득 찬 경우
if(picture.size() == n){
//정렬, 지울 후보 선정, 제거
Collections.sort(picture);
picture.get(0).isIn = false;
picture.remove(0);
}
//사진틀에 여유가 있는 경우
//students[num].num = num;
students[num].like = 1;
students[num].isIn = true;
students[num].time = i;
picture.add(students[num]);
}
}
Collections.sort(picture, new Comparator<Student>() {
public int compare(Student s1, Student s2){
return Integer.compare(s1.num, s2.num);
}
});
for(int i=0; i<picture.size(); i++){
System.out.print(picture.get(i).num+" ");
}
}
}
2003: 수들의 합 2
슬라이딩 윈도우 - 연속된 수들의 합 구할 때.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] nums = new int[N+1];
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
nums[i] = Integer.parseInt(st.nextToken());
}
int low = 0, high = 0, sum = nums[0], count = 0;
while (true){
// sum == M -> 답 low++
if(sum==M){
count++;
sum -= nums[low++];
}
// sum > M -> low++
else if (sum > M){
sum -= nums[low++];
}
// sum < M -> high++
else {
sum += nums[++high];
}
if(high == N){
break;
}
}
System.out.println(count);
}
}
1806: 부분합
슬라이딩 윈도우
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] nums = new int[N+1];
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
nums[i] = Integer.parseInt(st.nextToken());
}
int low = 0, high = 0, sum = nums[0], min = Integer.MAX_VALUE;
while (true){
// sum >= M -> 답 low++
if(sum>=M){
min = Math.min(high-low+1,min);
sum -= nums[low++];
}
else {
sum += nums[++high];
}
if(high == N){
break;
}
}
if(min == Integer.MAX_VALUE){
System.out.println(0);
} else{
System.out.println(min);
}
}
}
2805: 나무 자르기
투 포인터
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] trees = new int[N];
long max = 0;
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
trees[i] = Integer.parseInt(st.nextToken());
max = Math.max(trees[i],max);
}
long s = 0;
long e=max;
long mid=0;
long result = 0;
while(true){
long sum = 0;
mid = (s+e) /2;
for(int i=0; i<trees.length; i++){
if(trees[i]>mid){
sum+=trees[i] - mid;
}
}
//sum == M -> 정답, 탈출
if(sum == M){
result = mid;
break;
}
//sum < M -> mid -> end
else if(sum<M){
e = mid-1;
}
//sum > M -> mid -> s, 정답 후보
else {
result = mid;
s = mid+1;
}
//시작점이 끝점보다 커지면
if(s>e){
break;
}
}
System.out.println(result);
}
}
2143: 두 배열의 합
투 포인터 (subA, subB 만들어서)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
//1. SubA, SubB
//2. 정렬
//3. 2Pointer
public class Main {
static long T;
static int N, M;
static long[] inputA, inputB;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Long.parseLong(st.nextToken());
N = Integer.parseInt(br.readLine());
inputA = new long[N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
inputA[i] = Long.parseLong(st.nextToken());
}
M = Integer.parseInt(br.readLine());
inputB = new long[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<M;i++){
inputB[i] = Long.parseLong(st.nextToken());
}
List<Long> subA = new ArrayList<>();
List<Long> subB = new ArrayList<>();
//subA 구하기
for(int i=0; i<N; i++){
long sum = inputA[i];
subA.add(sum);
for(int j= i+1; j<N; j++){
sum += inputA[j];
subA.add(sum);
}
}
//subB 구하기
for(int i=0; i<M; i++){
long sum = inputB[i];
subB.add(sum);
for(int j= i+1; j<M; j++){
sum += inputB[j];
subB.add(sum);
}
}
//subA, subB 정렬하기
Collections.sort(subA);
Collections.sort(subB, Comparator.reverseOrder());
long result = 0;
int ptA = 0;
int ptB = 0;
while(true){
long currentA = subA.get(ptA);
long target = T - currentA;
//currentB == target -> subA, subB 같은 수 개수 체크 -> 답구하기.
if(subB.get(ptB) == target){
long countA = 0;
long countB = 0;
while(ptA < subA.size() && subA.get(ptA) == currentA){
countA++;
ptA++;
}
while(ptB < subB.size() && subB.get(ptB) == target){
countB++;
ptB++;
}
result += countA * countB;
}
//currentB > target -> ptB++
else if(subB.get(ptB)>target){
ptB++;
}
//currentB < target -> ptA++
else {
ptA++;
}
//탈출 조건
if(ptA == subA.size() || ptB == subB.size()){
break;
}
}
System.out.println(result);
}
}
1072: 게임
파라메트릭 서치
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static long X, Y;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
long Z = Y*100 / X;
if(Z >= 99){
System.out.println(-1);
} else {
long start = 0;
//X를 최대값으로 넣어도 됨. 다만 X로 하면 효율화 최대.
long end = X;
while(start < end){
long mid = (start + end) / 2;
long newRate = (100 * (mid + Y) / (mid + X));
//승률이 그대로 인 경우
if(newRate == Z){
start = mid + 1;
}
//승률이 변한 경우
else {
end = mid;
}
}
System.out.println(end);
}
}
}
'학습일지 > 삼성 SDS 알고리즘 특강' 카테고리의 다른 글
삼성 SDS 대학생 알고리즘 특강 6일차 - 그래프 (0) | 2022.07.25 |
---|---|
삼성 SDS 대학생 알고리즘 특강 5일차 - 조합론 (0) | 2022.07.22 |
삼성 SDS 대학생 알고리즘 특강 4일차 - 트라이 트리, 정수론 (0) | 2022.07.21 |
삼성 SDS 대학생 알고리즘 특강 3일차 - 자료구조 (0) | 2022.07.20 |
삼성 SDS 대학생 알고리즘 특강 1일차 - DFS&BFS (0) | 2022.07.18 |