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

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기

dp[i]: i에서 1로 만드는 데 걸리는 최소 연산 횟수

dp[i] = dp[i - 1] + 1
if(i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
if(i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)

3. 코드

package Baekjoon;

import java.io.IOException;
import java.util.Scanner;

public class S3_1463 {

  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] dp = new int[n + 1];
    //dp[x] = x에서 1로 만드는 최소 횟수

    dp[1] = 0;

    for (int i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + 1;
      if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
      if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }

    System.out.println(dp[n]);

  }//main
}//class

package Baekjoon;

import java.io.IOException;
import java.util.Scanner;

public class S3_1463 {

  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] dp = new int[n + 1];
    //dp[x] = x에서 1로 만드는 최소 횟수

    dp[2] = 1;
    dp[3] = 1;

    for (int i = 4; i <= n; i++) {
      dp[i] = dp[i - 1] + 1;
      if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
      if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }

    System.out.println(dp[n]);

  }//main
}//class

처음에는 이렇게 짰는데, n이 4 이하면 94%에서 index Error가 나서 실패한다!

실버 2 https://www.acmicpc.net/problem/11724

풀이

package Baekjoon;

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

public class S2_11724 {
  static ArrayList<Integer>[] close;
  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());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    close = new ArrayList[n + 1];
    visited = new boolean[n + 1];

    for (int i = 1; i < n + 1; i++) {
      close[i] = new ArrayList<>();
    }

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());

      close[u].add(v);
      close[v].add(u);
    }

    int cnt = 0;
    for (int i = 1; i < n + 1; i++) {
      if (!visited[i]) {
        cnt++;
        DFS(i);
      }
    }
    System.out.println(cnt);
  }

    static void DFS(int d) {
      if (visited[d]) {
        return;
      }
      visited[d] = true;
      for (int i : close[d]) {
        if (!visited[i]) {
          DFS(i);
        }
      }
    }
  }

실버 2 https://www.acmicpc.net/problem/12891

풀이

package Baekjoon;

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

public class S2_12891 {

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

    //s, p, ans
    int s = Integer.parseInt(st.nextToken());
    int p = Integer.parseInt(st.nextToken());
    int ans = 0;

    //dna
    st = new StringTokenizer(br.readLine());
    char[] dna = st.nextToken().toCharArray();

    //acgt 카운트
    int[] acgt = new int[4];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < 4; i++) {
      acgt[i] = Integer.parseInt(st.nextToken());
    }

    //첫번째 부분 문자열
    int start = 0;
    int end = p - 1;
    char[] first_arr = Arrays.copyOfRange(dna, start, end+1);

//    System.out.println(first_arr);

    //부분문자열의 acgt 개수 배열
    int[] cnt = new int[4];

    for (char f : first_arr) {
      count(f, cnt, 1);
    }

    if (cnt[0] >= acgt[0] && cnt[1] >= acgt[1] && cnt[2] >= acgt[2] && cnt[3] >= acgt[3]) {
      ans++;
    }

//    System.out.println(Arrays.toString(cnt));

    while (end + 1 < s) {
      count(dna[start], cnt, -1);
      start++;
      end++;
      //처음과 끝 카운트
      count(dna[end], cnt, 1);
//      System.out.println(dna[start] + " " + dna[end]);
//      System.out.println(Arrays.toString(cnt));

      if (cnt[0] >= acgt[0] && cnt[1] >= acgt[1] && cnt[2] >= acgt[2] && cnt[3] >= acgt[3]) {
        ans++;

      }
    }

    System.out.println(ans);

  }

  static void count(char c, int[] cnt_arr, int add) {
    if (c == 'A') {
      cnt_arr[0] += add;
    } else if (c == 'C') {
      cnt_arr[1] += add;
    } else if (c == 'G') {
      cnt_arr[2] += add;
    } else if (c == 'T') {
      cnt_arr[3] += add;
    }
  }
}

