모의고사

Posted on Edited on In , ,

문제정의

수포자 3명의 찍기 패턴이 주어지고 정답이 주어질 때 가장 문제를 많이 맞춘 수포자를 찾아내면 되는 문제이다.

문제풀이

수포자들의 찍기 패턴이 주어져있지만 이 패턴은 시간복잡도를 최적화하는 것과는 관련이 없다. 결국 모두 봐야한다.

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;

public class Test {

    public static void main(String[] args)
    {
        int[] answers = {1,2,3,4,5};
        int[] student1 = {1, 2, 3, 4, 5};
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int[] result = {0, 0, 0};
        int[] idx = {0, 0, 0};
        for(int ans : answers)
        {
            if(ans == student1[idx[0]])
                result[0]++;
            if(ans == student2[idx[1]])
                result[1]++;
            if(ans == student3[idx[2]])
                result[2]++;
            
            idx[0]++;
            idx[1]++;
            idx[2]++;
            
            idx[0] %= 5;
            idx[1] %= 8;
            idx[2] %= 10;
            
            
        }
        int max = 0;
        for(int cnt : result)
        {
            if(max < cnt)
                max = cnt;
        }
        Vector<Integer> v = new Vector<Integer>();
        for(int i = 0; i < 3; i++)
        {
            if(max == result[i])
                v.add(i);
                
        }
        int[] answer = new int[v.size()];
        for(int i = 0; i < v.size(); i++)
        {
            answer[i] = Integer.parseInt(v.get(i).toString()) + 1;
        }

    }
    
}

부분부분 살펴보자

1
2
3
4
5
6
int[] answers = {1,2,3,4,5};
int[] student1 = {1, 2, 3, 4, 5};
int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
int[] result = {0, 0, 0};
int[] idx = {0, 0, 0};

수포자 1,2,3의 패턴을 담은 student배열을 만들었다. result배열에는 학생의 시험 점수를 담는 배열이고 idx는 각 패턴배열에서 몇번째를 봐야하는지 나타내는 배열이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int ans : answers)
{
    if(ans == student1[idx[0]])
        result[0]++;
    if(ans == student2[idx[1]])
        result[1]++;
    if(ans == student3[idx[2]])
        result[2]++;
    
    idx[0]++;
    idx[1]++;
    idx[2]++;
    
    idx[0] %= 5;
    idx[1] %= 8;
    idx[2] %= 10;
    
    
}

정답을 맞춰보는 코드이다. 만약 학생들의 찍기와 맞다면 result값을 올린다. idx를 증가한다. 이때 나머지 연산통해 배열의 사이즈를 벗어나서 참조하지 않도록 한다. 이 부분의 시간복잡도는 answers의 길이를 n이라 할 때 \(O(n)\)이다.

1
2
3
4
5
6
int max = 0;
for(int cnt : result)
{
    if(max < cnt)
        max = cnt;
}

시험결과중 가장 높은 점수를 max에 저장한다. 이 때 result의 길이는 3으로 고정되어 있기 때문에 시간복잡도는 \(O(1)\)이다.

1
2
3
4
5
6
7
8
9
10
11
12
Vector<Integer> v = new Vector<Integer>();
for(int i = 0; i < 3; i++)
{
    if(max == result[i])
        v.add(i);
        
}
int[] answer = new int[v.size()];
for(int i = 0; i < v.size(); i++)
{
    answer[i] = Integer.parseInt(v.get(i).toString()) + 1;
}

result중에 max값과 같은 경우가 있다면 해당 학생을 벡터 v에 넣는다. c++에선 벡터를 주로 사용하였기 때문에 벡터를 썼는데, 자바에서는 벡터보다는 어레이리스트가 많이 쓰인다고 한다. 속도면에서 차이가 있다고 하는데 다음에는 어레이리스트로 작성해봐야겠다. 벡터는 Integer형식이기 때문에 int로 바꿔주는 작업과 동시에 +1을 해준다. 수포자0,1,2가 이나라 수포자 1,2,3이기 때문이다. 이 부분의 시간복잡도는 최대 3으로 고정되므로 \(O(1)\)이다.

최종 시간복잡도는 \(O(n)\)이다.

테스트