정적 팩토리 메서드와 public 생성자 모두 제약이 있다. 바로 선택적 매개변수가 많을 때 적절히 대응하기 어렵다는 점이다.

이 때 개발자들은 점층적 생성자 패턴을 사용했었다. 하지만 이것도 단점이 존재한다.

점층적 생성자 패턴도 쓸 수는 있지만, 배개변수 개수가 많아지면 클라이언트 코드를 작성하거나 읽기 어렵다.

 

점층적 생성자 패턴의 예시 : 

public class Pizza {
    private int size; // 필수
    private boolean cheese; // 선택적
    private boolean pepperoni; // 선택적
    private boolean bacon; // 선택적

    public Pizza(int size) {
        this(size, false); // 기본값 사용
    }

    public Pizza(int size, boolean cheese) {
        this(size, cheese, false); // 기본값 사용
    }

    public Pizza(int size, boolean cheese, boolean pepperoni) {
        this(size, cheese, pepperoni, false); // 기본값 사용
    }

    public Pizza(int size, boolean cheese, boolean pepperoni, boolean bacon) {
        this.size = size;
        this.cheese = cheese;
        this.pepperoni = pepperoni;
        this.bacon = bacon;
    }

    // Pizza 객체 사용 예
    Pizza pizza = new Pizza(12, true, true); // 크기 12, 치즈와 페페로니 추가
    Pizza cheesePizza = new Pizza(12, true); // 크기 12, 치즈 추가
    Pizza everythingPizza = new Pizza(16, true, true, true); // 크기 16, 모두 추가


}

 

지금은 4개 뿐이라서 이게 뭐가 단점이야? 라고 생각할 수 있지만 지금은 '고작' 4개인것 뿐이다.

이를 보완하기 위해 빌더 패턴을 사용한다.

빌더 패턴(Builder Pattern)은 복잡한 객체의 생성 과정을 단순화하는 디자인 패턴이다. 특히, 생성자나 정적 팩토리가 처리해야 할 매개변수가 많을 때 유용하다. 빌더 패턴은 필수 매개변수만으로 생성자를 호출하여 빌더 객체를 얻고, 빌더 객체가 제공하는 설정 메서드를 호출하여 선택적 매개변수를 설정한 다음, 마지막에는 build() 메서드를 호출하여 필요한 객체를 얻는다.

빌더패턴의 장점이 여러가지 있다.

1. 가독성 향상

2. 사용의 유연성

3. 불변성 유지

4. 객채 생성 코드의 재사용성

 

빌더 패턴의 예시 : 

public class Pizza {
    private final int size; // 불변 필드 선언으로 객체의 불변성을 유지
    private final boolean cheese;
    private final boolean pepperoni;
    private final boolean bacon;

    private Pizza(Builder builder) {
        this.size = builder.size; // Builder에서 설정된 값으로 초기화
        this.cheese = builder.cheese;
        this.pepperoni = builder.pepperoni;
        this.bacon = builder.bacon;
    }

    public static class Builder {
        private final int size; // 필수 매개변수
        private boolean cheese = false; // 선택적 매개변수는 기본값으로 초기화
        private boolean pepperoni = false;
        private boolean bacon = false;

        public Builder(int size) {
            this.size = size; // 필수 매개변수 설정
        }

        // 선택적 매개변수 설정 메서드는 체이닝을 통해 가독성과 사용의 유연성을 향상
        public Builder cheese(boolean value) {
            this.cheese = value;
            return this; // 메서드 체이닝을 가능하게 함
        }

        public Builder pepperoni(boolean value) {
            this.pepperoni = value;
            return this;
        }

        public Builder bacon(boolean value) {
            this.bacon = value;
            return this;
        }

        public Pizza build() {
            return new Pizza(this); // 최종 객체 생성 후 반환
        }
    }

    // Pizza 객체 사용 예
    public static void main(String[] args) {
        // 첫 번째 예시: 크기가 12인 치즈 피자
        // 가독성 향상: 각 설정 메서드의 이름을 통해 어떤 매개변수를 설정하는지 명확히 알 수 있음
        Pizza cheesePizza = new Pizza.Builder(12).cheese(true).build();

        // 두 번째 예시: 크기가 16인, 치즈, 페페로니, 베이컨이 모두 추가된 피자
        // 객체 생성 코드의 재사용성: Builder 객체를 통해 비슷한 객체를 생성할 때 설정 코드를 재사용할 수 있음
        Pizza everythingPizza = new Pizza.Builder(16)
                                .cheese(true)
                                .pepperoni(true)
                                .bacon(true)
                                .build();

        // 여기에서 cheesePizza와 everythingPizza 객체를 사용할 수 있습니다.
    }
}

 

 

