2020 구글 코드잼 Qualification Round(QR) 참가 후기

PS(알고리즘)을 취미 겸 코딩테스트 준비정도로 가볍게 하고 있어서 그런지..

 

1~3 문제까지는 어떻게든 풀었으나, 4~5번 문제는 풀기 어려웠다.. 

 

Contestants with a final score of at least 30 points in this round will advance to Round 1.

forumQuestions(이번 라운드에선 30점이 기준이었습니다. 3번 문제까지 풀면 통과는 가능)

 

340명이 5번문제까지 완벽하게 풀었더라구요..

 

끝나면,

친절하게 풀이 및 설명과 제출 하신 분들의 코드를 볼 수 있어서 도움이 많이 된 듯 합니다.

 

1번 Vestigium 

 

라틴 방진에 대한 설명과 함께, 입력으로 NxN 행렬이 주어지면 대각합 k 와 라틴 방진의 조건인

1~N까지 사용한(만족한) 행 r / 열 c 값을 구하는 문제였습니다. 시간 제한이나 뭐 그런 측면에 널널하기도 했고 

 

그냥 무식하게 HashSet으로 row값과 col값을 넣어주어서 N인 경우 r,c의 값을 1 증가했습니다.

 

2번 Nesting depth

 

간단한 simple set은 0 1 의 값만 주어지고 심화문제는 0~9까지 값이 input으로 들어옵니다.

            StringBuilder sb = new StringBuilder();
            int i = 0;
            sb.append("Case #"+tc+": ");
            while(i<input.length()){
                int now = input.charAt(i)-'0';
                if(now!=0){
                    int cnt = 0;
                   for(int j=0;j<now;j++){
                       sb.append('(');
                       cnt++;
                   }

                   sb.append(now);
                   i++;
                   while(i<input.length()){
                       int tmp = input.charAt(i)-'0';
                       if(tmp==0){
                           break;
                       }
                       if(tmp==now){
                           sb.append(tmp);
                           i++;
                       }
                       else if(tmp>now){
                            int dif = tmp-now;
                            for(int j=0;j<dif;j++){
                                sb.append('(');
                                cnt++;
                            }
                            sb.append(tmp);
                            now = tmp;
                            i++;
                       }
                       else {
                            int dif = now - tmp;
                            for(int j=0;j<dif;j++){
                                sb.append(')');
                                cnt--;
                            }
                            sb.append(tmp);
                            now = tmp;
                            i++;
                       }

                   }
                   for(int j=0;j<cnt;j++){
                       sb.append(')');
                   }

                }
                else {
                    sb.append(now);
                    i++;
                }

            }

더 나은 풀이도 있겠지만, 그냥 무식하게 구했습니다. 

 

 

3. Parenting Partnering Returns

 

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of activities to assign. Then, N more lines follow. The i-th of these lines (counting starting from 1) contains two integers Si and Ei. The i-th activity starts exactly Si minutes after midnight and ends exactly Ei minutes after midnight.

 

J 랑 C  두명이서 Input으로 들어온 시간값들에 대해서 일정을 어떻게 수행할 지 정하는 문제.

대략 볼 때 시간을 S 기준으로 정렬하면 좋을 거 같다는 생각을 했습니다. 그리고 처음에 J와 C 에 List의 첫번 째와 두번 째를 넣고 

 

    public static boolean isAva(Point p, int n){
        if(p.y<=list.get(n).x){
            return true;
        }
        else {
            return false;
        }
    }

와 같은 시간을 J 와 C 가 가능한 지 보고, 둘 다 안된다면 끝내면서 IMPOSSIBLE을 찍도록 했습니다.

근데 문제는 정렬을 시켰기에, 처음 들어왔을 때의 일정 순서에 대해서 어떻게 처리할 지에 대해서 생각을 해야 됐습니다.

                for(int i=0;i<n;i++){
                    for(Point ans : answerList){
                        if(ans.idx==i){
                            jc.append(ans.name);
                            break;
                        }
                    }
                }
                answer.append(jc.toString());

그래서 index를 나타내는 값을 Point Class에 추가했고, 정답을 위해서 name(J또는 C)을 추가했습니다.

 

4. 

지문량과 이해하기 어려워서 못풀었습니다...

 

5.

시간을 줄어야 한다는 것을 느꼈지만 방법이 떠오르지 않아서 그냥 완전탐색처럼 구하니, 간단한 set은 통과가 가능했습니다.

 

코드는 다음과 같습니다.