다른 풀이

package Baekjoon;

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

public class dfhjkd {

  static int[] cnt= new int['Z'+1];


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

    int S=Integer.parseInt(tokens.nextToken());
    int P=Integer.parseInt(tokens.nextToken());

    String Dna = input.readLine();

    int[] min_num=new int[4];

    int totalCnt = 0;

    tokens= new StringTokenizer(input.readLine());
    for(int i=0;i<4;i++) {
      min_num[i]=Integer.parseInt(tokens.nextToken());
    }

    for(int i=0;i<P;i++) {
      cnt[Dna.charAt(i)]++;
    }

    if(isAble(min_num)) {
      totalCnt++;
    }

    for(int i=0;i<S-P;i++) {
      cnt[Dna.charAt(i)]--;
      cnt[Dna.charAt(i+P)]++;

      if(isAble(min_num)) totalCnt++;

    }

    System.out.println(totalCnt);

  }

  static boolean isAble(int[] min_num) {
    return cnt['A']>=min_num[0] && cnt['C']>=min_num[1] && cnt['G']>=min_num[2] && cnt['T']>=min_num[3];
  }


}

이런 방법이.,..

실버 5 https://www.acmicpc.net/problem/2018

풀이

package Baekjoon;

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

public class S5_2018 {

  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 start = 1;
    int end = 2;
    int sum;
    int answer = 1;

    while (start < n / 2 + 1) {
      sum = (start + end) * (end - start + 1) / 2;

      if (sum < n) {
        end++;
      }
      else if (sum == n) {
        answer++;
        start++;
        end = start + 1;
      }
      else {
        start++;
        end = start + 1;
      }
    }

    System.out.println(answer);
  }

}

등차수열의 합

(start + end) * (end - start + 1) / 2

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기

• 나타내는 방법에 숫자 그대로도 있기 때문에 count를 1로 초기화
• start_index를 오른쪽으로 한 칸 이동 == 연속된 자연수에서 왼쪽 값 삭제
• end_index를 오른쪽으로 한 칸 이동 == 연속된 자연수의 범위 한 칸 더 확장

2. 슈도코드

3. 코드

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int count = 1;
    int start_index = 1;
    int end_index = 1;
    int sum = 1;

    while (end_index != n) {
      if (sum == n) {
        count++;
        end_index++;
        sum += end_index;
      } else if (sum > n) {
        sum -= start_index;
        start_index++;
      } else {
        end_index++;
        sum += end_index;
      }
    }
    System.out.println(count);

골드 3 https://www.acmicpc.net/problem/10986

풀이

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
//import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class G3_10986 {

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

    //n, m, ans
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    long ans = 0;

    //n개의 수 배열
    ArrayList<Integer> input = new ArrayList<>();

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      input.add(Integer.parseInt(st.nextToken()));
    }

    //누적합 배열
    long[] sum = new long[n+1];
    for (int i = 1; i <= n; i++) {
      sum[i] = sum[i - 1] + input.get(i-1);
    }

    //나머지 배열
    ArrayList<Long> rest = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
      rest.add(sum[i] % m);

    }

    //나머지 배열에 0이 있을 경우 개수 1 더하기
    for (long r: rest) {
      if (r == 0) {
        ans += 1;
      }
    }

    //나머지 배열에서 개수 구하기
    //나머지 배열 중복제거
    List<Long> done = rest.stream().distinct().collect(Collectors.toList());
    for (long d : done) {
      long cnt = Collections.frequency(rest, d);  //배열에서 개수 구하기
      ans += (cnt * (cnt - 1) / 2);
    }
    System.out.println(ans);
  }
}

누적합을 구한 이유 -> 부분합을 구하기 위해서 -> 누적합에서 부분합 구하는 방법은 S[j]-S[i-1]

두 수를 각각 m으로 나눴을때의 나머지가 같으면 두 수를 뺀 값도 나머지가 0일 것이다