빌더패턴은 계층적으로 설계된 클래스 구조(상속 구조) 에서 특히 유용하다.

상속 주고에서 사용되는 빌더 패턴의 예 : 

public abstract class Pizza {
    public enum Topping { HAM, MUSHROOM, ONION, PEPPER, SAUSAGE }
    final Set<Topping> toppings; // 피자의 토핑을 저장하는 컬렉션

    abstract static class Builder<T extends Builder<T>> {
        EnumSet<Topping> toppings = EnumSet.noneOf(Topping.class); // 초기 토핑은 비어있음

        // 토핑을 추가하는 메서드, 자기 자신을 반환하여 체이닝을 가능하게 함
        public T addTopping(Topping topping) {
            toppings.add(Objects.requireNonNull(topping));
            return self();
        }

        // 최종적으로 Pizza 객체를 생성하는 메서드, 하위 클래스에서 구현해야 함
        abstract Pizza build();

        // 하위 클래스에서 이 메서드를 오버라이드하여 "this"를 반환하도록 함. 체이닝을 위해 사용됨.
        protected abstract T self();
    }

    // Builder를 사용하여 Pizza 객체를 생성하는 생성자
    Pizza(Builder<?> builder) {
        toppings = builder.toppings.clone(); // Item 50 참고, toppings 복제
    }
}

// 마르게리타 피자 클래스, Pizza 클래스를 상속받음
class MargheritaPizza extends Pizza {
    MargheritaPizza(Builder builder) {
        super(builder); // 상위 클래스의 생성자 호출
    }

    // 마르게리타 피자를 위한 Builder 정적 내부 클래스, Pizza.Builder를 상속받음
    static class Builder extends Pizza.Builder<Builder> {
        @Override
        MargheritaPizza build() {
            return new MargheritaPizza(this); // MargheritaPizza 객체 생성
        }

        @Override
        protected Builder self() {
            return this; // 체이닝을 위해 Builder 인스턴스 자신을 반환
        }
    }
}

 

결론 : 생성자나 정적 팩토리 메서드에서 처리해야 할 매개변수가 많다면 빌더 패턴을 선택하는게 낫다. API는 시간이 지날수록 매개변수가 많아지는 경향이 있기 때문에 매개변수가 적어도 처음부터 빌더 패턴으로 시작하자.

인스턴스 : 클래스(설계도)를 바탕으로 만들어진 구체적인 객체

public 생성자 : 클래스의 인스턴스를 생성할 때 초기화를 담당하는 특별한 메서드

public class Car {
    private String color; // Car 클래스의 필드

    // Car 클래스의 public 생성자
    public Car(String color) {
        this.color = color; // 생성자를 통해 Car 인스턴스의 색상을 초기화
    }
    
    // Car 클래스의 메서드
    public void drive() {
        System.out.println(color + " 차가 달립니다.");
    }
}

// Main 클래스에서 Car 클래스의 인스턴스 생성 및 사용
public class Main {
    public static void main(String[] args) {
        Car myCar = new Car("빨간색"); // Car 클래스의 인스턴스를 생성
        myCar.drive(); // "빨간색 차가 달립니다." 출력
    }
}

위 예시에서 Car 클래스에는 색상(color)를 초기화하는 public 생성자가 있다. Main 클래스에서는 이 생성자를 사용해 Car 클래스의 인스턴스를 생성하고, drive 메서드를 호출한다. 이처럼 public 생성자를 통해 클래스 외부에서 인스턴스를 쉽게 생성하고 사용가능하다.

 

정적 팩토리 메서드는 클래스의 인스턴스를 반환하게하는 정적 메서드이다. 이 방법은 클래스의 인스턴스를 생성하고 반환하기 위한 'new' 키워드를 직접사용하지않고, 클래스 내부에 정의된 특정 메서드를 통해 객체의 인스턴스를 얻는 방식이다.

 

정적 팩토리 메서드의 예시 : 

public class Boolean {
    public static Boolean valueOf(boolean b) {
        return (b ? TRUE : FALSE);
    }
}

 

같은 코드를 public 생성자로 사용했을 때 : 

public class Boolean {
    private boolean value;

