BOJ) 좋은 대회

좋은 대회

14610번: 좋은 대회

풀이

 

두번의 로직을 세워서 풀었다.

우선, 공통된 코드는 참가자 수와 문제 수를 받은 후에, 문제 풀이를 담는 배열을 선언해주었다.

각 입력받은 라인마다 푼 문제에 대해 체크를 해주었다. 그리고 문제의 조건에 따라 좋은 대회가 아닌 경우를 판별해주었다.

 

문제의 조건

1. 모든 참가자가 한 문제 이상을 풀어야 한다.
2. 모든 문제는 한 명 이상의 참가자에게 풀려야 한다.
3. 모든 문제를 푼 참가자는 없어야 한다.

 

틀렸던 첫번째 로직은, 문제 풀이 여부 배열을 선언하고, 풀린 문제 번호나 그렇지 않은 경우를 각각 1과 0으로 저장해주었다.

또한, 각 라인마다 문제를 풀 수 있는 남은 횟수를 저장했다. 이후, 남은 횟수가 -1인 문제의 숫자보다 크거나 같은 경우 풀 수 있는 경우로 지정해주었는데, 특정 테스트 케이스에서 틀린 것을 확인했다.

 

그래서 두번째 로직으로 바꿔주었다.  문제를 풀 수 있는 남은 횟수와, -1인 문제들을 담을 LinkedList를 가지고 있는 Participant 클래스를 만들었다. 각 입력받은 라인에 따라 실행한 후에, 남은 횟수가 1 이상인 경우에 이 Participant 객체들을 담아 줄 LinkedList에 담았다.

 

LinkedList의 끝 부분부터 순회하면서, 문제를 풀 수 있는 경우를 체크하면서 problems 배열을 완성 시켰다.

그 이후 배열을 돌면서 못푼 문제가 존재하는 경우 (-1 or 0) 좋은 대회가 아닌 값을 리턴해주었고, 모든 검증을 마친 후에도 return된 적이 없다면, 좋은 대회라는 값을 return해주었다.

 

순회하는 기준은 앞이나 뒤나 상관 없을 것 같기는 하지만, 자체적으로 만들었던 테스트 케이스에서 뒤쪽부터 순회하는 경우를 생각하고 만들었어서 끝에서 처음 부분으로 순회를 했다.

 

설명하기에 조금 복잡하지만, 조건에 따라 문제를 풀 수 있는지 없는지를 판단하는 코드라고 이해하면 조금 도움이 될 것 같다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class GreatContest_14610 {
    public static void main(String[] args) throws IOException {
        System.out.println(solution(new BufferedReader(new InputStreamReader(System.in))));
    }

    private static String solution(BufferedReader br) throws IOException{
        final String YES = "YES";
        final String NO = "NO";

        String str = br.readLine();
        int N = Integer.parseInt(str.split(" ")[0]);   // 참가자 수
        int M = Integer.parseInt(str.split(" ")[1]);   // 문제 수
        int[] problems = new int[M]; // 문제 풀이 여부를 담을 배열

        LinkedList<Participant> remainList = new LinkedList<>();

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            Participant person = new Participant();
            for(int j=0; j<=M; j++) {
                if(j ==0) { // 푼 문제 수 담기
                    int solve = Integer.parseInt(st.nextToken());
                    if(solve ==0) { // 1번 조건
                        return NO;
                    } else if(solve == M) { // 3번 조건
                        return NO;
                    }
                    person.setRemain(solve);
                } else { // 문제에 대한 풀이 여부
                    int prob = Integer.parseInt(st.nextToken());
                    if(prob ==1) { // 풀었을 때
                        problems[j-1] = prob; // 풀었다고 체크
                        person.remain--;
                    } else if(prob ==-1) {
                        if(problems[j-1] == 0) { // 못 푼 상태일 때만
                            problems[j-1] = prob; // 못풀었다고 체크
                        }
                        person.addList(j-1);
                    }
                }
            }
            if(person.remain !=0) {
                remainList.add(person);
            }
        }

        while(!remainList.isEmpty()) {
            Participant person = remainList.pollLast();
            for(int idx : person.list) {
                if(problems[idx] ==-1 && person.remain-- >0) {
                    problems[idx] =1;
                }
            }
        }

        for(int prob : problems) {
            if(prob != 1) { // 2번 조건
                return NO;
            }
        }


        br.close();
        return YES;
    }
}

class Participant {
    int remain;
    LinkedList<Integer> list;

    public Participant() {
        this.remain =0;
        list = new LinkedList<>();
    }

    public void setRemain(int remain) {
        this.remain = remain;
    }

    public void addList(int problem) {
        list.offer(problem);
    }
}