누적합의 나머지를 구해보면 1 0 0 1 0

0이면 나누어떨어지는 거라서 답에 더해주기

0 세개 -> 두 개 아무거나 골라서 서로 빼더라도 0이라는 거니까 -> 3C2 1로 똑같은거 두개는 2C2

mCn일 때 공식이 m*(m-1) // 2 n이 2로 고정 -> 부분합 구할때 두개의 인덱스만 필요하기 때문에

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기 (A+B) % C 는 ((A%C) + (B%C)) % C랑 같다.

2. 슈도코드

3. 코드

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    long[] S = new long[n];
    long[] C = new long[m];
    long answer = 0;
    //바로 입력받아서 합 배열 만들기
    S[0] = sc.nextInt();
    for (int i = 1; i <= n; i++) {
      S[i] = S[i - 1] + sc.nextInt();
    }
    for (int i = 0; i < n; i++) {
      int remainder = (int) (S[i] % m);
      //구간합 자체가 0일때 정답에 더하기
      if (remainder == 0) answer++;
      //나머지에 해당하는 인덱스 개수 카운팅
      C[remainder]++;
    }
    for (int i = 0; i < m; i++) {
      if (C[i] > 1) {
        answer += C[i] * (C[i] - 1) / 2;
      }
    }
    System.out.println(answer);

나머지가 같은 인덱스의 개수 카운팅하는 방법

추가

계산 과정에서 int형이 저장할 수 없는 범위의 값이 나오면 틀린 결과가 나올 수 있다. long형으로 선언하면 오류가 발생하지 않는다.

여담

아이디어 떠올리기도 어려웠는데 그 와중에 계속 int로 해서 계속 틀림 ㅎㅎㅎ ㅎ ㅎㅎ ㅎ

스탠다드 백준 10807: 개수 세기

브론즈 3 - 백준 2562: 최댓값

2 - 백준 11720: 숫자의 합

1 - 백준 1546: 평균

1 - 백준 13322: 접두사 배열

실버 5 - 백준 2167: 2차원 배열의 합

5 - 백준 11728: 배열 합치기

5 - 백준 25966: 배찬우는 배열을 좋아해

4 - 백준 11656: 접미사 배열

4 - 백준 1337: 올바른 배열

3 - 백준 11659: 구간 합 구하기 4

1 - 백준 11660: 구간 합 구하기 5

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

풀이

package Baekjoon;

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

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

    //n, m 입력
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    ArrayList<int[]> sumList = new ArrayList<>();
    int[] sum;

    //행렬 입력
    int[][] matrix = new int[n][n];

    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        matrix[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    for (int[] arr : matrix) {
      //합배열 만들기
      sum = new int[n+1];
      for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + arr[i-1];
      }
      sumList.add(sum);
    }

    //구해야하는 합배열
    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 result = 0;

      for (int x = x1-1; x <= x2-1; x++) {
        int[] rowSum = sumList.get(x);
        result += rowSum[y2] - rowSum[y1-1];
      }
      sb.append(result + "\n");
    }
    System.out.print(sb);

  }
}

시간 초과가 떠서 아예 알고리즘을 수정했다. 2차원 배열에서 행 별로 합 배열을 만들고, 입력 인덱스만큼의 값만 누적해서 result에 더하고 출력했다.

시간 초과 풀이

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());
    StringBuilder sb = new StringBuilder();

    //n, m 입력
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    //행렬 입력
    String[][] matrix = new String[n][n];

    for (int i = 0; i < n; i++) {
      matrix[i] = br.readLine().split(" ");
    }

    //질의 입력
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int x1 = Integer.parseInt(st.nextToken()) - 1;
      int y1 = Integer.parseInt(st.nextToken()) - 1;
      int x2 = Integer.parseInt(st.nextToken()) - 1;
      int y2 = Integer.parseInt(st.nextToken()) - 1;
      int sum = 0;

      for (int x = x1; x <= x2; x++) {
        for (int y = y1; y <= y2; y++) {
          sum += Integer.parseInt(matrix[x][y]);
        }
      }
      sb.append(sum + "\n");
    }
    System.out.print(sb);
  }
}

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기 질의 개수가 100,000이므로 질의마다 합을 구하면 안되고, 구간 합 배열을 이용해야 한다.

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

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

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

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

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

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

