📙[Algo] 24.01.30 알고리즘

알고리즘 문제) BOJ 24956. 나는 정말 휘파람을 못 불어

24956번: 나는 정말 휘파람을 못 불어

문제 요약

• 대문자로 구성된 문자열 S에서 휘파람과 비슷한 소리(유사 휘파람 문자열) 개수를 구해야 함
  • WHEE : 유사 휘파람 문자열
  • WHEE + E붙인것도 유사 휘파람 문자열
• S에서 유사 휘파람 문자열인 부분수열 개수 구하기
  • 꼭 문자들이 연속하지 않아도 됨

시간 제한

• 1초

입력

• 문자열 S의 길이 N
  • 1≤N≤20만
• 문자열 S

출력

• 유사 휘파람 문자열인 부분 수열 개수를 1000000007로 나눈 나머지 출력

접근법

유사 휘파람 문자열은 최소 WHEE로 구성 될 것

1. 완전 탐색으로 접근하기
   WAHEWHEE WHEWHEE W → H → E → E → E….
   먼저 문자열 앞에서부터 W가 나올 때까지 탐색 진행
   W를 찾으면 그 다음 H, E, E순서대로 찾을 때까지 탐색 진행
   WHEE하나 완성 되면 카운트 증가, 그다음 끝까지 E만 등장할 때까지 탐색하면 카운트 하나씩 계속 증가
   최소 2중 for문 필요 (스타트 지점 찾을 for 문 * 이후 유사 휘파람 문자열 완성할 for문 ) ⇒ 그러나 문자열 길이가 20만이기 때문에 20만*20만 이면 시간 초과 발생 ⇒ 2중 for문 안 됨!
2. 최적화하기
   유사 휘파람 문자열은 W 1개, H 1개, E 2개이상으로 구성되어야 한다.
        E W H E H E H E W W W H E H E
   W: 0 1 1 1 1 1 1 1 2 3 4 4 4 4 4
   H : 0 0 1 1 2 2 3 3 3 3 3 4 4 5 5
   E : 1 1 1 2 2 3 3 4 4 4 4 4 5 5 6
   
   • W → H를 먼저 찾아야 한다.
     • H는 앞의 W의 개수에 영향을 받는다.
   • 즉, 우선 W, E의 등장 개수 누적합 배열을 만든다.
   • for문을 이용해 H 등장여부를 체크한다.
     • H가 등장하면 해당 지점까지 W등장 횟수 * 해당 지점 이후 E의 부분 집합 개수 중 2개 이상의 원소로 이루어진 부분 집합 개수만큼 더해준다.
   • ⇒ 1차원 배열로만 처리하기
   • ⇒ 부분집합 개수 구해버리면 최악의경우 2의 20만승을 계산하니까 무한대로 커질 수 있움,,,

코드

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


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());
        final int MOD = 1000000007;

        String S = br.readLine();
        int[] accW = new int[N + 1];
        int[] accE = new int[N + 1];
        long[] subset = new long[N + 1];
        for (int i = 1; i <= N; i++) {

            accW[i] += accW[i - 1];
            accE[i] += accE[i - 1];

            if(S.charAt(i-1) == 'W') accW[i] = (accW[i - 1] + 1) % MOD;
            else if(S.charAt(i-1) == 'E'){
                accE[i] = (accE[i - 1] + 1) % MOD;
                subset[accE[i]] = subset[accE[i - 1]] * 2 % MOD + accE[i - 1] % MOD;
            }

        }

        long answer = 0;
        for (int i = 1; i <= N; i++) {
            if (S.charAt(i - 1) == 'H') {
                answer += accW[i] * (subset[(int)accE[N] - (int)accE[i]]);
            }
        }
        bw.write(String.valueOf(answer % MOD));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 17074. 정렬

17074번: 정렬

문제 요약

• 배열의 모든 원소가 오름차 되도록 정렬
• 수를 하나 버린 뒤 배열이 정렬되게 하려고 함
• 이때 가능한 경우의 수?

시간 제한

• 1초

입력

• N
  • 2≤N≤10만
• 배열 원소 N개
  • -10억 ~ 10억

출력

• 하나를 버려 정렬된 배열 만들 수 있는 경우의 수

접근법

1. 완전 탐색으로 접근하기
   수 하나씩 버리면서 오름차순인지 체크한다.
   하지만 이렇게 되면 버릴 수 선택하는 for문 10만 * 버렸을 때 정렬 됐는 지 체크하는 for문 10만 ⇒ 100억 연산으로 시간초과
