구름톤 챌린지: 2주차(230821~230822)

230821

Day6 문제풀이

코드

1. 첫번째 방법 : S를 매번 substring 하기

import java.io.*;
import java.util.*;

class Main {  
public static void main(String\[\] args) throws Exception {  
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    ArrayList<String> list = new ArrayList<>(); // 중복 없는 모든 부분 문자열

    int N = Integer.parseInt(br.readLine());
    String[][] input = new String[N][3]; // 각 문자열의 부분 문자열

    String S = br.readLine();

    // 부분문자열을 list에 추가 후 정렬
    for(int a=1; a<S.length()-1; a++) {
        for(int b=a+1; b<S.length(); b++) {
            String temp1 = S.substring(0, a);
            String temp2 = S.substring(a, b);
            String temp3 = S.substring(b, S.length());

            if(!list.contains(temp1)) list.add(temp1);
            if(!list.contains(temp2)) list.add(temp2);
            if(!list.contains(temp3)) list.add(temp3);
        }
    }
    Collections.sort(list);

    // 정렬 후 문자에 대한 점수 부여
    HashMap<String, Integer> map = new HashMap<>();
    for(int i=0; i<list.size(); i++) {
        map.put(list.get(i), i+1);
    }

    // 부분문자열의 최댓값 구하기
    int max = 0;
    for(int a=1; a<S.length()-1; a++) {
        for(int b=a+1; b<S.length(); b++) {
            String temp1 = S.substring(0, a);
            String temp2 = S.substring(a, b);
            String temp3 = S.substring(b, S.length());

            int sum = map.get(temp1) + map.get(temp2) + map.get(temp3);
            if(max < sum) max = sum;
        }
    }

    // 결과 출력
    System.out.print(max);
    }
}

2. 두번째 방법 : S를 substring한 결과를 저장해서 사용하기

import java.io.*;
import java.util.*;

class Main {  
public static void main(String\[\] args) throws Exception {  
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    ArrayList<String> list = new ArrayList<>(); // 중복 없는 모든 부분 문자열

    int N = Integer.parseInt(br.readLine());
    ArrayList<String[]> input = new ArrayList<String[]>(); // 각 문자열의 부분 문자열

    String S = br.readLine();

    // 부분문자열을 list에 추가 후 정렬
    int index = 0;
    for(int a=1; a<S.length()-1; a++) {
        for(int b=a+1; b<S.length(); b++) {                
            String temp1 = S.substring(0, a);
            String temp2 = S.substring(a, b);
            String temp3 = S.substring(b, S.length());
            String[] temp = {temp1, temp2, temp3};
            input.add(temp);    

            if(!list.contains(input.get(index)[0])) list.add(input.get(index)[0]);
            if(!list.contains(input.get(index)[1])) list.add(input.get(index)[1]);
            if(!list.contains(input.get(index)[2])) list.add(input.get(index)[2]);

            index++;
        }
    }
    Collections.sort(list);

    // 정렬 후 문자에 대한 점수 부여
    HashMap<String, Integer> map = new HashMap<>();
    for(int i=0; i<list.size(); i++) {
        map.put(list.get(i), i+1);
    }

    // 부분문자열의 최댓값 구하기
    int max = 0;
    for(int i=0; i<input.size(); i++) {
        String temp1 = input.get(i)[0];
        String temp2 = input.get(i)[1];
        String temp3 = input.get(i)[2];

        int sum = map.get(temp1) + map.get(temp2) + map.get(temp3);
            if(max < sum) max = sum;
    }

    // 결과 출력
    System.out.print(max);
    }
}

중요

• 문제를 풀이하는 도중 문자열 S를 substring해야하는 일이 두 번 발생한다. 이 때 java7 업데이트 이후 substring의 시간 복잡도가 O(n)이라는 것을 알게 되었고, S를 매번 substring 하지 않고 분할한 S를 미리 arraylist에 저장해두는 방법을 떠올려보았다.
  substring의 시간 복잡도가 O(n)인 것에 비해 arraylist의 시간 복잡도는 add와 get 모두 O(1)이다. 비록 arraylist 저장을 위한 index 변수와 arraylist 때문에 공간복잡도는 좀 늘어났지만, 시간복잡도는 줄었을 것이라 예상한다.

time-complexity-of-javas-substring : https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring
Runtime Complexity of Java Collections : https://gist.github.com/psayre23/c30a821239f4818b0709

230822

Day7 문제풀이

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        int K = Integer.parseInt(tk.nextToken());

        // 게임판 구성
        boolean[][] board = new boolean[N][N];
        for(int i=0; i<N; i++) {
            tk = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++) {
                board[i][j] = tk.nextToken().equals("1") ? true : false;
            }
        }

        // 깃발 개수 카운트
        int countK = 0;
        int[][] search = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                // 구름이 없는 칸일 경우
                if(!board[i][j]) {
                    int countCloud = 0;
                    for(int k=0; k<search.length; k++) {
                        try {
                            if(board[i+search[k][0]][j+search[k][1]]) countCloud++;
                        } catch(Exception e) {}
                    }
                    if(countCloud == K) countK++;
                }
            }
        }

        System.out.print(countK);
    }
}

중요

• board의 boolean값을 넣는데 사용하였다. 평소에는 가독성의 이유로 if-else문을 사용했지만, 이번 경우에는 오히려 삼항연산자의 가독성이 더 높았다. 학부 시절 삼항연산자는 가독성이 좋지 않으니 사용하는 것을 지양하라는 말을 들었지만, 이렇게 되려 가독성이 높아지는 곳이 있다면 사용하는 것이 좋을 것 같다.