2. 슈도코드

3. 코드

public class S1_11660 {
  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 A[][] = new int[N+1][N+1];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        A[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    int D[][] = new int[N+1][N+1];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[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 result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
      System.out.println(result);

      }
  }
}

사실 공식 부분 제대로 이해못했다. ㅎ헤헤

실버 4 https://www.acmicpc.net/problem/1337

풀이

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class S4_1337 {

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

    int n = Integer.parseInt(br.readLine());
    ArrayList<Integer> list = new ArrayList<>();

    for (int i = 0; i < n; i++) {
      list.add(Integer.parseInt(br.readLine()));
    }

    Collections.sort(list);

    int[] cnt = new int[n];

    for (int i = 0; i < n; i++) {
      for (int j = 1; j < 5; j++) {
        if (!list.contains(list.get(i) + j)) {
          cnt[i]++;
        };
      }
    }

// 정렬해서 맨처음 값 출력하기
//    Arrays.sort(cnt);
//    System.out.println(cnt[0]);

    int min = cnt[0];
    for (int c : cnt) {
      if (c <= min) {
        min = c;
      }
    }
    System.out.println(min);
  }
}

배열의 각 요소마다 1, 2, 3, 4, 5를 더한 값이 입력 리스트에 있는지 비교했다. 없는만큼 개수를 1 더했고, 최종적으로 개수 리스트의 최소값을 출력했다.

여담

효율 생각해서 어렵게 접근하니까 잘 안풀렸다... 감 잡는데 좀 오래걸림...

실버 4 https://www.acmicpc.net/problem/11656

풀이

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class S4_11656 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    ArrayList<String> strList = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < str.length(); i++) {
      strList.add(str.substring(i));
    }
    Collections.sort(strList);

    for (String s : strList) {
      sb.append(s + "\n");
    }
    System.out.print(sb);
  }
}

substring 이용하니까 쉽다!

실버 5 https://www.acmicpc.net/problem/25966

풀이

package Baekjoon;

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

public class S5_25966 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //개수 입력
    StringTokenizer st = new StringTokenizer(br.readLine());
    StringBuilder sb = new StringBuilder();
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());

    //행렬 입력
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < m; j++) {
        matrix[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    //쿼리 입력
    for (int c = 0; c < q; c++) {
      st = new StringTokenizer(br.readLine());
      int first = Integer.parseInt(st.nextToken());
      int i = Integer.parseInt(st.nextToken());
      int j = Integer.parseInt(st.nextToken());

      if (first == 0) {
        int k = Integer.parseInt(st.nextToken());
        matrix[i][j] = k;
      }
      else {
        int[] tmp = matrix[i];
        matrix[i] = matrix[j];
        matrix[j] = tmp;
      }
    }
    //출력
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        sb.append(matrix[i][j] + " ");
      }
      sb.append("\n");
    }
    System.out.print(sb);
  }
}

여담

배찬우씨... 계속계쏙계속 시간 초과가 떠서 열받았다... StringBuilder의 중요성을 깨달았따....

실버 5 https://www.acmicpc.net/problem/11728

풀이

package Baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class S5_11728 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    ArrayList<Integer> list = new ArrayList<>();

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      list.add(Integer.parseInt(st.nextToken()));
    }

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < m; i++) {
      list.add(Integer.parseInt(st.nextToken()));
    }
    Collections.sort(list);

    for (int l : list) {
      bw.write(l + " ");
    }
    bw.flush();
    bw.close();
    br.close();
  }
}