2. 최적화하기
   1234334
   • 4 양 옆 3 == 3 이므로 4제거 가능
   • 3 양 옆 4 > 3 이므로 3 제거 X
   1236456
   • 6 양 옆 3<4이므로 6 제거 가능
   • 4 양 옆 6 > 5 이므로 4 제거 X
   1236467
   • 6 양 옆 3<4이므로 6 제거 가능
   • 4 양 옆 6 == 6 이므로 4 제거 가능
   1236478
   • 6 양 옆 3<4이므로 6 제거 가능
   • 4 양 옆 6<7 이므로 4 제거 가능
   12372347
   • 7 양 옆 3>2 이므로 7 제거 X
   • 2 양 옆 7>3 이므로 2 제거 X
   12213
   • 2 양 옆 2>1 이므로 2 제거 X
   • 1 양 옆 2<3 이므로 1 제거 가능
   12323
   • 3 양 옆 2==2 이므로 3 제거 가능
   • 2 양 옆 3==3 이므로 2 제거 가능
   12324
   • 3 양 옆 2==2 이므로 3 제거 가능
   • 2 양 옆 3<4 이므로 2 제거 가능
   13523
   • 5 양 옆 3>2 이므로 3 제거 X
   • 2 양 옆 5>3 이므로 2 제거 X
   12321
   • diff값 양수가 두 개 존재하므로 불가능
   12313
   • 3 양 옆 2>1 이므로 3 제거 X
   • 1 양 옆 3==3 이므로 1 제거 가능
   1232
   • 3 양 옆 2 == 2이므로 3 제거 가능
   • 2는 마지막 값이므로 제거 가능
   1231
   • 3 양 옆 2 > 1 이므로 3 제거 X
   • 1은 마지막 값이므로 제거 가능
   1233
   • diff가 양수인 게 없으므로 N만큼 가능
   3123
   • 3은 가장 첫 번째 값이므로 제거 가능
   • 1은 양 옆 3>1이므로 제거 X
   2123
   • 2는 가장 첫 번째 값이므로 제거 가능
   • 1은 양 옆 2==2 이므로 제거 가능
   1123
   • diff가 양수인 게 없으므로 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));

        int N = Integer.parseInt(br.readLine());

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

        // 1 2 2 3 2

        int idx = 0, cnt = 0;
        for (int i = 0; i < N - 1; i++) {
            if (diff[i] > 0) {
                cnt++;
                idx = i;
            }
        }

        int answer = 0;
        if (cnt == 1) {
            if (idx == 0 || idx == N - 2) answer++; // 양 끝 값은 무조건 제거할 수 있으니까

            if (0 <= idx - 1 && idx + 1 < N && arr[idx - 1] <= arr[idx + 1]) answer++;
            if (idx + 2 < N && arr[idx] <= arr[idx + 2]) answer++;
            if (N == 2) answer++;
        } else if (cnt == 0) {
            answer = N;
        }

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

 

알고리즘 문제) BOJ 14846. 직사각형과 쿼리

14846번: 직사각형과 쿼리

문제 요약

• N*N행렬이 주어지고 각 쿼리를 수행
• 쿼리마다 x1 y1 x2 y2 좌표가 주어지
  • 왼쪽 윗칸 (x1,y1) 오른쪽 아래칸(x2,y2)인 부분 행렬에 포함된 서로 다른 정수 개수 출력

시간 제한

• 2초

입력

• N (1≤N≤300)
• N개의 줄에 행렬 정보
  • 1~10 자연수
• Q (1≤Q≤10만)
  • Q개의 줄에 쿼리 정보 x1 y1 x2 y2
    • x1≤x2, y1≤y2

출력

• 각 쿼리마다 정답 출력

접근법

• 숫자들 개수들을 기록할 3차원 배열 선언 cnt[300][300][10]
  • 숫자개수들을 누적해서 기록한다
  • 3차원 누적합

1 2 3 3 2 1 5 6 3

• (1,1)

1	2	3	4	5	6	7	8	9	10
1

• (1,1) ~ (1,2)

1	2	3	4	5	6	7	8	9	10
1	1

• (1,1) ~ (1,3)

1	2	3	4	5	6	7	8	9	10
1	1	1

• (1,1) ~ (2,1)

1	2	3	4	5	6	7	8	9	10
1		1

• (1,1) ~ (2,2)

1	2	3	4	5	6	7	8	9	10
1	2	1

• (1,1) ~ (2,3)

1	2	3	4	5	6	7	8	9	10
2	2	2

 

=> 2차원 누적합처럼 등장한 숫자 개수를 누적해서 기록한다.(for문 1~10)

cnt[i][j][num] = cnt[i-1][j][num] + cnt[i][j-1][num] - cnt[i-1][j-1][num];

cnt[i][j][arr[i][j]]++;

 

출력할 때도 마찬가지로 구간합 배열에서 부분배열 합계 출력하는 공식 적용,,

(1,2) ~ (2,3)

for num 1~10까지

cnt[2][3][num] - cnt[2][1][num] - cnt[0][3][num] + cnt[0][0][num]

코드

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;

        int N = Integer.parseInt(br.readLine());

        int[][] arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 개수 구간합 구하기
        int[][][] cnt = new int[N + 1][N + 1][11];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= 10; k++) {
                    cnt[i][j][k] = cnt[i-1][j][k] + cnt[i][j-1][k] - cnt[i-1][j-1][k];
                }
                cnt[i][j][arr[i][j]]++;
            }
        }




        int Q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int x1, y1, x2, y2, ans;
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            ans = 0;
            for (int i = 1; i <= 10; i++) {
                if (cnt[x2][y2][i] > 0) {
                    if (cnt[x2][y2][i] - cnt[x1 - 1][y2][i] - cnt[x2][y1 - 1][i] + cnt[x1 - 1][y1 - 1][i] > 0) {
                        ans++;
                    }
                }
            }

            sb.append(ans+"\n");

        }

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