leeso

문제

https://leetcode.com/problems/first-bad-version/

n개의 버전[1, 2, ..., n]이 있고 첫 번째 불량 버전을 찾은 그 이후 다음 버전은 모두 불량이다.

버전이 잘못된지 여부를 반환하는 API bool isBadVersion(version) 이 제공된다.

API에 대한 호출 수를 최소화하여 첫 번째 불량 버전을 찾는 기능을 구현해야 된다.

풀이

1. 전체 버전에서 첫 번째와 마지막 버전을 지정한다.
2. 가장 중앙 버전의 불량여부를 확인한다.
3. 중앙 버전이 불량인 경우,
   1. 해당 제품의 이전 제품이 정상인 경우, 중앙값 리턴,
   2. 이전 제품도 불량이라면, 중앙제품 이전 제품을 마지막 버전으로 설정한다.
4. 중앙 버전이 정상인 경우 중앙 다음 제품을 최초 제품으로 설정한다.

Java Code

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n==1) return 1;        
        
        int begin = 1;
        int end = n;
        int mid = (end - begin) / 2 + begin;
        
        while(true){
            if(isBadVersion(mid)){
                
                if(!isBadVersion(mid-1)){
                    return mid;
                } else {
                    end = mid-1;
                    mid = (end-begin) / 2 + begin;
                }
                
            } else {
                
                begin = mid+1;
                mid = (end-begin) / 2 + begin;
                
            }
        }
    }
}

문제

https://www.acmicpc.net/problem/1316

공부한 부분

최초 생각 : 해시에다가 일단 넣고, 스택에다가 넣은거 빼면서 비교하자
1. 해시셋에 입력, 이때 스택에도 같이 넣어줌 (스택 사용해서 문자 연속으로 나오는것 확인을 위해)

2. 스택에서 알파벳을 한개씩 빼서 이전의 알파벳과 같은지 검사해서 다른 경우의 개수를 세어준다.

3. 이때의 개수가 해시셋에 있는 개수와 같으면 그룹단어

Java Code

package week2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Stack;
import java.util.StringTokenizer;

public class boj1316 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //해시에다가 일단 넣고, 스택에다가 넣은거 빼면서 비교?

        int answer = 0;
        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());

            String input = st.nextToken();
            char[] arr = input.toCharArray();
            HashSet<Character> hs = new HashSet();
            Stack<Character> stack = new Stack<>();

            for (int j = 0; j < arr.length; j++) {
                hs.add(arr[j]);
                stack.push(arr[j]);
            }

            char temp1 = stack.pop();
            int count = 0;

            while (!stack.isEmpty()){

                char temp2 = stack.pop();
                if (temp1 != temp2) {
                    count++;
                    //System.out.println("count "+count);
                }
                temp1 = temp2;
            }

            if (count == hs.size()-1) {
                answer++;
            }


        }
        System.out.println(answer);
    }
}

문제

https://www.acmicpc.net/problem/11660

공부한 부분

2차원 배열일 때 구간합 구하는 법에 대해 공부했다.

1. 2차원 구간 합 배열 D[X][Y] 정의

D[X][Y] = 원본 배열의 (0,0)부터 (X,Y)까지의 사각형 영역 안에 있는 수의 합

2. D[i][j]의 값을 채우는 구간 합 공식

D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

3. 질의 X1,Y1,X2,Y2에 대한 답을 구간합으로 구하는 방법

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] sum = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + map[i][j];
            }
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int X1 = Integer.parseInt(st.nextToken());
            int Y1 = Integer.parseInt(st.nextToken());
            int X2 = Integer.parseInt(st.nextToken());
            int Y2 = Integer.parseInt(st.nextToken());
      
            int answer = sum[X2][Y2] - sum[X1 - 1][Y2] - sum[X2][Y1 - 1] + sum[X1 - 1][Y1 - 1];
            System.out.println(answer);
        }
    }
}

문제

https://www.acmicpc.net/problem/11659

공부한 부분

구간합 구하는 법에 대해 공부했다.

1. 합 배열을 구한다.

S[i] = S[i-1]+A[i]

2. 구간 합을 구한다.

구간합 = S[j] - S[i]

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_003_11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] num = new int[N+1];
        int sum = 0;
        int[] sumArr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            sum += num[i];
            sumArr[i] = sum;
        }
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            System.out.println(sumArr[B]-sumArr[A-1]);

        }
    }
}

문제

https://www.acmicpc.net/problem/1546

풀이

방법1. 

처음에는 입력을 받으면서 최대값을 구하고,

입력된 모든 값을 점수/M*100으로 고치면서 총합을 구해서 평균을 구했는데 이렇게 되면 for문을 2번 돌게 된다.

방법2.

어차피 (A/M*100+B/M*100+C/M*100)/3 = (A+B+C)/M*100 이니까 for문 한번에 해줄 수 있었다. (2번째 방법)

Java Code (방법1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_002_1546 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        double[] score = new double[N];
        double max = Double.MIN_VALUE;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < score.length; i++) {
            score[i] = Double.valueOf(st.nextToken());
            max = Math.max(score[i],max);
        }
        double sum = 0.0;
        double[] changedScore = new double[N];
        for (int i = 0; i < score.length; i++) {
            changedScore[i] = score[i]/max*100;
            sum +=changedScore[i];
        }

        System.out.println(sum/N);
    }
}