    // Public 생성자
    public Boolean(String s) {
        this.value = Boolean.parseBoolean(s);
    }

    // valueOf 메서드 대신 사용하는 생성자
    // Boolean myBool = new Boolean("true");

    // 나머지 클래스 구현
}

 

 

정적 팩토리 메서드의 장점 5가지 : 

1. 이름을 가질 수 있다.

2. 호출될 때 마다 인스턴스를 새로 생성하지는 않아도 된다.

3. 반환 타입의 하위 타입 객체를 반환할 수 있다.

4. 입력 매개변수에 따라 매번 다른 클래스의 객체를 반환할 수 있다.

5. 정적 팩토리 메서드를 작성하는 시점에는 반환할 객체의 클래스가 존재하지 않아도 된다.

이 모든 장점을 하나의 코드안에 담아보았다 : 

public class VehicleFactory {

    private static final Map<String, Vehicle> cache = new HashMap<>();

    // 1. 이름을 가질 수 있음: 메서드 이름을 통해 반환되는 객체의 의도를 명확히 할 수 있습니다.
    public static Vehicle createElectricCar() {
        return new ElectricCar();
    }

    // 2. 호출될 때마다 인스턴스를 새로 생성하지 않아도 됨: 인스턴스 캐싱을 통해 불필요한 객체 생성을 방지합니다.
    public static Vehicle getBicycleInstance() {
        // 캐시에서 인스턴스를 검색, 없으면 생성하여 캐시에 추가
        return cache.computeIfAbsent("bicycle", k -> new Bicycle());
    }

    // 3. 반환 타입의 하위 타입 객체를 반환할 수 있음: 인터페이스 Vehicle의 하위 타입 반환
    public static Vehicle createVehicle(String type) {
        switch (type) {
            case "electric":
                return new ElectricCar();
            case "bicycle":
                return new Bicycle();
            default:
                throw new IllegalArgumentException("Unknown vehicle type");
        }
    }

    // 4. 입력 매개변수에 따라 다른 클래스의 객체를 반환할 수 있음: createVehicle 메서드 참조
    // (위에서 이미 설명함)

    // 5. 정적 팩토리 메서드를 작성하는 시점에는 반환할 객체의 클래스가 존재하지 않아도 됨:
    // 이 예시에서는 ElectricCar와 Bicycle 클래스가 이 메서드들을 사용하는 클라이언트 코드보다 나중에 작성될 수 있습니다.

    private interface Vehicle {
    }

    private static class ElectricCar implements Vehicle {
    }

    private static class Bicycle implements Vehicle {
    }
}

 

정적 팩토리 메서드의 단점도 존재한다.

1. 상속을 하려면 public 이나 protected 생성자가 필요하니 정적 팩토리 메서드만 제공하면 하위 클래스를 만들 수 없다.

2. 정적 팩토리 메서드는 프로그래머가 찾기 어렵다.

2번 단점을 보완할 수 있는 방법이있다. 바로 널리 알려진 규약을 따라 메서드 이름을 짓는것이다.

대표적인 명명방식들이 있다. 예를 들면 : 

 

  1. valueOf - 주어진 매개변수를 가지고 해당 타입의 인스턴스를 반환합니다. 주로, 기본 데이터 타입의 래퍼 클래스에서 많이 볼 수 있습니다.
    • 예: Integer.valueOf(int i)
  2. of - valueOf와 유사하지만, 더 간결한 버전으로 사용됩니다.
    • 예: List.of("a", "b", "c"), EnumSet.of(ChronoField.DAY_OF_WEEK)
  3. getInstance - 인스턴스를 가져오되, 같은 인스턴스임을 보장하지 않습니다. 싱글턴 패턴이나 인스턴스 캐싱 시 사용될 수 있습니다.
    • 예: Calendar.getInstance()
  4. getSingleton - getInstance와 유사하지만, 항상 같은 인스턴스를 반환함을 보장합니다. 주로 싱글턴 패턴 구현에 사용됩니다.
    • 예: Runtime.getRuntime()
  5. newInstance - getInstance와 유사하지만, 매번 새로운 인스턴스를 생성해 반환합니다. 반복 사용 시 다른 인스턴스를 기대할 때 사용합니다.
    • 예: Array.newInstance(Class<?> componentType, int length)
  6. getType - getInstance와 유사하지만, 반환되는 인스턴스의 타입이나 클래스에 더 집중할 때 사용됩니다.
    • 예: Files.getFileStore(Path path)
  7. newType - newInstance와 유사하지만, 새로운 인스턴스를 생성할 때 사용되며, 생성되는 인스턴스의 타입을 더 명확히 하고자 할 때 사용됩니다.
    • 예: Collections.newSetFromMap(Map<E, Boolean> map)

 

