📙 Algorithm Solving/Java

📙[Algo] 24.01.23 알고리즘

혜덕hyeduck 2024. 1. 23. 20:03

알고리즘 문제) BOJ 11728. 배열 합치기

 

11728번: 배열 합치기

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거

www.acmicpc.net

문제 요약

  • 정렬되어 있는 두 배열 A, B
  • 두 배열을 합친 다음 정렬해서 출력하기

시간 제한

  • 1.5초

입력

  • 배열 A의 N, 배열 B의 크기 M ( 1 ≤ N, M ≤ 100만)
  • 배열 A가 주어짐
  • 배열 B가 주어짐
  • 배열의 수는 절댓값이 10억보다 작거나 같은 정수

출력

  • 두 배열을 합친 후 정렬한 결과 출력

접근법

  • 정렬할 때, Arrays.sort()를 사용할 경우 평균 O(nlogn)이 발생하고, 최악의 경우 O(n*n)이 발생
    • 배열 A의 길이 100만개, 배열 B의 길이 100만개라면 둘이 합치면 200만개가 되고 이를 정렬할 경우, 최악의 경우 4조의 연산이 발생할 수 있다.
  • 정렬 최적화 하기
    • A배열, B배열 각각 포인터를 하나씩 둔다.
      2 3 5 9
      a 
      1 4 7
         b
    • A[a] < B[b] 이므로, A[a]를 새로운 배열에 담고, a+=1
    • 1 4 7 b
    • A배열, B배열 각각 포인터를 하나씩 둔다.

코드

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

public class Main {
    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;

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

        int[] arrA  = new int[N];
        int[] arrB  = new int[M];

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

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