각각 입력받아서 하나의 ArrayList에 바로 추가했다. 배열 크기가 1,000,000개까지 가능해서 BufferedWriter로 처리했다. bw.flush와 bw.close는 반드시 해줘야 한다!

추가

BufferedReader, BufferedWriter를 활용한 빠른 입출력 https://coding-factory.tistory.com/251

실버 5 https://www.acmicpc.net/problem/2167

풀이

package Baekjoon;

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

public class S5_2167 {
  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());

    // 2차원 배열 생성
    int[][] arr = new int[n][m];

    for (int p = 0; p < n; p++) {
      st = new StringTokenizer(br.readLine());
      for (int q = 0; q < m; q++) {
        arr[p][q] = Integer.parseInt(st.nextToken());
      }
    }

    st = new StringTokenizer(br.readLine());
    int k = Integer.parseInt(st.nextToken());

    for (int num = 0; num < k; num++) {
      st = new StringTokenizer(br.readLine());
      int i = Integer.parseInt(st.nextToken()) - 1;
      int j = Integer.parseInt(st.nextToken()) - 1;
      int x = Integer.parseInt(st.nextToken()) - 1;
      int y = Integer.parseInt(st.nextToken()) - 1;
      int sum = 0;

      // i~x, j~y
      for (int p = i; p <= x; p++) {
        for (int q = j; q <= y; q++) {
          sum += arr[p][q];
        }
      }
      System.out.println(sum);
    }
  }
}

여담

2차원 배열의 합을 구하는 방법이 헷갈렸는데, 해당하는 인덱스만큼만 돌면서 더해주면 되는거였다!

브론즈 1 https://www.acmicpc.net/problem/13322

풀이

package Baekjoon;
import java.util.Scanner;

public class B1_13322 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String input = sc.nextLine();

    for (int i = 0; i < input.length(); i++) {
      System.out.println(i);
    }
  }
}

여담

접두사 배열이라 결국 사전순으로 정렬되어있어서, 문자열 길이만큼 끝나는 인덱스만 찍어주면 되는 문제였다.

브론즈 3 https://www.acmicpc.net/problem/2562

풀이

package Baekjoon;

import java.util.Scanner;

public class B3_2562 {

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int[] arr = new int[9];

    for (int i = 0; i < 9; i++) {
      arr[i] = in.nextInt();
    }

    int max = arr[0];
    int idx = 0;

    for (int i = 0; i < 9; i++) {
      if (arr[i] >= max) {
        max = arr[i];
        idx = i + 1;
      }
    }

    System.out.println(max);
    System.out.println(idx);
  }
}

인덱스 처리를 해줘야하기 때문에 if문에서 조건을 arr[i] > max로 하면 안된다! 주의!

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

풀이

package Baekjoon;

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

public class B_10807 {
  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[] arr = new int[n];
    int cnt = 0;

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

    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    st = new StringTokenizer(br.readLine());
    int v = Integer.parseInt(st.nextToken());

    for (int i = 0; i < n; i++) {
      if (arr[i] == v) {
        cnt++;
      }
    }

    System.out.println(cnt);

  }
}

실버 3 https://www.acmicpc.net/problem/11659

풀이

import java.util.Scanner;

public class S3_11659 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int M = in.nextInt();

    int[] input = new int[N];
    int[] sum = new int[N];
    int[] result = new int[M];

    for (int i = 0; i < N; i++) {
      input[i] = in.nextInt();

      if (i == 0) {
        sum[i] = input[i];
      } else {
        sum[i] = sum[i-1] + input[i];
      }
    }

    for (int x = 0; x < M; x++) {
      int i = in.nextInt() - 1;
      int j = in.nextInt() - 1;

      if (i == 0) {
        result[x] = sum[j];
      } else {
        result[x] = sum[j] - sum[i - 1];
      }
    }

    for (int x = 0; x < M ; x++) {
      System.out.println(result[x]);
    }
  }
}

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기