종합 : 정적 팩토리 메서드와 public 생성자는 각자 쓰임새가 있지만 정적 팩토리 메서드를 사용하는게 유리한 경우가 더 많으므로 정적팩토리 멕서드사용을 지향하자.

https://www.acmicpc.net/problem/9372

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            for (int j = 0; j < M; j++) {
                st = new StringTokenizer(br.readLine(), " ");
            }
            System.out.println(N - 1);
        }
    }
}

 

[설명]

문제를 풀면서 뭔가 좀 이상함을 느꼈었다. 문제가 이해하기 어렵게 적혀있지만 결국에는 노드와 간선의 관계를 물어보는 문제였다. 노드가 N개 있고 노드끼리 모드 연결되어있게하려면 간선은 최소 N - 1개 있어야한다는걸 알고있냐는 질문이였다. 비행기를 타는 최소 횟수 같은걸 물어보는거였다면 문제를 다르게 풀어야 했겠지만 그냥 비행기의 종류가 몇개냐는 물어보는거였기 때문에 정답 코드가 이렇다.

'코딩테스트' 카테고리의 다른 글

백준 2493번: 탑[JAVA]  (0) 2024.03.12
백준 7682번: 틱택토[JAVA]  (0) 2024.03.11
백준 2668번: 숫자고르기[JAVA]  (0) 2024.03.07
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.07
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.05

https://www.acmicpc.net/problem/2668

 

2668번: 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절

www.acmicpc.net

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    static int n, num;
    static int[] arr;
    static boolean[] check;
    static List<Integer> answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        check = new boolean[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine()) - 1;
        }
        answer = new LinkedList<>(); // 답은 가변적이므로 리스트로 선언

        for (int i = 0; i < N; i++) {
            check[i] = true;
            num = i;
            dfs(i);
            check[i] = false;
        }
        Collections.sort(answer);
        System.out.println(answer.size());
        for (Integer integer : answer) {
            System.out.println(integer + 1);
        }
    }

    public static void dfs(int i) {
        if (arr[i] == num) { // 한바퀴돌아 다시 제자리로 돌아오는지 체크
            answer.add(num); // 돌아온다면 정답에 추가
        }
        if (!check[arr[i]]) {
            check[arr[i]] = true;
            dfs(arr[i]);
            check[arr[i]] = false;
        }
    }
}

 

[설명]

난이도가 높아질수록 문제를 이해하는것 자체부터가 힘들어진다. for문을 N번 만큼 돌면서 dfs 로직을 실행시켜준다.

dfs로직은 출발 숫자 -> arr[출발 숫자] -> arr[arr[출발 숫자]] 를 반복하다 출발 숫자를 다시 만나게 되면 첫째 줄과 둘째 줄 정수들의 집합이 일치한다고 볼 수 있다. 

for문을 N번 만큼 실행시키는 이유는 최대값을 찾기 위해서이다.

 

'코딩테스트' 카테고리의 다른 글

백준 7682번: 틱택토[JAVA]  (0) 2024.03.11
백준 9372번: 상근이의 여행[JAVA]  (0) 2024.03.09
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.07
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.05
백준 14719번: 빗물[JAVA]  (0) 2024.03.05

https://www.acmicpc.net/problem/2467

 

2467번: 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -

www.acmicpc.net

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = N - 1;
        int min = Integer.MAX_VALUE; // 현재 알고있는 최솟값
        int[] answer = new int[2];
        while (left < right) {
            int sum = Math.abs(arr[left] + arr[right]); // 새로운 최솟값
            if (sum < min) { // 새로운 최솟값이 원래 알고있는 최솟값보다 더 작다면 갱신
                min = sum;
                answer[0] = arr[left];
                answer[1] = arr[right];
            }
            if (sum == 0) {
                break;
            }
            if (arr[left] + arr[right] > 0) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(answer[0] + " " + answer[1]);
    }
}

 

[설명]

간단한 이분탐색 알고리즘 문제이다. 다른 이분탐색 알고리즘과 다른점은 left 와 right 가 arr배열의 인덱스 내에서만 이루어져야만 한다는것을 조심해야한다.

