인프런 커뮤니티 질문&답변

abc9023님의 프로필 이미지

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

12. 멘토링

멘토링 문제 4중for문

작성

·

890

0

이문제 4중for문 이외에 방법이 혹시 있나요?

반의 학생수가 지금 제한보다 훨씬 많아지면

4중for으로 하면 메모리나 시간 복잡도 때문에 

되지 않을것 같아서 질문드립니다~!

답변 6

2

안녕하세요 ArrayList 를 이용한 3중 for문 코드입니다.

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

class Main {
    public int solution(int[][] arr, int student_size, int test_size) {
        int answer = 0;
        ArrayList<Integer> possible = new ArrayList<>();

        for (int i = 0; i < student_size; i++) {
            possible.clear();
            for(int init = 1; init < student_size+1; init++) possible.add(init);

            int my = i+1;
            for(int test = 0; test < test_size; test++) {
                boolean islow = false;
                for (int rank = 0; rank < student_size; rank++) {
                    if (!islow && possible.contains(arr[test][rank])) possible.remove(Integer.valueOf(arr[test][rank]));
                    if (arr[test][rank] == my) islow = true;
                }
            }
            answer += possible.size();
        }

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int student = kb.nextInt();
        int test = kb.nextInt();
        int[][] arr = new int[test][student];
        for (int i = 0 ; i < test; i++)
            for (int j = 0; j < student; j++)
                arr[i][j] = kb.nextInt();
        System.out.println(T.solution(arr, student, test));
    }
}

1

import java.util.Scanner;

import static java.lang.System.in;
import static java.lang.System.out;

public class Main{
    public static int solution(int n, int m, int[][] arr) {
        int[][] temp = new int[n][n];
        int cnt = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = j; k < n; k++) {
                    temp[arr[i][j] - 1][arr[i][k] - 1] = 1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (temp[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        out.println(solution(n, m, arr));
    }

}

   ...

1

안녕하세요? 혹시나 도움이 되실까해서 글 남깁니다. ㅎㅎ

저는 아래방식처럼 3중 for문으로 풀었네욥

int solution (int n, int m,int[][] num) {
int[][] isMento = new int[n][n];
//m 번의 시험
for(int i=0; i<m; i++) {
// 비교
for (int j =0; j<n-1;j++) {
for(int k=j+1 ; k<n; k++) {
if(isMento[num[i][j]-1][num[i][k]-1] !=-1) {
if (isMento[num[i][k]-1][num[i][j]-1]==-1) {
isMento[num[i][j]-1][num[i][k]-1] = -1;
} else {
if(isMento[num[i][k]-1][num[i][j]-1]==1){
isMento[num[i][j] - 1][num[i][k] - 1] = -1;
isMento[num[i][k] - 1][num[i][j] - 1] = -1;
}else {
isMento[num[i][j] - 1][num[i][k] - 1] = 1;
}
}
}
}
}
}

int answer =0;

for(int i =0;i<n;i++) {
for(int j=0; j<n;j++) {
if(isMento[i][j] == 1) answer++;
}
}

return answer;
}

0

import java.io.*;
import java.util.Arrays;
import java.util.stream.Collectors;

public class 멘토링 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = br.readLine().split(" ");
        int studentCount = Integer.parseInt(temp[0]);
        int examCount = Integer.parseInt(temp[1]);
        int[][] arrs = new int[examCount][studentCount];

        for(int i  =0; i<examCount; i++){
            int[] students = new int[studentCount];
            String[] temp2 = br.readLine().split(" ");
            for(int j=0; j<studentCount; j++){
                students[j] = Integer.parseInt(temp2[j]);
            }
            arrs[i] = students;
        }

        bw.write(solution(arrs, studentCount, examCount));
        bw.flush();
        bw.close();
        br.close();

    }

    private static String solution(int[][] arrs, int studentCount, int examCount) {
        int[][] check = new int[studentCount+1][studentCount+1];
        int answer= 0;
        for(int i =0; i<examCount; i++) {
            for(int j=0; j<studentCount-1; j++){
                int mentor = arrs[i][j];
                for(int k = j+1; k<studentCount; k++){
                    int menti = arrs[i][k];
                    if(check[menti][mentor] ==0 && check[mentor][menti] ==0){
                        check[mentor][menti] =1;
                        answer++;
                    }else if(check[menti][mentor] ==1){
                        check[menti][mentor] =-1;
                        check[mentor][menti] = -1;
                        answer--;
                    }
                }
            }
        }
        return String.valueOf(answer);
    }


}

 

0

public int solution(int student, int test, int[][] arr) {

    int answer = 0;

    //(1번학생~4번학생까지 차례로 구하기)
    for (int i=0; i<student; i++) {
        List<Integer> list = new ArrayList<>();
        for(int j = 0; j<test; j++){
            int index = student-1;
            for(int k=0; k<student; k++){
                if(arr[j][k] == i+1){ //각 시험(행)에서 멘토 인덱스(등수) 구하기
                    index = k;
                }
                if(k>index){ //각 시험(행)에서 멘토의 등수보다 낮은 학생들 넣기
                    list.add(arr[j][k]);
                }
            }
            if(index == student-1) { //꼴등을 한번이라도 한적 있으면 멘토가 될 수 없어 clear
                list.clear();
            }
        }
        //list : 멘토 뒤 등수 인 학생 모임(중복 O)
        //중복제거 한 학생별로 list안에 시험 갯수(M) 만큼 있는 학생만 카운트.
        answer += list.stream().distinct()
                .filter(integer -> Collections.frequency(list, integer) == test)
                .count();
    }
    return answer;
}

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

해당 문제를 출제했던 대회에서 정답으로 제시한게 4중 for문입니다.

abc9023님의 프로필 이미지

작성한 질문수

질문하기