        int[] answer = new int[N+M];
        int a = 0, b = 0, idx = 0;
        while (idx < N + M) {

            if(a >= N || b >= M){
                if (a < N) {
                    for (int i = a; i < N; i++) {
                        answer[idx++] = arrA[i];
                    }
                } else if (b < M) {
                    for (int i = b; i < M; i++) {
                        answer[idx++] = arrB[i];
                    }
                }
                break;
            }


            if (arrA[a] > arrB[b]) {
                answer[idx++] = arrB[b];
                b += 1;
            } else if (arrA[a] <= arrB[b]) {
                answer[idx++] = arrA[a];
                a += 1;
            }

        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N + M; i++) {
            sb.append(answer[i]+" ");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14465. 소가 길을 건너간 이유 5

 

14465번: 소가 길을 건너간 이유 5

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

www.acmicpc.net

문제 요약

  • 1번부터 N번까지의 횡단보도 존재
  • 고장난 신호등이 B개 존재
  • 연속한 K개의 신호등이 존재하도록 하도록 수리하려 함
  • 최소 몇 개의 신호등을 수리?

시간 제한

  • 2초

입력

  • N, B, K (1≤B,K≤N)
    • 1 ≤ N ≤ 10만
  • B줄에 고장난 신호등이 주어짐

출력

  • 정상 작동하는 연속 k개 신호등이 존재하려면 최소 몇 개 수리?

접근법

  1. 완전 탐색으로 접근
    1 2 3 4 5 6 7 8 9 10
    f  f  t  t  f  t  t  t  f   f
    • 신호등을 고치는 경우의 수를 구하고(1개부터 B개까지), 그때 연속 K개 신호등이 존재하는 경우 고친 신호등의 개수가 가장 작은 값으로 갱신
  2. 최적화 하기
    • 고장난 신호등 번호들을 나열한다.
      1 3 4 6 10 11 14
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 / K=6
    • 연속된 신호등 6개씩 묶어서 이동시켜가며, 고장 난 신호등 개수를 체크한다.
    • 이때 고장난 신호등 개수를 체크해야한다.
      • 배열을 하나 만들어서 누적된 고장난 신호등 개수를 담아둔다.
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
        1 1 2 3 3 4 4 4 4 5 6 6 6 7 7
        • cnt = arr[e] - arr[s-1]
    • 1 2 3 4 5 6
      • cnt = 4
    • 2 3 4 5 6 7
      • cnt = 3
    • 3 4 5 6 7 8
      • cnt = 3
    • 4 5 6 7 8 9
      • cnt = 2
    • 5 6 7 8 9 10
      • cnt = 2
    • 6 7 8 9 10 11
      • cnt = 3
    • 7 8 9 10 11 12
      • cnt = 2
    • 8 9 10 11 12 13
      • cnt = 2
    • 9 10 11 12 13 14
      • cnt = 3
    • 10 11 12 13 14 15
      • cnt = 3

고민

  • 고장난 신호등 개수 누적합 배열 만드는거에서 시간을 많이 썼다.
  • 투포인터로 어떻게 풀라는거지? 고민을 많이 했는데, 너무 어렵게 생각한 거였다. 그냥 연속된 신호등 K개씩 묶어서 하나하나 이동하면서 고장난 신호등 개수 체크하는 문제였다.

코드

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

public class Main {
    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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int[] broken = new int[N];
        for (int i = 0; i < B; i++) {
            broken[Integer.parseInt(br.readLine())-1]++;
        }

        for (int i = 1; i < N; i++) {
            broken[i] += broken[i - 1];
        }

        int s = 1, e = s + (K-1), answer = broken[K-1];
        while (e < N) {
            answer = Math.min(answer, broken[e] - broken[s - 1]);
            s++;
            e++;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 15961. 회전 초밥  

 

15961번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2

www.acmicpc.net

문제 요약

  • 벨트 임의의 위치부터 k개 접시를 연속해서 먹을 경우 할인된 가격으로 제공
  • 초밥의 종류가 적힌 쿠폰으로, 위의 행사에 참여할 경우 해당 초밥 하나 무료 제공
  • 위 행사에 참여하여 최대한 다양한 종류의 초밥을 먹으려고 함!

시간 제한

  • 1초

입력

  • 회 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시 개수 k, 쿠폰 번호 c가 주어짐
    • 2 ≤ N ≤ 300만
    • 2 ≤ d ≤ 3000
    • 2 ≤ k ≤ 3000 ( k ≤ N)
    • 1 ≤ c ≤ d
  • 회전 방향(→)을 따라갈 때 초밥의 종류가 1~각 줄마다 주어짐

출력

  • 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값 출력

접근법

7 9 7 30 2 7 9 25

  • 순환이므로 인덱스가 N을 초과하면 %N으로 갱신
  • 시작 포인트 s, 끝나는 포인트 e를 지정
  • s=0, e=k-1부터 시작해서 s가 다시 0으로 올 때까지 실시 ⇒ 최대 300만연산 횟수 발생
  • 가짓수 계산을 어떻게 진행할까?
    • 모든 케이스 일일이 다 체크하면 안 됨 ⇒ 300만*3000으로 시간초과
    • 최적화 필요
      • 0부터 k-1까지 방문체크를 한다.(+1)
        • 이때 방문 체크 배열은 3010정도 길이를 갖고 있음
          • 방문할 때마다 1씩 증가
          • 추가로 쿠폰번호 c도 방문 체크!
        • 동시에 현재 초밥 가짓수까지 기록한다.
      • 그 다음 한 칸 우측으로 이동할 때마다
        • visited[sushi[s]] -= 1; s-=1;
        • e+=1; visited[sushi[e]] += 1
        • 이때 가짓수(cnt)는 (s : 이동전, e: 이동후)
          • visited[sushi[s]]
            • visited[sushi[s]]>1 : cnt
            • visited[sushi[s]]==1 : cnt-=1
          • visited[sushi[e]]
            • visited[sushi[e]] ≥1 : cnt
            • visited[sushi[e]] == 0 : cnt +=1
      • 초밥 가짓수가 최댓값이 될 때까지 갱신반복…

고민

  • while문 탈출 조건으로 순회 하나를 끝냈을 때로 하기위해 s=0부터 시작했는데, 그렇게 해버리니까 s=0, e=K-1부터 시작하면 아예 while문이 동작하지 않는다.
  • 그렇다고 s=1, e=k부터 하면 s=0, e=k-1에서 한 칸 이동할 때 발생하는 가짓수 처리를 못한다.
  • 그래서 중간에 if문으로 break를 걸었는데 뭔가 좀 그렇다..

코드

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

public class Main {
    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 d = Integer.parseInt(st.nextToken()); // 초밥의 가짓 수
        int k = Integer.parseInt(st.nextToken()); // 연속해서 먹는 접시 수
        int c = Integer.parseInt(st.nextToken()); // 쿠폰 번호

        int[] visited = new int[3010];
        int[] sushi = new int[N];
        for (int i = 0; i < N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }

        visited[c]++;
        int cnt = 1;
        for (int i = 0; i < k; i++) {
            if(visited[sushi[i]] == 0) cnt++;
            visited[sushi[i]]++;
        }


        int s = 0, e = k-1, ans = cnt;
        while (true) {

            if (visited[sushi[s]] == 1) cnt--;
            visited[sushi[s]]--;
            s = (s + 1) % N;

            if (s == 0) break;

            e = (e + 1) % N;
            if(visited[sushi[e]] == 0) cnt++;
            visited[sushi[e]]++;

            ans = Math.max(ans, cnt);
        }

        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 23032. 서프라이즈~

 

23032번: 서프라이즈~

쿠기는 가톨릭대학교 컴퓨터정보공학부 학부장이다. 곧 다가오는 시험 기간에 학생들에게 힘을 주고자 간식 행사에 안심 스테이크를 주려고 한다. 컴퓨터정보공학부에는 N명의 학생이 있는데,

www.acmicpc.net

문제 요약

  • 1부터 N명의 학생, 학생별로 먹고 싶은 스테이크 그램 수 지정.
  • 다음 규칙으로 당첨자들에게 스테이크를 나눠줌
    1. 임의로 연속된 학번의 학생을 정함
    2. 임의로 대상 학생들을 두 그룹으로 나눔
      • 이 때 한 그룹의 학생들은 학번이 인접
      • 최소 1명 이상 존재
    3. 두 그룹의 스테이크 무게 합의 차 E (큰 그룹 - 작은 그룹)
    4. E가 최솟값인 두 그룹이 당첨
    5. 여러가지 존재 시 스테이크 무게 합이 가장 큰 두 그룹이 당첨
  • 당첨자들의 스테이크 무게 합 구하기

시간 제한

  • 1초

입력

  • N ( 2 ≤ N ≤ 2,000)
  • 1번부터 N번 학생까지 설문조사에 적은 스테이크 무게 정수 W가 주어짐
    • 1≤ W ≤ 10000

출력

  • 이벤트에 당첨된 학생들의 스테이크 무게 합을 출력

접근법

N = 6

2 1 5 2 4 4

  1. 완전 탐색으로 접근하기
    • 2명부터 N명까지 임의로 이벤트 대상 학생들을 선택하는 모든 경우의 수에 대해
      • 2중 for문
        • for i 0~N-2 : 대상 학생 시작 지점
          • for j i+1~N-1 : 대상 학생 끝 지점
    ⇒ 여기까지 2000*2000 = 4,000,000 ( 400만 )
    • 두 그룹으로 나눌 수 있는 모든 경우의 수에서
      • for k i~j-1 : 기준 점 [i~k, k+1~j]
    ⇒ 여기까지 200020002000 = 8,000,000,000 (80억) 시간초과 발생
    ⇒ 해당 부분 최적화 할 것  
    • E가 최솟값인 경우 찾기, 여러 개일 경우 무게 합이 가장 큰 경우 찾기  
      • 무게 합 구할 때도 일일이 방문하면서 합할 경우 추가 시간 발생
        ⇒ 여기도 최적화 필요
  2. 최적화 하기
    • 두 그룹으로 나누는 경우와 스테이크 무게합 구하는 부분을 최적화 할 것
    • 무게합 최적화
      • 전체 무게 = 18
      • 결국 연속된 학생들로 두 그룹으로 나누기 때문에 누적합 배열(acc) 사용
        2 1 5 2 4 4 (i=1, j=N)
        2 3 8 10 14 18
    • 그룹 나누기 최적화
      • 최소 1명부터 그룹이 만들어진다. s→0,e→0부터 시작
        2 3 8 10 14 18
        s             e
      • s→1, e→5
        • acc[e] = 14이므로, 두 그룹의 무게는 14와 4
          • 두 그룹의 무게 차는 14
        • 현재, e는 s기준 올 수 있는 가장 큰 인덱스값이다. 여기서 무게 차를 줄이기 위해서 e-=1;
      • s→1, e→4
        • acc[e] = 10이므로, 두 그룹의 무게는 10과 8
          • 무게 차 : 2
        • e-=1;
      • s→1, e→3
        • acc[e] = 8이므로, 두 그룹의 무게는 8과 10
          • 무게 차 : 2
        • e -= 1;
      • s→1, e→2
        • acc[e] = 3이므로, 두 그룹의 무게는 3과 15
          • 무게 차 12
        • 값이 오히려 커졌으므로 더 이상 탐색 종료
          • 이걸 체크하기 위해서는 전에 기록해둔 무게 차 변수를 하나 더 추가한다.
  1.  
  • 최솟값이 나올 수 있는 경우가 여러 개 있을 수 있으니까, 정답을 기록할 때 단순히 무게차의 최솟값만 기록하지 말고, 추가로 두 그룹의 무게 합까지 기록한다.
    • ansDiff < diff
      • ansDiff= diff, ansSum = sum
    • ansDiff == diff
      • ansSum < sum
        • ansSum = sum

고민

  • 이게 왜 투 포인터일까?
    • 포인터 하나로만 했는데,,,
    • 그룹 시작지점 i가 start포인트가 되는 건가???
  • 누적합 구할 때랑 뒤에 누적합 배열에서 두 그룹별 무게 구할 때 i=0부터 시작하면 i-1일 때 인덱스 오류 떠서 N+1배열로 선언해서 사용했다.
    • 다음부터 누적합 쓸 때 처음부터 배열 크기를 1늘려야겠다.
  • beforeDiff라는 변수 만들어서 무게차가 커지는 경우 while문 탈출하도록 조건 걸었는데,, 이것말고 다른 방법은 없을까??

코드

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

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

        int N = Integer.parseInt(br.readLine());
        int[] acc = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            acc[i] = Integer.parseInt(st.nextToken()) + acc[i-1];
        }

        int p = 0, diff = 0, sum = 0, ansSum = 0, ansDiff = Integer.MAX_VALUE, beforeDiff = 0;
        for (int i = 1; i <= N-1; i++) {
            for (int j = i + 1; j <= N; j++) {
                p = j - 1;
                beforeDiff = Integer.MAX_VALUE;

                while (p >= 0) {
                    diff = Math.abs((acc[p]-acc[i-1]) - (acc[j] - acc[p]));
                    sum = acc[j] - acc[i-1];

                    if(beforeDiff < diff) break;

                    if (ansDiff > diff){
                        ansDiff = diff;
                        ansSum = sum;
                    }else if (ansDiff == diff) {
                        if (ansSum < sum) ansSum = sum;
                    }

                    p -= 1;
                    beforeDiff = diff;
                }

            }
        }

        bw.write(String.valueOf(ansSum));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 22862. 가장 긴 짝수 연속한 부분 수열 (large)

 

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

www.acmicpc.net

문제 요약

  • 길이가 N인 수열 S
  • 수열 S는 1이상인 정수로 이루어져 있음
  • 원하는 위치에 있는 수를 골라 최대 K번 삭제 가능
  • 이때 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져있는 연속 부분 수열 중 가장 긴 길이 구하기

시간 제한

  • 1초

입력

  • N K
    • 1≤N≤100만
    • 1≤K≤10만
  • 수열 S
    • 1≤원소의 값≤100만

출력

  • 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어진 연속 부분 수열 중 가장 긴 길이 찾기

접근법

K=2

1 2 3 4 5 6 7 8

  1. 먼저 완전 탐색으로 접근하기
    • 재귀로 depth가 2가 될 때까지 수열 중 2 개의 원소를 찾아 제거하고, 수열 앞에서부터 짝수로 시작하는 부분수열을 찾아 가장 길이가 긴 값으로 갱신한다.
    • 100만의 k승(원소 K개 삭제한 경우들) * 100만(짝수로 시작하는 연속 부분 수열 최장 길이 찾기)이므로 엄청난 연산 시간이 발생
  2. 최적화 진행하기
    1 2 3 4 5 5 6 6 8
       s
       e
    • 홀수만 제거하면 된다.
    • 구간 시작 포인터인 s, 끝 포인터인 e를 만든다.
      • 이 두개 포인터는 무조건 짝수를 가리킨다.
      • 초기에는 s와 e를 같은 곳을 가리키도록 한다.
    • 제거한 개수 delCnt = 0;
    • s → 2, e→ 2
      • delCnt=0;
      • e+=1;
      • len = 1
    • s→2, e→3
      • e→3일 때 홀수이므로
        • delCnt+=1;
      • e+=1
      • len = 1
    • s→2, e→4
      • delCnt = 1
      • e+=1
      • e→4일 때 짝수이므로 len += 1
      • len = 2
    • s→2, e→5
      • delCnt += 1 → 2
      • e+=1
    • s→2, e→5
      • delCnt += 1 → 3
      • s→2일때 짝수이므로 len-=1
      • s+=1
      • len = 1
    • s→3, e→5
      • delCnt = 3
      • s+=1
      • s→3일때 홀수이므로 delCnt-=1
      • len = 2
    • s→4, e→5
      • delCnt = 2
      • e+=1
      • len = 1
    • s→4, e→6
      • delCnt = 2
      • e+=1
      • e→6일 때 짝수이므로 len += 1
      • len = 2
    • s→4, e→6
      • delCnt = 2
      • e+=1
      • e→6일 때 짝수이므로 len += 1
      • len = 3
    • s→4, e→8
      • delCnt = 2
      • e+=1
      • e→8일 때 짝수이므로 len += 1
      • len = 4
    • 종료조건 : e ≥ N

코드

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

public class Main {
    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;

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

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        int s = -1, e = -1;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());

            if (s == -1 && arr[i] % 2 == 0) {
                s = i;
                e = i;
            }
        }

        int delCnt = 0, len = 1, answer = 0;
        while (0 <= e && e < N) {

            if (delCnt > K) {
                if (arr[s] % 2 == 0) len--;
                else delCnt--;
                s++;
            } else {
                answer = Math.max(answer, len);
                e++;
                if (arr[e] % 2 == 0) len++;
                else delCnt++;
            }

        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 15831. 준표의 조약돌

 

15831번: 준표의 조약돌

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조

www.acmicpc.net

문제 요약

  • 1~N개까지 일렬로 검은색과 흰색 조약돌이 있음
  • 이때 시작 지점을 임의로 정하고, 원하는 지점까지 조약돌을 줍는다.
    • 단 구간을 정할 때 아래 기준 충족
      1. 검은색 조약돌은 B이하
      2. 흰색 조약돌은 W이상
  • 이때 최대 구간 길이 구하기

시간 제한

  • 1초

입력

  • 조약돌의 총 개수 N, 원하는 검은색 조약돌 최대 개수 B, 원하는 하얀색조약돌 최소 개수 W가 주어짐
    • 1 ≤ N ≤ 30만
    • 0 ≤ B, W, B+W ≤ N
  • N개의 조약돌의 정보 ( B : 검은색, W : 흰색)

출력

  • 걸을 수 있는 가장 긴 구간 길이 구하기, 없다면 0 출력

접근법

N = 10, B = 1, W = 2 WBBWWBWWBW

  1. 완전 탐색으로 생각하기
    • 시작지점과 끝지점을 각각 지정해준 이중 for문을 사용
    • 이때 모든 케이스에 대해서 조건을 충족하는 경우 찾고 최대 구간 길이로 갱신
    ⇒ 30만30만30만 ⇒ 시간초과
  2. 최적화 하기
    • 먼저 구간의 조약돌 갯수를 일일이 체크하기 번거로우므로 미리 누적합배열을 사용해서 기록할 것(W, B 갯수 모두 기록해야므로 2차원 배열)
      0 1,0 1,1 1,2 2,2 3,2 3,3 4,3 5,3 5,4 6,4
    • 구간 구하기
      1 2 3 4 5 6 7 8 9 10
      W B B W W B W W B W
      s
      e
      • s→1, e→1
        • bCnt = acc[e][1] = 0 < B
        • wCnt = acc[e][0] = 1 < W (X)
        • e+=1
      • s→1, e→2
        • bCnt = acc[e][1] = 1 == B
        • wCnt = acc[e][0] = 1 < W (X)
        • e+=1
      • s→1, e→3
        • bCnt = acc[e][1] = 2 > B (X)
        • wCnt = acc[e][0] = 2 == W
        • s+=1
      • s→2, e→3
        • bCnt = acc[e][1] - acc[s-1][1] = 2 > B (X)
        • wCnt = acc[e][0] - acc[s-1][1] = 0 < W (X)
        • s+=1, e+=1
      • s→3, e→4
        • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
        • wCnt = acc[e][0] - acc[s-1][1] = 1 < W (X)
        • e+=1
      • s→3, e→5
        • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
        • wCnt = acc[e][0] - acc[s-1][1] = 2 == W
        • e+=1 → 혹시 더 가능성 있는 케이스가 있을 수 있으니
      • s→3, e→6
        • bCnt = acc[e][1] - acc[s-1][1] = 2 > B (X)
        • wCnt = acc[e][0] - acc[s-1][1] = 2 == W
        • s += 1
      • s→4, e→6
        • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
        • wCnt = acc[e][0] - acc[s-1][1] = 2 == W
        • e+=1
      • s→4, e→7
        • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
        • wCnt = acc[e][0] - acc[s-1][1] = 4 > W
        • e+=1
      • s→4, e→8
        • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
        • wCnt = acc[e][0] - acc[s-1][1] = 4 > W
        • e+=1
      • s→4, e→9
        • bCnt = acc[e][1] - acc[s-1][1] = 2 > B (X)
        • wCnt = acc[e][0] - acc[s-1][1] = 4 > W
        • s+=1
      ⇒ 이렇게 구간 이동하면서 구간 길이 최댓값을 갱신한다. 이때 종료 조건은 s > e인 순간 ⇒ e>N일떄
      ⇒ 검정 조약돌이 B보다 큰 경우만 s+=1 하고, 나머지는 e+=1로 바꿈(코드 깔끔하게 하기 위해)

코드

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

public class Main {
    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 B = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        String road = br.readLine();
        int[][] acc = new int[N+1][2]; // 0 : 검정색 누적개수, 1: 하얀색 누적개수
        // 조약돌 갯수 누적합 배열에 담기
        for (int i = 1; i < N + 1; i++) {
            if (road.charAt(i - 1) == 'B') {
                acc[i][0] = acc[i - 1][0] + 1;
                acc[i][1] = acc[i - 1][1];
            } else {
                acc[i][0] = acc[i - 1][0];
                acc[i][1] = acc[i - 1][1] + 1;
            }
        }

        // 구간별 조건 충족여부 체크 & 충족시 구간 길이 최댓값으로 갱신
        int s = 1, e = 1, answer = 0, bCnt = 0, wCnt = 0;
        while (e <= N) {
            bCnt = acc[e][0]-acc[s-1][0];
            wCnt = acc[e][1]-acc[s-1][1];

            if(bCnt <= B && wCnt >= W) answer = Math.max(answer, e - s + 1);

            if (bCnt > B) s++;
            else e++;

        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1806. 부분합

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

문제 요약

  • 10,000이하 자연수로 이루어진 길이 N짜리 수열
  • 연속된 수들의 부분합 중 그 합이 S이상 되는 것 중, 가장 짧은 것 출력

시간 제한

  • 1초

입력

  • N S
    • 10 ≤ N < 10만
    • 0 < S ≤ 1억

출력

  • 구하려는 최소 길이

접근법

N=10 S=15 5 1 3 5 10 7 4 9 2 8

  1. 완전 탐색
    • 2중 for문을 사용해서 시작점과 끝점을 정하고, 원소 하나하나 접근해서 더한 후 S이상인지 체크
    ⇒ 10만10만10만 시간 초과
  2. 최적화 진행
    • 구간 정하는 부분이랑 합 구하는 부분 모두 최적화 필요 ⇒ 0.5초 안에 들어와야 하니 ⇒ 즉 최대한 10만 연산 안에 이루어지도록 할 것
    • 일단 처음부터 입력 받을 때부터 전체 수열 원소의 합을 구한다. sum = 54
    • 현재까지의 원소 합을 변수에 기록 sum
      • 이동할 때마다 sum에서 더하고 빼고,,
    • s → 0, e→ 0를 가리키고 시작
      5 1 3 5 10 7 4 9 2 8
      s
      e
      • s→0, e→0
        • sum : 5 < S
        • e+=1
        • sum += arr[e];
      • s→0, e→1
        • sum : 6 < S
        • e+=1
      • s→0, e→2
        • sum : 9 < S
        • e+=1
      • s→0, e→3
        • sum : 14 < S
        • e+=1
      • s→0, e→4
        • sum : 24 > S
        • s+=1
      • s→1, e→4
        • sum : 19 > S
        • s+=1
      • s→2, e→4
        • sum : 18 > S
        • s+=1
      • s→3, e→4
        • sum : 15 == S
        • 정답 찾음 ⇒ 답 갱신
        • e +=1
      • 위 과정을 반복한다.
      • 종료 조건 : e ≥ N

코드

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

public class Main {
    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;

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

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int s = 0, e = 0, sum = arr[0], answer = Integer.MAX_VALUE;
        while (e < N) {

            if (sum < S) {
                e++;
                sum += arr[e];
            } else {
                if (sum >= S) {
                    answer = Math.min(answer, e - s + 1);
                }
                sum -= arr[s];
                s++;
            }
        }

        if(answer == Integer.MAX_VALUE) answer = 0;

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}