자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_임시반장 정하기)

 

 

https://cote.inflearn.com/contest/10/problem/02-11

OnlineJudge

 

11. 임시반장 정하기

예시 입력 1 

5
2 3 1 7 3
4 1 9 6 8
5 5 2 4 4
6 5 2 6 7
8 4 2 2 2

예시 출력 1

4

 

내가 푼 틀린 풀이 (5개 케이스중 2개 오답 - 정확도 낮음)

결론 : 문제를 읽고 2차원 배열에서 어떤 개념을 먼저 순회해야할지, 어떤 방향으로 순회해야할지 미숙하다.

 

나는 우선 학년 5개를 제일 첫번째 for문으로 시작했는데, 그렇게 되면 학생 수보다 학년이 고정된 상태라서

특정 학생이 학년별로 같은 반이 었는지 확인하기가 어려울 것 같다.

학생은 고정된 상태에서 학년이 내부 for문으로 돌아야 다음 학년까지 비교를 할 수 있을 것 같다.

 

그리고 같은 반이었던 숫자를 set에다가 넣었는데.. 글쎄 왜 이렇게 풀려고 했을까?

학년 마다 한번 1반을 하면 다시 1반을 하지 않을 거라고 생각했던 것 같다.

그래서 같은 반이었던 숫자들을 모아서 다시 for문을 돌려서 전부 일치하는 학생을 정답으로 하고 싶었다.

import java.util.*;

public class Main {

    public int solution(int n, int[][] arr) {
        int answer = 0;
        Set<Integer> duplicates = new HashSet<>();
        // 학년 5개
        for (int i = 0; i < 5; i++) {
            // 학생 수
            for (int j = 0; j < n; j++) {
                int duplicate = arr[j][i];
                // 학생 수
                for (int k = 0; k < n; k++) {
                    if (duplicate == arr[k][i] && j != k) {
                        duplicates.add(arr[k][i]);
                    }
                }
            }
        }
        if (duplicates.isEmpty()) return answer+1;

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < 5; j++) {
                for (int x:duplicates) {
                    if (x == arr[i][j])
                        count ++;
                }
                if (count == duplicates.size()) {
                    answer = i;
                    break;
                }
            }
        }
        return answer;
    }

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

 

강의 풀이(Time: 202ms Memory: 29MB)

1. 인덱스는 zero base 기반이기 때문에, 학년(1학년~5학년)과 학생(1번 학생~n번 학생)을 따졌을때 1부터 시작하는게 좋다.

2. 그래서 입력값 받아서 int[][]배열을 만들때 가장자리에 임시로 0을 만들어줘야 한다 

0 0 0 0 0 0 
0 2 3 1 7 3
0 4 1 9 6 8
0 5 5 2 4 4
0 6 5 2 6 7 --> 4번 학생
0 8 4 2 2 2

3. 1번학생과 그 다음학생을 비교하기 위해 2중 for문을 돌립니다. 그리고 학년을 비교하기 위에 내부에 for문을 추가합니다

4. i학생의 k학년 반과 j학생의 k학년 반이 같으면 cnt++하고 break해줍니다.

import java.util.Arrays;
import java.util.Scanner;

public class Answer {

    public int solution(int n, int[][] arr) {
        int ans = 0, max = Integer.MIN_VALUE;

        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= 5; k++) {
                    // i학생의 k학년의 반과 j학생의 k학년의 반이 같으면
                    if (arr[i][k] == arr[j][k]) {
                        cnt++;
                        break; // 중요하다~
                    }
                }
            }
            if (cnt > max) {
                max = cnt;
                ans = i;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n+1][6];
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= 5; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        System.out.println(T.solution(n,arr));
    }
}

강의를 듣기 전에 내가 풀었을때는 2학년(k)때 3번학생(j)과 4번학생(i)이 같고

3학년(k)때도 3번학생(j)과 4번학생(i)이 같은 경우를 카운팅 했었습니다.

 

그런데 같았던 횟수를 구하는게 아니고, 같았던 학생의 명수를 구하는거라서 한번 같았으면 break해야 합니다.

 다시 말해서, i와 j가 고정된 상태에서 k를 순회하는 중에 한번이라도 같으면 break를 합니다.

 

알고리즘 문제를 풀 때 2차원 배열을 순회하는 것은 중요한 스킬 중 하나입니다.
다음은 2차원 배열 순회에 대한 몇 가지 기본적인 개념과 팁입니다.

1. 행 먼저, 열 먼저 결정하기:대부분의 2차원 배열 순회 문제에서는 행(row)을 먼저 순회하고, 그 안에서 열(column)을 순회하는 것이 일반적입니다. 이러한 순서를 선택하면 문제를 해결하는 데 도움이 됩니다.

2. 중첩 반복문 사용:2차원 배열을 순회하려면 중첩된 반복문을 사용해야 합니다. 바깥쪽 반복문은 행을 나타내고, 안쪽 반복문은 열을 나타냅니다.

3. 순회 방향 결정하기:2차원 배열을 순회할 때, 행을 먼저 순회하는지 열을 먼저 순회하는지, 또는 특정한 패턴을 따라 순회하는지를 결정해야 합니다. 이는 문제의 요구사항에 따라 다를 수 있습니다.

4. 인덱스 범위 설정:중요한 부분 중 하나는 인덱스 범위를 올바르게 설정하는 것입니다. 행과 열의 개수를 알고 있다면, 인덱스가 범위를 벗어나지 않도록 조건을 검사해야 합니다.

5. 문제 요구사항 이해:문제를 잘 읽고, 2차원 배열 순회 과정에서 어떤 작업을 수행해야 하는지 이해하는 것이 중요합니다. 문제의 요구사항을 명확히 이해하고 해당 작업을 반복문 안에서 구현하세요.