client host request, receives service from always-on server
ex. web browser/server, email client/server
peer-peer model
minimal use of dedicated servers
ex. skype, bitTorrent, KaZaA
network core
access networks, physical media
network core에서 데이터를 전달하는 방식
1. circuit switching
출발지에서 목적지까지 가는 길을 다 계산해 놓는다.
bandwidth에 따라 사용할 수 있는 인원 제한이 있다.
ex. 유선 전화 방식
2. packet switching - 인터넷에서 사용
유저에게 패킷을 받아서 그때그때 포워딩 해준다.
많은 사용자가 몰리면 각자의 사용 시간에 따라 분산되어서 제약 없이 사용할 수 있다.
packet switching의 단점: delay, loss
processing delay: 먼저 라우터에서 패킷을 받으면, 맨 먼저 패킷 검사를 한다.(어디로 가야하는지, 제대로 된 패킷인지 확인) ⇒ 라우터 성능에 따라 줄일 수 있다.
queueing delay: 라우터에서 나가는 속도보다 쌓이는 속도가 빠르게 되면 라우터 안에서 줄이 생길텐데, 잠깐 저장하는 큐가 있다. 이 경우 자신의 순서가 될 때까지 기다려야 한다. ⇒ 사용자들이 사용하는 패턴에 따라 달라진다. 네트워크 상황에서 발생하는 거의 모든 delay의 원인 ⇒ 큐의 크기도 제한되어 있기 때문에, 너무 많은 데이터가 들어오면 유실된다. 인터넷에서 발생하는 거의 모든 loss의 원인
transmission delay: 내 차례가 되어서 나가는 순간, 첫번째 비트부터 마지막 비트까지 데이터가 모두 나가는 순간까지 걸리는 시간이 있다. ⇒ packet length(bits)/link bandwidth(bps) ⇒ 케이블 공사를 해서 bandwidth를 늘리면 줄일 수 있다.
propagation delay: 물리적인 link를 통해 sender에서 receiver까지 도달하는 시간을 의미한다. 보통 통신 선의 종류에 따라 크게 달라짐 ⇒ length of physical link/propagation speed in medium(=빛의 속도)
그러면 패킷 유실이 일어난다면 재 전송이 필요한데, 누가 재전송 할 것이냐?
⇒ 맨 처음 라우터가 재전송: 왜냐하면 라우터는 빠르게 전달하는 것이 목적이므로, 단순 작업을 하는 것을 최대한 목표로 한다. 지능적인 작업은 최대한 edge에 몰아 넣도록 한다.
방을 방문하기 위한 순서가 있다. 2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다. 2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다. 2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다. 2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다. => 사이클이 없다
문제 조건을 읽으니 가장 먼저 위상 정렬을 이용해서 풀어야겠다는 생각이 들었다.
풀이 로직은 아래와 같다.
1. path를 이용하여 양방향 그래프를 생성한다.
2. 양방향 그래프를 bfs를 이용하여 방향 그래프로 바꾸어 준다.
3. 그래프에 order을 적용하여 위상 정렬 알고리즘을 돌린다.
class Solution {
public static boolean solution(int n, int[][] path, int[][] order) {
List<Integer>[] childs = new ArrayList[n];
for (int i = 0; i < n; i++) {
childs[i] = new ArrayList<>();
}
for (int i = 0; i < path.length; i++) {
childs[path[i][0]].add(path[i][1]);
childs[path[i][1]].add(path[i][0]);
}
return isPossible(createGraph(childs), order);
}
public static List<Integer>[] createGraph(List<Integer>[] graph) {
Queue<Integer> q = new LinkedList<>();
List<Integer>[] directedGraph = new ArrayList[graph.length];
for (int i = 0; i < directedGraph.length; i++)
directedGraph[i] = new ArrayList<>();
boolean[] v = new boolean[directedGraph.length];
q.offer(0);
v[0] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur].get(i);
if (v[next])
continue;
directedGraph[cur].add(next);
v[next] = true;
q.offer(next);
}
}
return directedGraph;
}
public static boolean isPossible(List<Integer>[] childs, int[][] order) {
Queue<Integer> queue = new LinkedList<>();
int[] parentNum = new int[childs.length];
for (int i = 0; i < childs.length; i++) {
for (Integer next : childs[i]) {
parentNum[next]++;
}
}
for (int i = 0; i < order.length; i++) {
childs[order[i][0]].add(order[i][1]);
parentNum[order[i][1]]++;
}
for (int i = 0; i < childs.length; i++) {
if (parentNum[i] == 0) {
queue.add(i);
}
}
int cnt = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
cnt++;
for (int i = 0; i < childs[cur].size(); i++) {
int next = childs[cur].get(i);
parentNum[next]--;
if (parentNum[next] == 0) {
queue.add(next);
}
}
}
return cnt == childs.length ? true : false;
}
}
정적 팩터리 메소드와 생성자는 선택적 매개변수가 많을 떄 적절하게 대응하기 어렵다는 단점이 있다.
만약 있을 수도 없을 수도 있는 필드가 많은 객체가 있다고 가정하자.
1. 옛날에는 이러한 클래스에서 점층적 생성자 패턴(telescoping constructor pattern)을 즐겨 사용했다.
이 패턴은 필수 매개변수를 받는 생성자와, 선택 매개변수를 하나씩 늘여가며 생성자를 만드는 패턴이다.
=> 매개변수 개수가 많아지면 클라이언트 코드를 작성하거나 읽기 어렵다
class Person {
private String name; // 필수
private int age; // 필수
private String job; // 선택
private String hobby; // 선택
public Person(String name, int age, String job, String hobby) {
this.name = name;
this.age = age;
this.job = job;
this.hobby = hobby;
}
// 이런 생성자는 사용자가 설정하길 원치 않는 매개변수까지 포함하기 쉬운데,
// 어쩔 수 없이 hobby 매개변수에도 ""라는 값을 지정해줘야 한다.
public Person(String name, int age, String job) {
this(name, age, job, "");
}
public Person(String name, int age) {
this(name, age, "", "");
}
}
코드를 읽을 때 각 값의 의미가 무엇인지 헷갈릴 것이고, 매개변수가 몇 개인지도 주의해서 세어 보아야 한다.
또한 타입이 같은 매개변수가 연달아 늘어서 있으면 찾기 어려운 버그로 이어 질 수 있다.
클라이언트가 실수로 매개변수의 순서를 바꿔 건네줘도 컴파일러 는 알아채지 못하고, 결국 런타임에 엉뚱한 동작을 하게 된다(아이템 51).
2. 위 문제점에 대한 대안으로는 자바빈즈 패턴(JavaBeans pattern)이 있다.
매개변수가 없는 생성자로 객체를 만든 후, 세터(setter) 메서드들을 호출해 원하는 매개변수의 값을 설정하는 방식이다.
@Setter
class Person {
private String name = ""; // 필수
private int age = 0; // 필수
private String job = ""; // 선택
private String hobby = ""; // 선택
public Person() {
}
}
public class DemoApplication {
public static void main(String[] args) {
Person person=new Person();
person.setName("soyeon");
person.setAge(25);
person.setJob("student");
person.setHobby("exercise");
}
}
자바빈즈 패턴의 경우 장점은 코드가 길어지긴 했지만 인스턴스를 만들기 쉽고, 그 결과 더 읽기 쉬운 코드가 되었다는 점이다.
하지만 단점은 객체 하나를 만들기 위해 많은 메서드를 호출해야 하며, 객체가 완전히 생성되기 전까지는 일관성(consistency)이 무너진 상태에 놓이게 된다. => 버그가 존재하는 코드와 그 버그 때문에 런타임에 문제를 겪는 코드가 물리적으로 멀리 떨어져 있을 것이므로 디버깅이 어려워진다.
점층적 생성자 패턴에서는 매개변수들이 유효한지를 생성자에서만 확인하면 일관성을 유지할 수 있었는데, 그 장치가 완전히 사라진 것이다. 이처럼 일관성이 무너지는 문제 때문에 자바빈즈 패턴에서는 클래스를 불변(Item17)으로 만들 수 없으며 스레드 안전성이 없다는 문제도 있다.
3. 마지막 대안은 점층적 생성자 패턴의 안전성과 자바 빈즈 패턴의 가독성을 겸비한 빌더 패턴(Builder pattem)[Gamma95]이다.
클라이언트는 필요한 객체를 직접 만드는 대신, 필수 매개변수만으로 생성자 또는 정적 팩터리 메서드를 호출해 빌더 객체를 얻는다.
클라이언트는 빌더 객체가 제공하는 일종의 세터 메서드들로 원하는 선택 매개변수들을 설정한다.
마지막으로 매개변수가 없는 build 메서드를 호출해 드디어 우리에게 필요한 객체를 얻는다.(이 객체는 일반적으로 불변객체이다.)
빌더는 생성할 클래스 안에 정적 멤버 클래스로 만들어 두도록 한다.
package com.yapp.crew.domain.model;
import javax.persistence.Entity;
import javax.persistence.FetchType;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;
import javax.persistence.JoinColumn;
import javax.persistence.ManyToOne;
import lombok.AccessLevel;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;
@Entity
@Getter
@NoArgsConstructor(access = AccessLevel.PROTECTED)
public class BookMark extends BaseEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
@ManyToOne(fetch = FetchType.LAZY)
@JoinColumn(nullable = false)
@Setter(value = AccessLevel.PRIVATE)
private User user;
@ManyToOne(fetch = FetchType.LAZY)
@JoinColumn(nullable = false)
@Setter(value = AccessLevel.PRIVATE)
private Board board;
public static BookMarkBuilder getBuilder() {
return new BookMarkBuilder();
}
public static class BookMarkBuilder { // 정적 멤버 클래스
private User user;
private Board board;
public BookMarkBuilder withUser(User user) {
this.user = user;
return this;
}
public BookMarkBuilder withBoard(Board board) {
this.board = board;
return this;
}
public BookMark build() {
BookMark bookMark = new BookMark();
bookMark.setUser(user);
bookMark.setBoard(board);
return bookMark;
}
}
}
private void saveBookMark(Board board, User user) {
// 빌더의 세터 메서드들은 빌더 자신을 반환하기 때문에 연쇄적으로 호출 할 수 있다.(method chaining)
BookMarkBuilder bookMarkBuilder = BookMark.getBuilder();
BookMark bookMark = bookMarkBuilder
.withUser(user)
.withBoard(board)
.build();
user.addBookMark(bookMark);
board.addBookMark(bookMark);
bookMarkRepository.save(bookMark);
}
이때, 빌더의 생성자와 메서드에서 입력 매개변수를 검사하고, build 메서드가 호출하는 생성자에서 여러 매개변수에 걸친 불변식 (invariant)을 검사하도록 하면 더 좋다. 공격에 대비해 이런 *불변식을 보장하려면 빌더로부터 매개변수를 복사한 후 해당 객체 필드들도 검사해야 한다(Item50).
검사해서 잘못된 점을 발견하면 어떤 매개변수가 잘못되었는지를 자세히 알려주는 메시지를 담아 IllegalArgumentException을 던지면 된다(Item75).
빌더 패턴은 계충적= 설계된 클래스와 함께 쓰기에 좋다. 각 계층의 클래스에 관련 빌더를 멤버로 정의하자.
추상 클래스는 추상 빌더를, 구체 클래스(concrete class)는 구체 빌더를 갖게 한다.
다음은 피자의 다양한 종류를 표현 하는 계층구조의 루트에 놓인 추상 클래스다.
용어
불변 vs 불변식
불변(immutable, immutability): 어떠한 변경도 허용하지 않는다는 뜻으로, 주로 변경을 허용하는 가변(mutable) 객체와 구분하는 용도로 쓰인다. ex) String 객체
불변식(invariant): 프로그램이 실행되는 동안, 혹은 정해진 기간 동안 반드시 만족해야 하는 조건을 뜻한다. 즉, 변경을 허용할 수는 있으나 주어진 조건 내에서 만 허용한다는 뜻이다.(아이템 50)
ex) 리스트의 크기는 반드시 0 이상 = 만약 한순간 이라도 음수 값이 된다면 불변식이 깨진 것이다.
ex) 기간을 표현하는 Period 클래스에서 start 필드의 값은 반드시 end 필드의 값보다 앞서야 = 두 값이 역전되면 불변식이 깨진 것이다
따라서 가변 객체에도 불변식은 존재할 수 있으며, 넓게 보면 불변은 불변식의 극단적 인 예라 할 수 있다.
public class Person {
private static Person PERSON = new Person();
private Person() { // 외부 생성 금지
}
public static final Person create() { // factory method
return PERSON;
}
}
정적 팩터리 메소드의 장점
1. 이름을 가질 수 있다.
일반 생성자의 경우 매개변수와 생성자 자체 만으로는 반환될 객체의 특성을 제대로 설명하지 못한다.
정적 팩터리 메서드의 경우는 이름을 지으면서 반환될 객체의 특성을 쉽게 묘사할 수 있다.
// BigInteger.probablePrime: 함수 네이밍을 통해 '값이 소수인 Biginteger를 반환한다'는 의미를 잘 전달한다.
public static BigInteger probablePrime(int bitLength, Random rnd) {
if (bitLength < 2)
throw new ArithmeticException("bitLength < 2");
return (bitLength < SMALL_PRIME_THRESHOLD ?
smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
}
또한, 생성자 방식으로 인스턴스를 생성할 경우, 같은 매개변수로는 동일한 생성자를 사용해야하지만
정적 팩터리 메서드는 이름을 가질 수 있으므로 한 클래스에 같은 매개변수의 생성자가 여러개 필요하다면 차이를 잘 드러내는 이름을 지어줌으로써 역할 구분이 가능하다.
2. 호출될 때마다 인스턴스를 새로 생성하지는 않아도 된다.
*불변 클래스는 인스턴스를 미리 만들어 놓거나 새로 생성한 인스턴스를 캐싱하여 재활용함으로써 불필요한 객체 생성을 피할 수 있다.
public final class Boolean implements java.io.Serializable, Comparable<Boolean> {
// static 자원은 JVM 클래스로더의 초기화 부분에서 할당된다.
public static final Boolean TRUE = new Boolean(true);
public static final Boolean FALSE = new Boolean(false);
...
public static Boolean valueOf(boolean b) {
return (b ? TRUE : FALSE);
}
}
같은 객체가 자주 요청되는 상황이고, 이 객체의 생성비용이 크다면 정적팩터리 메소드 방식으로 인스턴스를 생성하도록 한다.
3. 반환 타입의 하위 타입 객체를 반환할 수 있는 능력이 있다. - 인터페이스기반 프레임워크(Item20)의 핵심기술
이 능력은 반환할 객체의 클래스를 자유롭게 선택할 수 있게 한다.
이를 응용하면 구현 클래스를 공개하지 않고도 그 객체를 반환할 수 있어 API를 작게 유지할 수 있다.
interface Person {
}
class Doctor implements Person {
private Doctor() {
} // 외부 생성 금지
public static final Person create() { // 구체적인 타입을 숨길 수 있다
return new Doctor();
}
}
정적 팩터리 메서드를 사용하는 클라이언트는 얻은 객체를 (그 구현 클래스 가 아닌) 인터페이스만으로 다루게 된다(Item64)
4. 입력 매개변수에 따라 매번 다른 클래스의 객체를 반환할 수 있다. (반환 타입의 하위 타입이기만 하면)
정적팩터리 메서드를 사용하면 동적으로 적절한 타입의 객체를 반환할 수 있다.
심지어 다음 릴리스에서는 또 다른 클래스의 객체를 반환해도 된다.
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
// 원소의 수에 따라 두 가지 하위 클래스 중 하나의 인스턴스를 반환
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
if (universe.length <= 64)
return new RegularEnumSet<>(elementType, universe);
else
return new JumboEnumSet<>(elementType, universe);
}
클라이언트는 RegularEnumSet과 JumboEnumSet 클래스의 존재를 모른다.
따라서 RegularEnumSet, JumboEnumSet등을 삭제하거나 다른 클래스들을 추가하더라도 클라이언트는 팩터리가 건네주는 객체가 어느 클래스의 인스턴스인지 모르기 때문에 문제 없다. EnumSet의 하위 클래스이기만 하면 되는 것이다.
5. 정적 팩터리 메서드를 작성하는 시점에는 반환할 객체의 클래스가 존재하지 않아도 된다.
ex) JDBC(Java Database Connectivity): 서비스 제공자 프레임워크에서의 제공자(provider)는 서비스의 구현체다. 그리고 이 구현체들을 클라이언트에 제공하는 역할을 프레임워크가 통제하여 , 클라이언트를 구현체로부터 분리해준다.
서비스 제공자 프레임워크의 컴포넌트 3요소
서비스 인터페이스(service interface): 구현체의 동작을 정의
제공자 등록 API (provider registration API): 제공자가 구현체를 등록할 때 사용
서비스 접근 API (service access API): 클라이언트가 서비스의 인스턴스를 얻을 때 사용
그런데 Class.forName으로 드라이버 이름만 호출했는데 어떻게 DriverManager가 커넥션을 만들어서 리턴할 수 있었을까?
1. Class.forName(String name) 메소드에 의해 문자열로 전달되는 "com.mysql.jdbc.Driver"이라는 클래스가 메모리에 로드 된다.
2. 메모리에 로드되면서 "com.mysql.jdbc.Driver" 클래스의static 절이 실행된다. 아래와 같이 DriverManager.registerDriver() 메소드를 통해 자기 자신을 등록한다. 즉, 이러한 이유로 Class.forName("com.mysql.jdbc.Driver") 실행시 JDBC Driver가 자동 등록된다.
자바5 이후는 java.util.ServiceLoader라는 범용 서비스 제공자 프레임워크가 제공되어 프레임워크를 직접 만들 필요가 거의 없어졌다.(Item59).
JDBC는 자바 5 전에 등장한 개념이므로 ServiceLoader를 사용하지 않고 위와 같이 구현되어 있다.
단점
1. 정적 팩터리 메서드만 제공하면 하위 클래스를 만들 수 없다.
상속을 하려면 public이나 protected 생성자가 필요한데, 정적 팩터리 메서드를 사용하는 경우 private 기본생성자를 통해 외부 생성을 막아두기 때문이다. 따라서 정적 팩터리 메서드를 이용하는 대표적인 클래스인 컬렉션 프레임워크의 유틸리티 구현 클래스들은 상속할 수 없 다.
이 제약은 상속보다 컴포지션을 사용(Item18) 하도록 유도하고 불변 타입으로 만들려면 이 제약을 지켜야 한다는 점에서 오히려 장점이 될 수 있다.
2. 정적 팩터리 메서드는 프로그래머가 찾기 어렵다.
생성자처럼 API 설명에 명확히 드러나지 않으므로 사용자는 정적 팩터리 메서드 방식 클래스를 인스턴스화할 방법을 API 문서를 통해 알아내야 한다.
아래는 정적 팩터리 메서드에서 통용되는 명명 방식이다.
from： 매개변수를 하나 받아서 해당 타입의 인스턴스를 반환하는 형변환 메서드
Date d = Date.from(instant);
of： 여러 매개변수를 받아 적합한 타입의 인스턴스를 반환하는 집계 메서드
Set<Rank> cards = EnumSet.of(JACK, QUEEN, KING);
valueOf： from과 of의 더 자세한 버전
Boolean true = Boolean.valueOf(true);
instance (getlnstance)： (매개변수를 받는다면) 매개변수로 명시한 인스턴스를 반환하지만, 같은 인스턴스임을 보장하지는 않는다.
Calendar calendar = Calendar.getlnstance(zone);
public static Calendar getInstance(TimeZone zone){
return createCalendar(zone, Locale.getDefault(Locale.Category.FORMAT));
}
create (newlnstance)： instance 혹은 getlnstance와 같지만, 매번 새로 운 인스턴스를 생성해 반환함을 보장한다.
방법 1 - 부모 노드에 대한 링크가 있는 경우 => 최대 높이가 d일 때, 공통 조상을 찾는데까지 시간 복잡도 O(d)
1. v1, v2를 루트 노드에서 거리를 구한다.
2. v1, v2를 같은 높이가 될 때까지 한 노드의 높이를 올려준다.
3. v1, v2의 높이를 하나씩 올리면서 겹치는 경우를 찾는다.
class Solution {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int test = in.nextInt();
for (int t = 1; t <= test; t++) {
int n = in.nextInt();
int e = in.nextInt();
int v1 = in.nextInt();
int v2 = in.nextInt();
LinkedList<Integer> childs[] = new LinkedList[n + 1];
for (int i = 1; i <= n; i++) {
childs[i] = new LinkedList<Integer>();
}
int[] parent = new int[n + 1];
for (int i = 0; i < e; i++) {
int p = in.nextInt();
int c = in.nextInt();
childs[p].add(c);
parent[c] = p;
}
int height1 = heightFromRootNode(v1, childs);
int height2 = heightFromRootNode(v2, childs);
int commonNode = findCommonParent(v1, v2, height1, height2, parent);
int subNodes = calculateSubNodes(commonNode, childs);
System.out.println("#" + t + " " + commonNode + " " + subNodes);
}
}
private static int calculateSubNodes(int name, LinkedList<Integer>[] childs) {
int answer = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(name);
while (!queue.isEmpty()) {
int now = queue.poll();
answer++;
queue.addAll(childs[now]);
}
return answer;
}
private static int findCommonParent(int v1, int v2, int height1, int height2, int parent[]) {
// 무조건 height1 <= height2라고 생각 -> v2를 위로 땡긴다.
if (height1 > height2) {
return findCommonParent(v2, v1, height2, height1, parent);
}
while (height1 != height2) {
v2 = parent[v2];
height2--;
}
while (v1 != v2) {
v1 = parent[v1];
v2 = parent[v2];
}
return v1;
}
private static int heightFromRootNode(int name, LinkedList<Integer>[] childs) {
int height = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
while (!queue.isEmpty()) {
int size = queue.size();
height++;
for (int i = 0; i < size; i++) {
int parent = queue.poll();
if (parent == name) {
return height;
}
queue.addAll(childs[parent]);
}
}
return height;
}
}
출발지점부터 distance 사이에 바위를 제거했을 때, 제거한 바위의 최솟값 중에 가장 큰 값을 구하는 문제이다.
이 문제는 바위를 제거하는 모든 경우를 구한 후 최솟값을 구한다면,
바위가 N개, R개를 제거할 수 있다면 O(NCR)로 시간초과가 발생하게 된다.
이러한 경우에는 바위를 제거하는 모든 경우의 수를 구하기보다는,
바위간의 최소 거리를 정해두고 이 조건이 가능한지 여부를 보는 쪽으로 생각하면 된다.
바위간의 최소 거리를 정할 때에는 이분 탐색을 사용하도록 했다. 풀이 방식은 아래와 같다.
1. 이분 탐색으로 최대 사잇값 diff를 정한다.
2. 돌을 n개 지웠을 때 최소 거리가 diff인지 확인한다.
=> 즉, 돌 사이의 거리가 diff보다 작으면 돌을 없애고,
최종적으로 없애야 하는 돌의 수가 n보다 크면 diff를 너무 크게 잡은 것이므로 왼쪽을 탐색하도록 한다.
class Solution {
public int solution(int distance, int[] rocks, int n) {
int length = rocks.length;
int start = 0;
int end = distance;
int answer = 0;
Arrays.sort(rocks);
while (start <= end) {
int mid = (start + end) / 2;
if (!isPossible(rocks, n, length, mid, distance)) {
// diff가 너무 크니까 줄이자
end = mid - 1;
} else { // 가능하니까 일단 answer에 저장하고 더 늘려보자
answer = Math.max(answer, mid);
start = mid + 1;
}
}
return answer;
}
public boolean isPossible(int[] rocks, int n, int length, int diff, int distance) {
int remove = 0;
int before = 0;
for (int i = 0; i < length; i++) {
if (rocks[i] - before < diff) { // diff보다 작으니 돌을 없애자
remove++;
} else {
before = rocks[i];
}
if (remove > n) { // 돌을 n개보다 더 없애야 하는 경우
return false;
}
}
if (distance - before < diff) {
remove++;
}
return remove <= n;
}
}
배열의 (1, 1)~(n, n)까지 이동할 때, 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 문제이다.
배열에서 이동하는 모든 경우를 완전탐색 할 경우 O(4^N)이 걸릴 것이다.
이런 경우 최댓값과 최솟값을 차이를 무작정 구하는 방법 보다는,
최댓값과 최솟값을 차이를 정해두고 가능한지 여부를 보는 방법이 더 쉬울 수 있다.
1차 시도 - 이분탐색을 사용하자
처음 생각한 문제 풀이 과정은 아래와 같다.
1. 이진 탐색으로 최대-최소 차이를 정한다.
2. (1, 1) -> (n, n)로 차이 내에 갈 수 있는지 bfs로 탐색한다.
이 경우에는 차이를 구하더라도 이에 맞는 쌍을 구해야 하는데,
이때 해당하는 쌍을 구할 때 이중for문을 사용하기보다는 두 포인터를 이용하여 시간을 줄이도록 했다.
import java.util.*;
public class Main {
public static int dr[] = { 0, 0, 1, -1 };
public static int dc[] = { 1, -1, 0, 0 };
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int mat[][] = new int[n][n];
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] = in.nextInt();
set.add(mat[i][j]);
}
}
int[] numbers = set.stream().mapToInt(i -> i).toArray();
System.out.println(findDifference(numbers, mat, n));
}
private static int findDifference(int[] numbers, int[][] mat, int n) { // 이분탐색
int length = numbers.length;
int start = 0;
int end = numbers[length - 1] - numbers[0];
int answer = Integer.MAX_VALUE;
while (start <= end) {
int mid = (start + end) / 2;
if (findMaxMinFromDifference(mat, numbers, mid, n)) {
answer = mid; // 경로가 존재하니까 일단 저장
end = mid - 1; // 더 줄여보자
} else {
start = mid + 1;
}
}
return answer;
}
private static boolean findMaxMinFromDifference(int mat[][], int[] numbers, int diff, int n) { // 투 포인터
int length = numbers.length;
int start = 0;
int end = 0;
while (start < length && end < length) {
if (numbers[end] - numbers[start] > diff) {
start++;
} else {
if (bfs(mat, numbers[end], numbers[start], n)) {
return true;
}
end++;
}
}
return false;
}
// 최댓값과 최솟값의 차이가 min 보다 클 경우 false 리턴
public static boolean bfs(int[][] mat, int max, int min, int n) { // bfs
if (!isValuePossible(mat[0][0], max, min)) {
return false;
}
Queue<Route> queue = new LinkedList<Route>();
queue.add(new Route(0, 0));
boolean[][] isVisited = new boolean[n][n];
isVisited[0][0] = true;
while (!queue.isEmpty()) {
Route route = queue.poll();
if (route.row == n - 1 && route.col == n - 1) {
return true;
}
for (int i = 0; i < 4; i++) {
int newRow = route.row + dr[i];
int newCol = route.col + dc[i];
if (isBoundary(newRow, newCol, n) && !isVisited[newRow][newCol]
&& isValuePossible(mat[newRow][newCol], max, min)) {
Route newRoute = new Route(newRow, newCol);
isVisited[newRow][newCol] = true;
queue.add(newRoute);
}
}
}
return false;
}
public static boolean isValuePossible(int value, int max, int min) {
if (value < min) {
return false;
}
if (value > max) {
return false;
}
return true;
}
public static boolean isBoundary(int row, int col, int n) {
if (row < 0) {
return false;
}
if (row >= n) {
return false;
}
if (col < 0) {
return false;
}
if (col >= n) {
return false;
}
return true;
}
}
class Route {
int row;
int col;
public Route(int row, int col) {
this.row = row;
this.col = col;
}
}
생각해보니 굳이 이분탐색으로 범위를 줄여서 또 두 포인터로 각각 최대/최소 원소를 구하는 것은 연산이 중복되는 느낌이 들었다..ㅋㅋㅋ
따라서 이분탐색 부분은 제외하고 두 포인터와 bfs를 이용한 풀이로 다시 고쳐보았다.
추가적으로 isVisited의 경우 함수 내에서 계속 새로 할당할 경우 시간이 더 걸릴 수 있으므로 재사용하는 부분을 추가했다.
import java.util.*;
public class Main {
public static int dr[] = { 0, 0, 1, -1 };
public static int dc[] = { 1, -1, 0, 0 };
public static boolean isVisited[][];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int mat[][] = new int[n][n];
isVisited = new boolean[n][n];
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] = in.nextInt();
set.add(mat[i][j]);
}
}
int[] numbers = set.stream().mapToInt(i -> i).toArray();
System.out.println(findMaxMin(mat, numbers, n));
}
private static int findMaxMin(int mat[][], int[] numbers, int n) { // 투 포인터로 max, min 정하기
int length = numbers.length;
int start = 0;
int end = 0;
int answer = Integer.MAX_VALUE;
while (start < length && end < length) {
int diff = numbers[end] - numbers[start];
if (bfs(mat, numbers[end], numbers[start], n)) {
answer = Math.min(answer, diff); // 가능한 경로이므로 일단 저장
start++; // 더 줄여보자
} else {
end++; // 불가능한 경로이므로 diff 범위를 늘리자
}
}
return answer;
}
public static boolean bfs(int[][] mat, int max, int min, int n) { // bfs 가능한 경로 탐색
if (!isPossible(0, 0, n, max, min, mat)) {
return false;
}
clearMatrix(isVisited, n);
Queue<Route> queue = new LinkedList<Route>();
queue.add(new Route(0, 0));
isVisited[0][0] = true;
while (!queue.isEmpty()) {
Route route = queue.poll();
if (route.row == n - 1 && route.col == n - 1) {
return true;
}
for (int i = 0; i < 4; i++) {
int newRow = route.row + dr[i];
int newCol = route.col + dc[i];
if (isPossible(newRow, newCol, n, max, min, mat) && !isVisited[newRow][newCol]) {
Route newRoute = new Route(newRow, newCol);
isVisited[newRow][newCol] = true;
queue.add(newRoute);
}
}
}
return false;
}
public static void clearMatrix(boolean[][] isVisited, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
isVisited[i][j] = false;
}
}
}
public static boolean isPossible(int row, int col, int n, int max, int min, int[][] mat) {
// 바운더리 안에 존재하며, [min, max]인 값임을 확인
if (row < 0) {
return false;
}
if (row >= n) {
return false;
}
if (col < 0) {
return false;
}
if (col >= n) {
return false;
}
if (mat[row][col] < min) {
return false;
}
if (mat[row][col] > max) {
return false;
}
return true;
}
}
class Route {
int row;
int col;
public Route(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "(" + row + ", " + col + ")";
}
}