left는 0 (첫번째 인덱스), right는 N - 1 (마지막 인덱스)로 초기화하고 left가 right를 넘어갈때 까지 반복한다.

left 와 right를 더한 값이 0 이상일 경우 right-- 아닐 경우 left ++ 한다.

혹은 0 일경우 바로 출력한다.

https://www.acmicpc.net/problem/5972

 

5972번: 택배 배송

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는

www.acmicpc.net

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static int N, M;
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<>(); // 2차원 ArrayList 로 graph 를 구현(2차원 배열처럼)
    public static boolean[] visited;
    public static int[] d = new int[50001];
    public static int answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N];

        //ArrayList 초기화
        for(int i=0;i<=N;i++) {
            graph.add(new ArrayList<>());
        }

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); // 시작 노드
            int b = Integer.parseInt(st.nextToken()); // 끝 노드
            int dist = Integer.parseInt(st.nextToken()); // 비용

            // 양방향 간선
            graph.get(a).add(new Node(b, dist)); // a 에서 b 까지의 가중치 dist
            graph.get(b).add(new Node(a, dist)); // b 에서 a 까지의 가중치 dist
        }

        //1부터 N 까지의 최소거리 구하기
        dijkstra(1);

        System.out.println(d[N]);
    }

    public static void dijkstra(int start) {
        Arrays.fill(d, Integer.MAX_VALUE); // d 배열의 모든 요소를 Integer.MAX_VALUE 로 채워줌

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0)); // 시작노드에서 시작노드로 가기위한 최단 경로는 0
        d[start] = 0; // 시작노드에서 시작노드까지의 가중치는 제자리 이므로 0

        while (!pq.isEmpty()) {
            Node temp = pq.poll();
            int nodeB = temp.nodeB; // 현재 노드번호
            int distance = temp.distance; // 현재 노드의 가중치

            if(d[nodeB] < distance) continue; // //현재 노드가 이미 처리된적이 있는 노드라면 무시 ( 거리가 더 작다는것은 이미 더 효율적인 방안으로 처리된 것 )
            for(int i=0;i<graph.get(nodeB).size();i++) { //현재 노드와 연결된 다른 인접한 노드들을 확인
                int cost = d[nodeB] + graph.get(nodeB).get(i).distance; // cost = 현재노드의 가중치 + 현재노드와 다음 노드까지의 간선의 가중치
                if( cost < d[graph.get(nodeB).get(i).nodeB]) { // 새롭게 측정한 비용이 다음 노드가 원래 가지고 있던 가중치보다 적을 경우
                    d[graph.get(nodeB).get(i).nodeB] = cost; // 더 적은 값으로 갱신해준다
                    pq.offer(new Node( graph.get(nodeB).get(i).nodeB, cost)); // 계속 탐색을 해봐야 모든 노드들의 최솟값을 알 수 있기 때문에 현재의 가중치를 가지고 계속 탐색
                }
            }
        }
    }

}


// 그래프의 간선을 표현하기 위한 클래스
class Node implements Comparable<Node>{
    int nodeB; // 이 간선이 연결하는 목적지 노드의 번호
    int distance; // 시작노드에서 nodeB 까지의 가중치
    public Node(int nodeB, int distance) {
        this.nodeB = nodeB;
        this.distance = distance;
    }

    // Node 인스턴스 끼리 비교할 때 사용
    // 우선순위 큐에 삽입되었을 때 distance 값이 작은 노드(가장 가까운 노드) 부터 우선순위가 높게 설정되어 먼저 처리된다
    @Override
    public int compareTo(Node other) {
        if(this.distance > other.distance) {
            return 1;
        }else if(this.distance == other.distance) {
            return 0;
        }else {
            return -1;
        }
    }
}

 

[설명]

이 문제는 다익스트라 알고리즘을 활용해 푸는 기본적인 문제이다. 코드는 다른사람의 코드를 참고했다. 

graph 를 이중 ArrayList로 선언해주고 노드끼리의 가중치를 초기화 해준다. 

graph는 이런형태로 값이 저장된다. 

코드에 주석을 자세히 달아 놨으므로 코드와 주석을 동시에 보면서 확인하면 이해가 쉽다.

'코딩테스트' 카테고리의 다른 글

백준 2668번: 숫자고르기[JAVA]  (0) 2024.03.07
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.07
백준 14719번: 빗물[JAVA]  (0) 2024.03.05
백준 14940번: 쉬운 최단거리[JAVA]  (1) 2024.02.29
백준 1072번: 게임[JAVA]  (0) 2024.02.15