Java Code (방법2)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_002_1546_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        double[] score = new double[N];
        double max = Double.MIN_VALUE;
        double sum = 0.0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < score.length; i++) {
            score[i] = Double.valueOf(st.nextToken());
            max = Math.max(score[i],max);
            sum += score[i];
        }
        double answer = sum/max*100/N;


        System.out.println(answer);
    }
}

문제

https://www.acmicpc.net/problem/11720

N개의 숫자가 공백 없이 쓰여있을 때, 숫자의 합을 출력하는 문제

공부한 부분

1. 공백 없이 숫자가 주어질 때 입력 값 받는 방법

12345 이런식으로 입력이 주어지고, 1,2,3,4,5 숫자를 따로 사용해야 할 때

일단 String 값으로 12345를 받고, char형 배열에 toCharArray를 사용해서 분리해준 후

해당 char형 값에 -'0' 해주어 int 값으로 바꿔준다.

숫자 CHAR(0~9)는 ASCII 코드 48부터 시작하므로, 48을 빼주면 숫자를 얻을 수 있다.

char c = '5';
int n = 0;
n = c - 48;

char c = '5';
int n = 0;
n = c - '0';

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int N = Integer.parseInt(br.readLine());
        String sNum = br.readLine();
        char[] cNum = sNum.toCharArray();

        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += cNum[i]-'0';
        }
        System.out.println(sum);
    }
}

1. 글씨가 전부다 같은 경우 : -1
2. 글씨가 전부다 다른 경우 : 글자 수
3. 팰린드롬인 경우 : 글자수 -1 3가지 경우의 수로 나눠서 코드 짜면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class boj15927 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        char[] arr = str.toCharArray();
        HashSet<Character> hs = new HashSet<>();
        for (int i = 0; i < arr.length / 2; i++) {
            hs.add(arr[i]);
            if (arr[i] != arr[arr.length - 1 - i]) {
                System.out.println(arr.length);
                return;
            }
        }
        for (int i = arr.length / 2; i < arr.length; i++) {
            hs.add(arr[i]);
        }
        if(hs.size()==1){
            System.out.println(-1);
        }else{
            System.out.println(arr.length-1);
        }

    }
}

문제 링크

문제 설명

풀이 방법

풀이 코드

package week1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ_2493 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(st.nextToken());
            while (!stack.isEmpty()) {
                if (stack.peek()[0] > input) {
                    System.out.println(stack.peek()[1] + " ");
                    break;
                } else {
                    stack.pop();
                }
            }
            if (stack.isEmpty()) {
                System.out.println("0 ");
            }
            stack.add(new int[]{input , i + 1});
        }

    }
}

문제링크

문제 설명

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열 중 원소의 합이 가장 큰 부분 배열 구하기(X의 연속한 일부분)

풀이 방법

구간합 구하는 문제가 주어지면, 누적합을 먼저 떠올린다.

누적 합 < 0이 되는 구간에 dp값을 0으로 초기화해준다. 

누적합이 음수가 되는 순간 그 뒤에 있는 수들은 새로운 누적합(0)을 구하는게 더 최댓값을 가져오기 때문이다.

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[] num = new int[N];
            int[] dp = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }
            int max = num[0];
            dp[0]=num[0];
            for (int i = 1; i < num.length; i++) {
                if(dp[i-1]<0){
                    dp[i-1]=0;
                }
                dp[i]=dp[i-1]+num[i];
                max = Math.max(max,dp[i]);
            }
            System.out.println(max);
        }
    }
}

문제 링크 

문제 설명

1. C개의 알파벳 중 서로 다른 L개의 알파벳을 구해야한다.

* 이때 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야한다.

풀이 방법

1. 중복없이 L개를 뽑는 조합 구하기

* 이때 모음(a,e,i,o,u) 과 최소 두개의 자음으로 구성되어 있는지 확인한다.

N과 M(6) 번 문제에서 중복 없이 수열 구했던 문제를 활용했다.

dfs 함수 안에서 for문안의 i=0 부분을 start로 두어, 중복으로 선택하는 것을 피했다.

전체 코드

package week1;

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

public class boj1759 {

    static int L, C;
    static String[] ans;
    static String[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new String[C];
        ans = new String[L];
        visited = new boolean[C];

        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken();
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        dfs(0, 0);
    }

    private static void dfs(int index, int start) {

        if (index == L) {
            StringBuilder sb = new StringBuilder();
            int mo = 0, ja = 0;
            for (int i = 0; i < L; i++) {
                if (ans[i].equals("a") || ans[i].equals("e") || ans[i].equals("i") || ans[i].equals("o") || ans[i].equals("u")) {
                    mo++;
                } else {
                    ja++;
                }
                sb.append(ans[i]);
            }
            if (mo >= 1 && ja >= 2) {
                System.out.println(sb);
                return;
            } else {
                return;
            }

        }
        for (int i = start; i < C; i++) {
            if (!visited[i]) {
                visited[i] = true;
                ans[index] = arr[i];
                dfs(index + 1, i + 1);
                visited[i] = false;
            }

        }
    }
}