[백준] 백준 1043 거짓말 (java)

백준 1043 거짓말 java

4 sloved.ac Gold4/Class4

문제 해설

거짓말을 할 수 있는 파티의 수를 출력하는 문제입니다. 이 문제에서 중요한점은 아래 두가지 입니다.

1. 파티에 진실을 아는 사람이 있는 경우, 해당파티에 있는 사람은 모두 진실을 아는 사람이다.
2. 진실을 아는 사람이 없는 파티에서는 거짓말을 할 수 있다.

문제 해결 순서

1. 진실을 아는 사람과 한번이라도 겹치는 사람들을 모두 진실을 아는 사람에 추가합니다.

2. 진실을 아는 사람이 한번도 참석하지 않은 파티의 수를 출력합니다.

부분 코드

knowReals -> 진실을 아는사람들을 저장한 ArrayList
peopleInParty -> 파티에 참석하는 사람들을 모아둔 ArrayList의 ArrayList

1. 진실을 아는 사람과 한번이라도 겹치는 사람들을 모두 진실을 아는 사람에 추가합니다.

// 모든 파티를 체크
for(int j = 0; j<numberOfParty; j++) {
    for (int i = 0; i < numberOfParty; i++) {
        // knowReals에 속하는 사람이 해당 파티에 존재하는 경우,
        for (int knowReal : knowReals) {
            // 해당 파티에 참석한 모든 사람을 knowReals에 추가한다.
            if (peopleInParty.get(i).contains(knowReal)) {
                for (int personInParty : peopleInParty.get(i)) {
                    knowReals.add(personInParty);
                }
                break;
            }
        }
    }
}

2. 진실을 아는 사람이 한번도 참석하지 않은 파티의 수를 출력합니다.

// 진실을 아는 사람이 아무도 없는 경우, 해당 파티에서는 거짓말을 해도 된다.
for(int i = 0; i<numberOfParty; i++) {
    for(int person : knowReals) {
        if (peopleInParty.get(i).contains(person)) {
            addPoint = 0;
            break;
        }
        addPoint = 1;
    }
    result += addPoint;
}

결론

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        String[] strings = scanner.nextLine().split(" ");
        int numberOfParty = Integer.parseInt(strings[1]);

        int addPoint = 1;
        int result = 0;

        strings = scanner.nextLine().split(" ");

        ArrayList<Integer> knowReals = new ArrayList<Integer>();
        for(String str : strings) {
            knowReals.add(Integer.parseInt(str));
        }
        knowReals.remove(0); // 처음 값은 총 인원이기 때문에 제외

        ArrayList<ArrayList<Integer>> peopleInParty = new ArrayList<ArrayList<Integer>>();

        //파티와 각 파티에 참석하는 사람을 저장한다.
        for(int i = 0; i<numberOfParty; i++) {
            peopleInParty.add(new ArrayList<Integer>());
            strings = scanner.nextLine().split(" ");
            for(String str : strings) {
                peopleInParty.get(i).add(Integer.parseInt(str));
            }
            peopleInParty.get(i).remove(0);
        }

        // 광기의 knownReals.. 찾기

        // 모든 파티를 체크하는데, 시간상관없이 체크해야하기 때문엔 이중 for문을 돈다.
        for(int j = 0; j<numberOfParty; j++) {
            for (int i = 0; i < numberOfParty; i++) {
                // knowReals에 속하는 사람이 해당 파티에 존재하는 경우,
                for (int knowReal : knowReals) {
                    // 해당 파티에 참석한 모든 사람을 knowReals에 추가한다.
                    if (peopleInParty.get(i).contains(knowReal)) {
                        for (int personInParty : peopleInParty.get(i)) {
                            knowReals.add(personInParty);
                        }
                        break;
                    }
                }
            }
        }

        // 진실을 아는 사람이 아무도 없는 경우, 해당 파티에서는 거짓말을 해도 된다.
        for(int i = 0; i<numberOfParty; i++) {
            for(int person : knowReals) {
                if (peopleInParty.get(i).contains(person)) {
                    addPoint = 0;
                    break;
                }
                addPoint = 1;
            }
            result += addPoint;
        }
        System.out.println(result);
    }
}

느낀점

이전에 풀었던 문제를 다시 보면서 포스팅을 하니 코드의 문제점이 많이 보인다.
좀 더 효율적이고 읽기 좋은 코드를 짜기 위해 노력해야겠다.

github

제 알고리즘 문제풀이 코드는 해당 깃헙 레파지토리에서 확인하실 수 있습니다.

https://github.com/Jeeseob/Algoritm_Study