자바가 제공하는 다중 구현 메커니즘은 인터페이스와 추상 클래스 두가지이다. 둘의 가장 큰 차이는
추상 클래스가 정의한 타입을 구현하는 클래스는 반드시 추상 클래스의 하위 클래스가 되어야 한다는 점이다. 자바는 단일 상속만 지원하니, 추상 클래스 방식은 새로운 타입을 정의하는데 큰 제약을 안게되는 셈이다.
반면 인터페이스가 선언한 메서드를 모두 정의하고 그 일반 규약을 잘 지킨 클래스라면 다른 어떤 클래스를 상속했든 같은 타입으로 취급된다.
다중 구현 메커니즘 : 한 클래스가 둘 이상의 인터페이스를 구현할 수 있는 기능
인터페이스의 장점 :
- 인터페이스는 기존 클래스에도 손쉽게 새로운 인터페이스를 구현해 넣을 수 있다.
- 인터페이스로는 계층구조가 없는 타입 프레임워크를 만들 수 있다.
- 인터페이스는 기능을 향상시키는 안전하고 강력한 수단이 된다.
결론 : 일반적으로 다중 구현용 타입으로는 인터페이스가 가장 적합하다. 복잡한 인터페이스라면 구현하는 수고를 덜어주는 골격 구현을 함께 제공하는 방법이 좋다. 골격 구현은 가능한 한 인터페이스의 디폴트 메서드로 제공하여 그 인터페이스를 구현한 모든곳에서 활용하도록 하는 것이 좋다. 가능한 한 이라고 한 이유는, 인터페이스에 걸려 있는 구현상의 제약 때문에 골격 구현을 추상 클래스로 제공하는 경우가 더 흔하기 때문이다.
메서드를 재정의하면 어떤 일이 일어나는지를 정확히 정리하여 문서로 남겨야 한다. 상속용 클래스는 재정의할 수 있는 메서드들을 내부적으로 어떻게 이용하는지(자기 사용 패턴) 문서로 남겨야 한다.
자기 사용 패턴 : 클래스 내부의 한 메서드가 같은 클래스의 다른 메서드를 호출하는 패턴. 자기 사용 패턴이 상속과 결합될 때 문제가 발생할 수 있다. 슈퍼클래스가 자신의 메서드를 호출할 때 실제로 실행되는 메서드가 서브클래스에서 오버라이드된 메서드일 수 있다.
아래는 API 문서의 메서드 설명 예시이다.
설명 끝 부분에 "Implementation Requirements"로 시작되는 부분은 그 메서드의 내부 동작 방식을 설명하는 곳이다.
public boolean remove(Object o)
주어진 원소가 이 컬렉션 안에 있다면 그 인스턴스를 하나 제거한다(선택적 동작). 더 정확
하게 말하면, 이 컬렉션 안에 'Object.equals(o, e)가 참인 원소' e가 하나 이상 있다면 그
중 하나를 제거한다. 주어진 원소가 컬렉션 안에 있었다면(즉, 호출 결과 이 컬렉션이 변경
됐다면) true를 반환한다.
Implementation Requirements: 이 메서드는 컬렉션을 순회하며 주어진 원소를 찾도록
구현되었다. 주어진 원소를 찾으면 반복자의 remove 메서드를 사용해 컬렉션에서 제거한다.
이 컬렉션이 주어진 객체를 갖고 있으나, 이 컬렉션의 iterator 메서드가 반환한 반복자가
remove 메서드를 구현하지 않았다면 UnsupportedOperationException을 던지니 주의하자.
설명에 따르면 iterator 메서드를 재정의하면 remove 메서드의 동작에 영향을 줌을 알 수 있다. iterator 메서드로 얻은 반복자의 동작이 remove메서드의 동작에 주는 영향도 설명했다. 이런식으로 클래스를 안전하게 상속할 수 있도록 하려면 내부 구현 방식을 설명해주어야 한다.
하지만 내부 매커니즘을 문서로 남기는 것만이 상속을 위한 설계의 전부는 아니다. 효율적인 하위 클래스를 만들 수 있게 하려면 클래스의 내부 동작 과정 중간에 끼어들 수 있는 훅(hook)을 잘 선별하여 protected메서드 형태로 공개해야 할 수도 있다.
훅 메서드 : 상위 클래스에서 정의되지만, 기본적으로 아무 작업도 수행하지 않거나 기본 동작만 수행하는 메서드이다. 이 메서드들을 오버라이드(재정의)함으로써, 상위 클래스의 동작 과정 중 특정 지점에서 원하는 동작을 알고리즘 흐름을 변경하지 않으면서 추가하거나 변경할 수 있다.
public abstract class Beverage {
// 이 메서드는 알고리즘의 템플릿을 제공합니다.
// 즉, 음료를 준비하는 일련의 단계를 정의합니다.
final void prepareRecipe() {
boilWater();
brew();
pourInCup();
if (customerWantsCondiments()) { // 훅(hook). 하위 클래스에서 이 메서드를 오버라이드할 수 있습니다.
addCondiments();
}
}
abstract void brew();
abstract void addCondiments();
void boilWater() {
System.out.println("물을 끓입니다.");
}
void pourInCup() {
System.out.println("컵에 붓습니다.");
}
// 이것이 바로 훅 메서드입니다. 기본적으로 이 메서드는 'true'를 반환하지만,
// 하위 클래스에서 이 메서드의 동작을 변경할 수 있습니다.
protected boolean customerWantsCondiments() {
return true;
}
}
// 하위 클래스 예시: 커피 준비하기
public class Coffee extends Beverage {
@Override
void brew() {
System.out.println("필터를 통해 커피를 우려냅니다.");
}
@Override
void addCondiments() {
System.out.println("설탕과 우유를 추가합니다.");
}
@Override
protected boolean customerWantsCondiments() {
// 여기서는 사용자가 조미료(설탕, 우유)를 추가하길 원하는지에 대한 로직을 구현할 수 있습니다.
// 예를 들어, 사용자의 입력을 받아 결정할 수 있습니다.
// 이 예제에서는 단순화를 위해 항상 'true'를 반환하도록 합니다.
return true;
}
}
이처럼 hook 메서드를 잘 활용하면 내부 동작 과정 중 중간에 끼어들어 수정할 수 있다. 어떤 메서드를 protected로 노출해야 할지는 그냥 심사숙고해서 잘 예측해보고, 실제로 하위 클래스를 만들어 보는것이 최선이다. 반드시 하위 클래스를 만들어 검증해야 한다.
클래스를 상속용으로 설계하려면 엄청난 노력이 들고 그 클래스에 안기는 제약도 상당하기 때문에 절대 가볍게 생각하고 정할 문제가 아니다. 상속을 허용하는게 명확히 정당한 상황이 있고, 아닌 상황이 있다. 이런 문제를 해결하는 가장 좋은 방법은 상속용으로 설계하지 않은 클래스는 상속을 금지하는 것이다.
결론 : 상속용 클래슬르 설계하려면 클래스 내부에서 스스로를 어떻게 사용하는지(자기 사용 패턴) 모두 문서로 남겨야 하며, 일단 문서화 한것은 그 클래스가 쓰이는 한 반드시 지켜야 한다. 그렇지 않으면 그 내부 구현 방식을 믿고 활용하던 하위 클래스를 오동작하게 만들 수 있다. 다른 이가 효율 좋은 하위 클래스를 만들 수 있도록 일부 메서드를 protected로 제공해야할 수도 있다. 그러니 클래스를 확장해야 할 명확한 이유가 떠오르지 않으면 상속을 금지하는 편이 낫다. 상속을 금지하려면 클래스를 final로 선언하거나 생성자 모두를 외부에서 접근할 수 없도록 만들면 된다.
상속 : 한 클래스가 다른 클래스의 속성과 메서드를 확장 혹은 재정의할 수 있도록 해주는 매커니즘
// 상속의 예시 :
// 부모 클래스: 동물
class Animal {
public void eat() {
System.out.println("이 동물은 먹는다.");
}
}
// 자식 클래스: 개
// Dog 클래스는 Animal 클래스를 상속받음으로써 "개는 동물이다"라는 Is-a 관계를 형성합니다.
class Dog extends Animal {
public void bark() {
System.out.println("개는 짖는다.");
}
}
컴포지션 : 하나의 클래스가 다른 클래스의 인스턴스를 포함하여, 그 인스턴스의 메서드를 활용하는 방식
// 컴포지션의 예시 :
// 독립된 기능을 가진 클래스: 소리 생성기
class SoundMaker {
public void makeSound(String sound) {
System.out.println(sound);
}
}
// 개 클래스에서 소리 생성기를 사용
class Dog {
private SoundMaker soundMaker;
public Dog() {
this.soundMaker = new SoundMaker();
}
// 전달 메서드: Dog 클래스의 bark 메서드는 내부적으로 SoundMaker의 makeSound 메서드를 호출합니다.
public void bark() {
soundMaker.makeSound("멍멍!"); // 위임: Dog 객체는 짖는 기능을 SoundMaker 객체에 위임합니다.
}
}
상속은 코드를 재사용하는 강력한 수단이지만, 항상 최선은 아니다. 잘못 사용하면 오류를 내기 쉬운 소프트웨어를 만들게 된다.
상속의 문제점 :
강한 결합 : 부모 클래스의 내부 변경이 자식 클래스에 영향을 줄 수 있어 유연성이 저하된다.
캡슐화 위반 : 자식 클래스가 부모 클래스의 구현 세부 사항에 의존하게되면, 캡슐화가 약화된다.
재사용성 저하 : 특정 구현에 강하게 결합된 상속 구조는 새로운 상황에 재사용하기 어렵다.
이러한 문제를 모두 피해가기 위해 기존 클래스를 확장하는 대신, 새로운 클래스를 만들고 private 필드로 기존 클래스의 인스턴스를 참조하게 하자. 기존 클래스가 새로운 클래스의 구성요소로 쓰인다는 뜻에서 이런 설계를 컴포지션(compostition : 구성) 이라고 한다.
새 클래스의 인스턴스들은 기존 클래스의 대응하는 메서드를 호출해 그 결과를 반환한다. 이 방식을 전달(forwarding) 이라고 하며, 새 클래스의 메서드들을 전달 메서드라 부른다.
컴포지션과 전달(위임)의 장점 :
낮은 결합도 : 객체간의 결합도를 낮춰, 유연성과 확장성을 향상시킨다.
캡슐화 강화 : 내부 구현을 숨기고, 필요한 인터페이스만 노출시켜 캡슐화를 강화.
재사용성 향상 : 구성 요소를 쉽게 교체하거나 재사용할 수 있어, 다양한 상황에 맞게 시스템을 조정할 수 있다.
Is-a 관계는 상속을 이용하여 한 클래스가 다른 클래스의 특별한 형태임을 나타내는 관계다.
래퍼 클래스는 기본 데이터 타입의 값을 객체로 변환해야 할 때 사용된다.
// 래퍼 클래스의 예
int i = 5; // 기본 타입 int 사용
Integer integerObject = new Integer(5); // Integer 객체 생성 (래퍼 클래스 사용)
Integer autoBoxedInteger = 5; // 오토 박싱을 통한 Integer 객체 생성
// 오토 언박싱: Integer 객체에서 int 기본 타입 값으로 자동 변환
int unboxedInt = integerObject;
//오토 박싱은 기본 데이터 타입의 값을 해당하는 래퍼 클래스의 객체로 자동 변환하는 과정을,
//언박싱은 그 반대 과정을 의미합니다.
결론 : 상속은 강력하지만 캡슐화를 해친다. 상속은 상위 클래스와 하위 클래스가 순수한 is-a 관계일 때만 써야 한다. is-a 관계일 때도 하위 클래스의 패키지가 상위 클래스와 다르고, 상위 클래스가 확장을 고려해 설계되지 않았다면 여전히 문제가 될 수 있다. 이를 해결하려면 컴포지션과 전달을 사용해야 한다. 특히 래퍼 클래스로 구현할 적당한 인터페이스가 있다면 더욱 그렇다. 래퍼 클래스는 하위 클래스보다 견고하고 강력하다.
import java.io.*;
import java.util.*;
public class Main {
static int[][] graph;
static boolean[] visited;
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 M = Integer.parseInt(st.nextToken()); // 간선의 수
int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점 번호
graph = new int[N + 1][N + 1]; // 1부터 시작
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph[u][v] = graph[v][u] = 1; // 양방향 간선
}
visited = new boolean[N + 1];
dfs(V);
System.out.println();
visited = new boolean[N + 1];
bfs(V);
}
// dfs : 깊이우선탐색(재귀)
public static void dfs(int v) {
visited[v] = true;
System.out.print(v + " ");
if (v == graph.length) {
return;
}
for (int i = 1; i < graph.length; i++) {
if (graph[v][i] == 1 && visited[i] == false) {
dfs(i);
}
}
}
// bfs : 너비우선탐색(큐)
public static void bfs(int v) {
Queue<Integer> q = new LinkedList<>();
q.add(v);
visited[v] = true;
System.out.print(v + " ");
while (!q.isEmpty()) {
int tmp = q.poll();
for (int i = 1; i < graph.length; i++) {
if (graph[tmp][i] == 1 && visited[i] == false) {
q.add(i);
visited[i] = true;
System.out.print(i + " ");
}
}
}
}
}
[설명]
dfs 와 bfs의 기본문제이다. 항상 풀 때마다 개념정립이 애매했는데. 이 문제를 디버깅하면서 제대로 이해했다.
클래스를 불변으로 설계하는 이유 : 가변 클래스보다 설계하고 구현하고 사용하기 쉽고 오류가 생길 여지가 적어 안전하다.
클래스를 불변으로 만드는 규칙 :
객체의 상태를 변경하는 메서드(변경자)를 제공하지 않는다.
setter 메서드를 제공하지 않아야한다. 객체의 상태는 생성 시점에만 설정되고, 이후에는 변경될 수 없다.
클래스를 확장할 수 없도록 한다.
상속을 통해 하위 클래스에서 부주의하게 객체의 상태를 변경하는 사태를 막아준다.
모든 필드를 final로 선언한다.
필드가 생성자에서 한 번만 할당될 수 있고, 이후에는 그 값이 변경될 수 없다.
모든 필드를 private으로 선언한다.
private으로 선언함으로써 클래스 외부에서 직접 접근할 수 없게한다.
자신 외에는 내부의 가변 컴포넌트에 접근할 수 없도록 한다.
클래스에 가변 객체를 참조하는 필드가 하나라도 있다면 클라이언트에서 그 객체의 참조를 얻을 수 없도록 해야 한다. 가변 객체를 참조하는경우 해당 참조를 직접 노출하지 않고 방어적 복사를 통해 반환해야 한다.
이 다섯가지 규칙을 모두 활용해 만든 예시 코드이다 :
public final class ImmutableClass {
private final String name; // 3. 모든 필드는 final
private final int value;
private final List<String> mutableList; // 가변 컴포넌트
// 생성자에서 모든 필드를 초기화
public ImmutableClass(String name, int value, List<String> mutableList) {
this.name = name;
this.value = value;
// 5. 내부 가변 컴포넌트의 방어적 복사본 생성
this.mutableList = new ArrayList<>(mutableList);
}
// 1. 변경자 메서드 없음
// 접근자 메서드는 필드의 값만 반환하고, 가변 필드의 경우 방어적 복사본을 반환
public String getName() {
return name;
}
public int getValue() {
return value;
}
public List<String> getMutableList() {
// 가변 필드에 대한 방어적 복사본 반환
return new ArrayList<>(mutableList);
}
}
결론 : 클래스는 꼭 필요한 경우가 아니라면 불변이어야 한다. 하지만 모든 클래스를 불변으로 만들 수는 없다. 불변으로 만들 수 없는 클래스라도 변경할 수 있는 부분을 최소한으로 줄이자. 다른 합당한 이유가 없다면 모든 필드는 private final 이어야 한다. 생성자는 불변식 설정이 모두 완료된, 초기화가 완벽히 끝난 상태의 객체를 생성해야 한다. 확실한 이유가 없다면 생성자와 정적 팩터리 메서드 외에는 그 어떤 초기화 메서드도 public으로 제공해서는 안된다.
캡슐화는 객체의 데이터(필드)와 그 데이터를 조작하는 메서드를 하나의 단위로 묶는 것을 의미한다. 이를 통해 객체의 상태를 보호하고 외부에서 직접 접근하는 것을 제한하여 객체의 유지보수와 확장성을 향상시킬 수 있다.
// 좋지 않은 예: public 필드를 직접 사용
class PersonBadExample {
public String name;
public int age;
public PersonBadExample(String name, int age) {
this.name = name;
this.age = age;
}
}
// 좋은 예: private 필드와 public 접근자/설정자 메서드를 사용
class PersonGoodExample {
private String name;
private int age;
public PersonGoodExample(String name, int age) {
this.name = name;
this.age = age;
}
// 이름에 대한 접근자 메서드
public String getName() {
return name;
}
// 이름을 설정하는 메서드
public void setName(String name) {
this.name = name;
}
// 나이에 대한 접근자 메서드
public int getAge() {
return age;
}
// 나이를 설정하는 메서드
public void setAge(int age) {
if (age > 0) { // 유효성 검사 예시
this.age = age;
}
}
}
// 사용 예
public class Main {
public static void main(String[] args) {
// 좋지 않은 예
PersonBadExample badExample = new PersonBadExample("John Doe", 30);
badExample.age = -5; // 유효하지 않은 나이 설정 가능
// 좋은 예
PersonGoodExample goodExample = new PersonGoodExample("Jane Doe", 30);
goodExample.setAge(-5); // 유효성 검사를 통과하지 못해 설정되지 않음
}
}
좋지 않은 예에서는 필드를 public 으로 설정해 객체의 상태를 외부에서 직접 변경할 수 있게 되어있다. 이는 잘못된 설계이다.
좋은 예 에서는 모든 필드를 private로 선언해 각 필드에 대한 접근자(getter)와 설정자(setter)메서드를 제공해주어 내부 표현 방식을 언제든 바꿀 수 있는 유연성을 얻을 수 있다.
결론 : public 클래스는 절대 가변 필드를 노출해서는 안된다. 불변 필드라면 노출해더 덜 위험하지만 안전한것은 아니다. 하지만 package-private 클래스나 private 중첩 클래스에서는 종종 필드를 노출하는 편이 나을때도 있다.
"클래스와 멤버의 접근권한을 최소화하라"는 원칙은 정보 은닉(Encapsulation)과 관련된 개념으로, 코드를 작성할 때 클래스와 그 내부 멤버에 대한 접근 권한을 가능한 한 제한하는 것을 권장하는 원칙이다. 이렇게 함으로써 코드의 유지 보수성과 안정성을 높일 수 있다.
정보은닉의 기본 원칙 : 모든 클래스와 멤버의 접근성을 가능한 한 좁혀야 한다. 소프트웨어가 올바르게 동작하는 한 항상 가장 낮은 접근 수준을 부여해야 한다.
멤버에 부여할 수 있는 접근 수준 :
public: 이 접근 수준을 가진 멤버는 어디서든 접근할 수 있다. 즉, 해당 멤버는 외부 클래스, 패키지, 심지어 다른 모듈에서도 접근할 수 있다.
protected: 이 접근 수준을 가진 멤버는 동일한 패키지 내의 클래스 및 해당 클래스를 상속한 하위 클래스에서 접근할 수 있다. 즉, protected 멤버는 패키지 외부에서는 접근할 수 없지만, 하위 클래스에서는 접근할 수 있다.
default (package-private): 접근 수준을 명시하지 않는 경우, 해당 멤버는 기본(default) 접근 수준을 가진다. 이 경우, 멤버는 동일한 패키지 내의 클래스에서만 접근할 수 있다. 패키지 외부에서는 접근할 수 없다.
private: 이 접근 수준을 가진 멤버는 선언된 클래스 내에서만 접근할 수 있다. 외부 클래스에서는 접근할 수 없다. 이는 정보 은닉을 위해 사용된다.
- public 클래스의 인스턴스 필드는 되도록 public이 아니어야 한다. 클래스의 내부 구현 세부사항을 외부에 노출시키지 않고, 외부에서 직접적으로 접근하여 변경하지 못하도록 하는 것을 의미한다. 가능한한 클래스의 인스턴스 필드는 private으로 선언하고, 필요한 경우에만 접근자(getter)와 설정자(setter)를 제공하여 외부에서 간접적으로 접근하도록 하는 것이 바람직하다. 이를 통해 정보 은닉과 캡슐화를 유지하고, 안정성과 유연성을 높여 데이터 유효성을 보장해준다.
- public 가변 필드를 갖는 클래스는 일반적으로 스레드 안전하지 않다. 멀티 스레드 환경에서 해당 클래스의 인스턴스를 여 러 스레드가 동시에 접근하고 수정할 때 문제가 발생할 수 있다. 예를 들어, 한 스레드가 값을 읽는 동안 다른 스레드가 값을 변경할 수 있으며, 이로 인해 데이터 불일치가 발생할 수 있다.
- 클래스에서 public static final 배열 필드를 두거나 이 필드를 반환하는 접근자 메서드를 제공해서는 안된다.
public : 모든 클래스에서 접근 할 수 있다.static : 클래스의 인스턴스화 없이 사용할 수 있다.final : 한 번 초기화되면 그 값이 변경되지 않는다. 즉, 해당 필드는 상수로 취급된다. (상수 : 고정된 값)
아래의 클래스는 public static final 배열 필드를 사용하고, 해당 필드를 반환하는 접근자 메서드를 제공한다. 보안 허점이 숨어있는 코드이다.
public class Constants {
public static final String[] COLORS = {"Red", "Green", "Blue"};
public static String[] getColors() {
return COLORS;
}
}
COLORS 배열을 public static final 필드로 선언하고, getColors() 메서드를 통해 외부에서 이 배열에 접근할 수 있다.
이 코드는 2가지 문제점이 있다.
불변성 보장의 부족: COLORS 배열은 public static final로 선언되어 있지만, 배열 자체는 불변이 아니다. 즉, 배열의 요소를 변경할 수 있다. 배열은 크기가 고정되고 한 번 생성되면 수정할 수 없는 자료 구조이다. 이러한 배열을 public static final 필드로 제공하면 해당 배열은 수정할 수 없는 상수 배열로 간주된다. 그러나 배열이 참조 타입이기 때문에 해당 배열을 참조하는 다른 변수들이 배열 내의 요소를 변경할 수 있어서 불변성을 보장하지 않는다.
캡슐화 원칙 위배: 외부에서 COLORS 배열에 직접 접근할 수 있으므로 캡슐화 원칙을 위배한다. 캡슐화는 클래스의 내부 상태를 외부에서 직접 접근할 수 없도록 보호하는 것을 의미한다. 배열의 참조를 변경하는 것은 불가능하지만, 배열 내의 요소를 변경하는 것은 가능하다. 예를 들어, Constants.COLORS[0] = "Yellow"; 같이 배열의 요소를 변경할 수 있다.
아래처럼 코드를 수정하면 해결할 수 있다.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Constants {
// private static final로 선언된 배열 COLORS
private static final String[] COLORS = {"Red", "Green", "Blue"};
// getColors 메서드: COLORS 배열을 변경할 수 없는 리스트 형태로 반환
public static List<String> getColors() {
// Arrays.asList 메서드를 사용하여 COLORS 배열을 리스트로 변환
// 이 메서드는 고정 크기의 리스트를 반환하므로 리스트의 크기는 변경될 수 없음
// unmodifiableList 메서드를 사용하여 리스트를 변경할 수 없는 리스트로 래핑
return Collections.unmodifiableList(Arrays.asList(COLORS));
}
}
public 배열을 private 으로 만들고 public 불변 리스트를 추가해주면 된다.
결론 : 프로그램 요소의 접근성은 가능한 한 최소한으로 하자. 꼭 필요한 것만 골라 최소한의 public API를 설계하자. 그 외에는 클래스, 인터페이스, 멤버가 의도치 않게 API로 공개 되는 일이 없도록 해야 한다. public 클래스는 상수용 public static final 필드 외에는 어떠한 public 필드도 가져서는 안 된다. public static final 필드가 참조하는 객체가 불변인지 확인하자.
import java.io.*;
import java.util.*;
public class Main {
static int root;
static Node[] tree;
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());
tree = new Node[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
int parent = Integer.parseInt(st.nextToken());
tree[i] = new Node(parent); // 노드의 번호는 i, i번 노드의 부모는 parent 인 Node를 생성
if (parent == -1) { // parent 번호가 -1 이면 해당 노드는 루트 노드
root = i;
}
}
// 루트 노드가 아닌 경우, 해당 노드의 부모 노드를 찾아 자식노드에 자신을 추가
for (int i = 0; i < N; i++) {
if (root != i) { // 루트노드가 아닐경우
int parent = tree[i].parent; // i 번 노드의 부모노드를 꺼내서
tree[parent].addChild(i); // 부모노드의 자식에 i번 노드를 추가해줌
}
}
int removeNode = Integer.parseInt(br.readLine()); // 삭제 할 노드 번호
if (removeNode == root) { // 루트 노드를 지울경우 전부 삭제되므로 0 출력
System.out.println(0);
} else {
int parent = tree[removeNode].parent; // 삭제하려는 노드의 부모 노드의 값을 꺼냄
tree[parent].removeChild(removeNode); // 그 부모노드의 자식노드들 중 삭제하려는 노드번호를 삭제
int leafSize = getLeafSize(root); // 리프노드의 수를 카운팅
System.out.println(leafSize);
}
}
static int getLeafSize(int index) {
if (tree[index].isLeaf()) { // 해당 노드의 자식노드가 없다면 true 를 반환해서
return 1; // 1 반환
}
int sum = 0;
for (int i = 0; i < tree[index].getChildrenSize(); i++) {
sum += getLeafSize(tree[index].children.get(i)); // 반복문을 재귀적으로 돌며 자식노드가 없는 노드들을 탐색
}
return sum;
}
}
// 노드 클래스
class Node {
int parent; // 해당 노드의 부모 노드
List<Integer> children; // 자식노드들
public Node(int parent) {
this.parent = parent;
this.children = new ArrayList<>(); // 자식노드들은 ArrayList 로 생성
}
public void addChild(int child) { // 노드의 자식들을 ArrayList.add 로 삽입
this.children.add(child);
}
public void removeChild(int child) { // 노드의 자식들을 ArrayList.remove 로 삭제
this.children.remove(Integer.valueOf(child));
}
public boolean isLeaf() { // 노드의 자식이 없다면 true 반환
return this.children.isEmpty();
}
public int getChildrenSize() { // 노드의 자식들의 개수를 ArrayList.size() 메서드를 활용해 출력
return this.children.size();
}
}
[설명]
저번에 풀었던 노드의 심화버전이다. 그래서 저번에 풀었던 코드를 조금만 수정해 풀려고 했으나 실패해 포기해 다른분들의 코드를 찾아보며 풀어버렸다.