1. N개의 수를 입력받음과 동시에 합 배열 생성

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

2. 구간 i, j가 주어지면 구간 합을 구하는 공식으로 정답 출력

   S[j] = S[i-1]

2. 슈도코드

3. 코드

    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

    int suNo = Integer.parseInt(stringTokenizer.nextToken());   // 데이터 개수, 5
    int quizNo = Integer.parseInt(stringTokenizer.nextToken());   // 질의 개수, 3

    long[] S = new long[suNo + 1];   // 1 더해서 6개의 원소를 가진 배열 생성

    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    for (int i = 1; i <= suNo; i++) {      // 1부터 시작해서
      S[i] = S[i - 1] + Integer.parseInt(stringTokenizer.nextToken());   // 바로 받으면서 합 배열 생성
    }

    for (int q = 0; q < quizNo; q++) {
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int i = Integer.parseInt(stringTokenizer.nextToken());
      int j = Integer.parseInt(stringTokenizer.nextToken());
      System.out.println(S[j] - S[i - 1]);   // 구간 합 구하기
    }

여담

생각보다 오래 걸렸다...

nextInt는 공백 구분 가능

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

풀이

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

public class B1_1546 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[] grade = new int[N];

    StringTokenizer st = new StringTokenizer(br.readLine());
    // 공백으로 나눠서 배열에 입력
    for (int i = 0; i < N; i++) {
      grade[i] = Integer.parseInt(st.nextToken());
    }

    int M = grade[0];
    double[] grade_d = new double[N];
    double sum = 0;

    // 최댓값 구하기
    for (int g : grade) {
      if (g > M) {
        M = g;
      }
    }
    // 점수 배열 변환
    for (int i = 0; i < N; i++) {
      grade_d[i] = (double) grade[i] / M * 100;
    }
    // 합 구하기
    for (double d : grade_d) {
      sum += d;
    }
    System.out.println(sum / N);
  }
}

    과목 개수 int N 입력 받기
    현재 성적 입력받아서 int[]에 넣기
    M 최댓값
    sum 합
    for(int[] 돌면서)
      더 크면 M에 저장

    for(int[] 돌면서)
      점수 = 점수/M*100

    for(int[] 돌면서)
      합 += 점수

    print 점수/N

처음에는 이렇게 int 배열 내에서 변환하려고 했는데 정수로 나누고 하다보니 0이 나왔다...생각해보니 당연함... double 배열을 새로 만들어서 계산해야 올바른 값이 나온다.

    과목 개수 int N 입력 받기
    현재 성적 입력받아서 int[]에 넣기
    double[] 선언
    M 최댓값
    sum 합
    for(int[] 돌면서)
      더 크면 M에 저장

    for(i 돌면서)
      점수 = 점수/M*100 로 double[] 에 넣기

    for(int[] 돌면서)
      합 += 점수

    print 점수/N

[Do it! 알고리즘 코딩 테스트 자바편]

과정

1. 문제 분석 & 풀어보기 일일이 변환 점수를 구할 필요 없이 한번에 올바른 값을 구할 수 있다.

(A + B + C) * 100 / M / 3

-> (A / M * 100 + B / M * 100 + C / M * 100) / 3

1) 점수를 1차원 배열에 저장 2) 배열을 탐색하며 최고 점수와 총합 3) 총합 * 100 / 최고 점수 / 과목 수

2. 슈도코드

변수 N에 과목 수 입력받기
길이가 N인 A[] 선언

for(A[] 길이)
    A[i]에 각 점수 저장

for(A[] 길이)
    max에 최댓값, sum에 총점 저장

sum * 100 / max / N 출력

3. 코드

    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A[] = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    long sum = 0;
    long max = 0;
    for (int i = 0; i < N; i++) {
      if (A[i] > max) max = A[i];
      sum += A[i];
    }
    System.out.println(sum * 100.0 / max / N);

추가

자동 타입 변환