https://www.acmicpc.net/problem/14719

 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

 

 

[정답 코드]

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int[] arr = new int[W];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < W; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;

        for (int i = 1; i < W - 1; i++) { // 처음벽과 마지막벽에는 물이 고일수 없다
            int current = arr[i]; // 현재 벽의 높이
            int leftMax = current; // 왼쪽 벽
            int rightMax = current; // 오른쪽 벽
            for (int j = i - 1; j >= 0; j--) { // 왼쪽 벽 최대 높이 탐색
                if (arr[j] > current) {
                    leftMax = Math.max(leftMax, arr[j]);
                }
            }
            for (int j = i + 1; j < W; j++) { // 오른쪽 벽 최대 높이 탐색
                if (arr[j] > current) {
                    rightMax = Math.max(rightMax, arr[j]);
                }
            }
            if (Math.min(leftMax, rightMax) > current) { // 현재 벽보다 높은 벽이 양쪽에 있는 경우
                answer += (Math.min(leftMax, rightMax) - arr[i]);
            }
        }
        System.out.println(answer);
    }
}

 

[설명]

처음에는 구현문제가 쉬운 문제인줄 알았는데 풀면 풀 수록 구현 문제도 어렵다는걸 깨달았다. 이 문제는 다른 블로그들을 대부분 참고했다.

문제 풀이방법은 for문을 돌며 현재 벽 기준으로 왼쪽 벽 중 가장 높은벽과 가장 높은 오른쪽 벽을 구한 후, 그 벽들이 현재 벽보다 높을 경우 빗물이 고이기 때문에 높은 벽에서 현재 벽을 빼주면 그 차이 만큼 빗물이 쌓인다.

이때 문제의 핵심은 두가지가 있다.

1. 가장 왼쪽벽과 가장 오른쪽 벽에는 빗물이 고일 수 없다.

그래서 for문을 돌릴때 i = 1부터 시작되고 끝은 W - 1까지 한다. 

2. 현재 벽보다 높은 양쪽 벽중에 더 낮은 벽 기준으로 빗물이 고인다.

예를 들면 빨간 체크한 벽이 for문에서 현재 current 라고 했을 때, 왼쪽벽 중 가장 높은벽은 4 이고 오른쪽벽 중  가장 높은 벽은 2이다. 이때 그림으로 보면 알 수 있듯이 왼쪽벽을 기준으로 계산하는게 아닌 오른쪽 벽을 기준으로 계산해야 한다.

'코딩테스트' 카테고리의 다른 글

백준 5972번: 택배 배송[JAVA]  (0) 2024.03.07
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.05
백준 14940번: 쉬운 최단거리[JAVA]  (1) 2024.02.29
백준 1072번: 게임[JAVA]  (0) 2024.02.15
백준 1920번: 수 찾기[JAVA]  (0) 2024.02.14

https://www.acmicpc.net/problem/14940

 

14940번: 쉬운 최단거리

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이

www.acmicpc.net

 

[정답코드]

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int[][] result;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0}; // 상,하,좌,우
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m];
        result = new int[n][m];
        int x=0, y=0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 2) {
                    x = i;
                    y = j;
                } else if (graph[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }
        bfs(x, y);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    result[i][j] = -1;
                }
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        result[nx][ny] = result[tmp[0]][tmp[1]] + 1;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

 

[설명]

bfs를 활용해야하는 문제이다. 시작지점의 위치를 입력받고 입력받은 위치를 큐에 넣고 bfs로직을 돌려준다.

bfs로직은 입력받은 x, y 를 큐에 넣고  해당 위치를 기준으로 4방탐색을 한다. 4방탐색을 했을 때 방문하지않은장소이고, 갈 수 있는 장소이고, 지도 내에 있다면 visited를 true로 변경해주고, 새로 탐색한 위치의 값을 이동할 때 마다 1씩 증가시켜준다. 그리고 새로탐색한 위치를 큐에 넣어준다.

'코딩테스트' 카테고리의 다른 글

백준 5972번: 택배 배송[JAVA]  (0) 2024.03.05
백준 14719번: 빗물[JAVA]  (0) 2024.03.05
백준 1072번: 게임[JAVA]  (0) 2024.02.15
백준 1920번: 수 찾기[JAVA]  (0) 2024.02.14
백준 2512번: 예산[JAVA]  (1) 2024.02.13

+ Recent posts