SWEA[3378] - 스타일리쉬 들여쓰기 [D4]

링크

SWEA[3378]

문제설명

• 특정 조건을 만족하는 R,C,S쌍을 찾는다

문제풀이

• 부정방정식의 해를 구한다
  • 부정방정식의 특징
  • 해가 여러개일 수 있음
  • a+b+c=0, a+b-c=2 일 때
  • a+b = 1 로 고정값을 가진다. 이러한 경우도 고려해야함.
• 결국 그냥 모~든경우 완전탐색

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution3378 {

    public static int[] temp_rcs;
    public static int[] ans_rcs;

    public static int[][] br_cnt;
    public static int[] dot_cnt;

    public static int[][] my_br_cnt;
    public static int[] my_dot_cnt; 

    public static int p;
    public static int q;

    public static boolean anscnt=false;

    public static int count(String line, char brace) {
        int len = line.length();
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if(line.charAt(i)==brace)ans++;
        }
        return ans;
    }

    public static int dot_count(String line) {
        int len = line.length();
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if(line.charAt(i)=='.')ans++;
            else {
                break;
            }
        }
        return ans;
    }

    public static void Search(int cnt) {
        if(cnt==3) {
//            temp_rcs[0]*(br_cnt[i][1]-br_cnt[i][0]) +
//            temp_rcs[1]*(br_cnt[i][3]-br_cnt[i][2]) +
//            temp_rcs[2]*(br_cnt[i][5]-br_cnt[i][4]) =
//            dot_cnt[i] = dot_count(master[i]);
//            가 성립이 되는 rcs[0],rcs[1],rcs[2] 짝을 찾아야 한다.
//            조건이 성립하면
            boolean right = true;
            for (int i = 0; i < p-1; i++) {
                if(    temp_rcs[0]*(br_cnt[i][0]-br_cnt[i][1]) +
                    temp_rcs[1]*(br_cnt[i][2]-br_cnt[i][3]) +
                    temp_rcs[2]*(br_cnt[i][4]-br_cnt[i][5]) !=
                    dot_cnt[i+1]){  
                    right=false;
                }
            }
            if(right) {
                ans_rcs = temp_rcs.clone();
//                ans_rcs 기준으로 my_dot_cnt에 설정한다.
                int temp;
//                처음 할당하는 경우
                if(!anscnt) {
                    anscnt=true;
                    for (int i = 0; i < q-1; i++) {
                        temp=0;
                        for (int j = 0; j < 3; j++) {
                            temp += ans_rcs[j]*(my_br_cnt[i][j*2+0]-my_br_cnt[i][j*2+1]);
                        }
                        my_dot_cnt[i+1]=temp;
                    }
                }
//                이미 할당된 경우
                else {
                    for (int i = 0; i < q-1; i++) {
                        temp=0;
                        for (int j = 0; j < 3; j++) {
                            temp += ans_rcs[j]*(my_br_cnt[i][j*2+0]-my_br_cnt[i][j*2+1]);
                        }
//                        다른 띄어쓰기 값이 나온다면
                        if(my_dot_cnt[i+1]!=temp) {
                            my_dot_cnt[i+1]=-1;
                        }
                    }
                }
            }
            return;
        }

        for (int i = 1; i <= 20; i++) {
            temp_rcs[cnt]=i;
            Search(cnt+1);
        }
    }


    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/3378.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            p = Integer.parseInt(st.nextToken());
            q = Integer.parseInt(st.nextToken());

            String[] master = new String[p];
            String[] my = new String[q];
            for (int i = 0; i < p; i++) {
                master[i]=br.readLine();
            }
            for (int i = 0; i < q; i++) {
                my[i]=br.readLine();
            }

            ans_rcs = new int[3];
            temp_rcs = new int[3];
            br_cnt = new int[p][6];
            dot_cnt = new int[p];

            for (int i = 0; i < p; i++) {
                if(i>0) {
                    for (int j = 0; j < 6; j++) {
                        br_cnt[i][j] += br_cnt[i-1][j];
                    }
                }

                br_cnt[i][0] += count(master[i], '(');
                br_cnt[i][1] += count(master[i], ')');
                br_cnt[i][2] += count(master[i], '{');
                br_cnt[i][3] += count(master[i], '}');
                br_cnt[i][4] += count(master[i], '[');
                br_cnt[i][5] += count(master[i], ']');
            }

            for (int i = 0; i < p; i++) {
                dot_cnt[i] = dot_count(master[i]);
            }
//            temp_rcs[0]*(br_cnt[i][1]-br_cnt[i][0]) +
//            temp_rcs[1]*(br_cnt[i][3]-br_cnt[i][2]) +
//            temp_rcs[2]*(br_cnt[i][5]-br_cnt[i][4]) =
//            dot_cnt[i] = dot_count(master[i]);
//            가 성립이 되는 rcs[0],rcs[1],rcs[2] 짝을 찾아야 한다.

            my_br_cnt = new int[q][6];
            my_dot_cnt = new int[q];

            for (int i = 0; i < q; i++) {
                if(i>0) {
                    for (int j = 0; j < 6; j++) {
                        my_br_cnt[i][j] += my_br_cnt[i-1][j];
                    }
                }

                my_br_cnt[i][0] += count(my[i], '(');
                my_br_cnt[i][1] += count(my[i], ')');
                my_br_cnt[i][2] += count(my[i], '{');
                my_br_cnt[i][3] += count(my[i], '}');
                my_br_cnt[i][4] += count(my[i], '[');
                my_br_cnt[i][5] += count(my[i], ']');
            }

            Search(0);

            System.out.print("#"+test_case+" ");
//            System.out.println(Arrays.toString(ans_rcs));
//            System.out.println(Arrays.toString(my_dot_cnt));
            for (int i = 0; i < q; i++) {
                System.out.print(my_dot_cnt[i]+" ");
            }
            System.out.println();
//            초기화
            anscnt=false;
        }
    }
}

아쉬운점

• 더러워서 안풀었었음
  • 그냥 완전탐색문제라는걸 깨닫는데 시간이 좀 걸렸음
  • 문제 제대로 읽었으면 1<=R,C,S<=20 조건 보고 깨달았을텐데
• 부정방정식의 특징 고려 안함
  • r, c, s 각각 쌍이 여러개가 있다면 그냥 r,c,s 각각 -1로 고정시키고 무시했었음.
  • r(a-b)+ c(c-d) +s(e-f)에서 (a-b)가 0인 경우만 고려했었음
  • r+c 이런게 고정값이 나오는 경우가 있음.
    • #8 같은 경우는 값이 다른 rcs쌍이 있더라도, 들여쓰기의 답은 고정되는 경우가 있음.
    • r+c+s=0, r+c-s=2 일 때
    • r+c = 2 로 고정값을 가진다. 이러한 경우도 고려해야함.
    • 즉 나의 스타일 들여쓰기의 경우를 여러개 검사하면서 다른 경우가 나올때만 -1로 설정해주면됨.
• 초기화 실수
  • anscnt(해가 나왔었는지 안나왔었는지)

잘한점

• O(N) = (R,C,S) = 20^3 = 시간초과안걸림
• 인덱스 오류 안생김
  • 이전 줄만 고려해서 하기 때문에 for 문 돌 때 p-1, q-1 이렇게 해야함.
• 괄호갯수, '.'의 갯수만 고려해서 문제 풀었음
• 문제 적당히 읽음
  • 괄호갯수 누적처리 했음
• 시간(1:15)