double d1 = 5 * 3.14;
double d2 = 1;

이렇게 하면 int가 double로 자동 타입 변환된다.

기초 타입 범위 double > float > long > int > short, char > byte

백준 11720: 브론즈 2 https://www.acmicpc.net/problem/11720

풀이

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int a = in.nextInt();
    String b = in.next();
    int sum = 0;

    for (int i = 0; i < b.length(); i++) {
      int num_b = Integer.parseInt(String.valueOf(b.charAt(i)));
      sum += num_b;
    }
    System.out.println(sum);
  }
}
  }
}

[Do it! 자바 코딩테스트 알고리즘 자바편]

과정

1. 문제 분석 & 풀어보기

1) 문자열로 입력값 받고 -> String으로 저장 2) 문자 배열로 변환하고 -> char []로 변환 3) 문자 배열값을 순서대로 읽으면서 -> for문 4) 숫자로 변환해서 -> 아스키코드 연산 5) 더해야한다. -> 결괏값에 누적

🌵 문자열을 숫자로 변경하려면 아스키코드를 이해해야 한다. 같은 의미의 문자와 숫자의 코드 값 차이는 48이다. ex) 문자 '1'의 아스키코드 값은 49, '0'은 48 문자 '1'을 숫자 1로 변환하려면, '1'-48, 또는 '1'-'0'으로 연산

2. 슈도코드

N 입력 받기
길이 N의 숫자를 입력받아 String sNum에 저장
char [] cNum에 sNum 변환해서 저장
int sum = 0;

for (cNum의 길이) {
    cNum[i] int로 바꿔서 += sum
}

sum 출력

3. 코드

    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String sNum = sc.next();
    char[] cNum = sNum.toCharArray();
    int sum = 0;
    for (int i = 0; i < cNum.length; i++) {
      sum += cNum[i] - '0';  // 정수형으로 변환
    }
    System.out.println(sum);

다른 사람의 풀이

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        char[] numbers = br.readLine().toCharArray();
        int total = 0;

        for (int i = 0; i < N; i++) {
            total += Integer.parseInt(String.valueOf(numbers[i]));
        }
        System.out.println(total);

BufferedReader를 이용해봐야겠다.

추가

자바 형변환(String↔숫자형, String↔char)

next(), nextLine()의 차이 https://devlog-wjdrbs96.tistory.com/80

여담

22.11.21 자바 적응하기 어렵다ㅎ ㅎ

String str = "1234";

int i1 = Integer.parseInt(str);  // int 리턴
int i2 = Integer.valueOf(str);  // Integer Object 리턴
// Integer.valueOf(str).intValue(); -> Integer Object를 int로 변환할 수 있음

double, float, long, short도 마찬가지로 하면 된다. Double.parseDouble(str), Double.valueOf(str) 이런 식!

int와 Integer의 차이 primitive 타입과 wrapper class

2. 숫자형(int, double, float, long, short) → String

int i = 1234;

String i1 = String.valueOf(i);
String i2 = Integer.toString(i);

double, float, long, short도 마찬가지로 하면 된다. double d가 있다면, String.valueof(d), Double.toString(d) 이런 식!

3. String → char

char 배열로 변환

String str = "hello";

char[] charArray = str.toCharArray();

stream 방식

String str = "hello";

str.chars().mapToObj(ch -> (char)ch).forEach(System.out::println);

charAt()으로 특정 인덱스에 있는 문자 가져오기

String str = "hello";

char c = str.charAt(인덱스);

4. char → String

valueOf(char)

char c = 'a';

String str = String.valueOf(c);

// 같은 방식으로 char[] 배열도 String으로 변환 가능

toString()

char c = 'a';

String str = Character.toString(c);

// char[] 배열은 변환 불가능

참고

https://codechacha.com/ko/java-convert-string-to-chararray/

char -> String https://codechacha.com/ko/java-convert-chararray-to-string/

https://java119.tistory.com/106