📙[Algo] 24.08.20 알고리즘

알고리즘 문제) BOJ 30646. 최대 합 순서쌍의 개수

• 링크 : https://www.acmicpc.net/problem/30646

문제 요약

• 크기가 N인 배열 a
• 배열 a의 임의의 위치를 나타내는 두 수 i, j를 골랐을 때, 아래 두 조건을 만족하면 같은 수 순서쌍 (i, j)를 만들 수 있다
  • 1 ≤ i ≤ j ≤ N
  • ai = aj
• 만들어진 같은 수 순서쌍 (i, j)의 합은 ai부터 aj까지의 합 ai + ai+1 + ai+2 + … + aj-1 + aj
• 이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫 번째 배열 a의 크기 N
  • 1 ≤ N ≤ 200,000
• 두 번째 줄에 배열 a의 원소 a1, a2, …, aN
  • 1 ≤ ai ≤ 10^9

출력

• 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합과 최대 합을 가진 같은 수 순서쌍의 개수를 출력

접근법

• 누적합 + 맵 사용
• N이 20만으로 O(N)안에 연산을 마쳐야 한다.
• 정수를 key를 갖고, 해당 정수의 인덱스를 value로 갖는 map 생성
• 또한, 매번 구간 합을 구하지 않기 위해 누적합 배열 prefix 생성 → 값을 입력 받음과 동시에 prefix배열 갱신
• 만약 이미 map에 현재 가리키는 정수(cur)를 key로 갖고 있는게 존재한다면, value에 저장된 인덱스(map.get(cur))부터 현재 가리키는 인덱스까지의 누적합 구해서 최댓값 갱신 ⇒ 누적합 배열 사용(prefix[i] - prefix[map.get(cur) - 1])
  • 이때, 문제에서 i = j인 경우에도 누적합을 찾아야 하므로, map에 존재하지 않는 경우에는 key = 정수(cur), value = 인덱스(i)로 저장 후, 마찬가지로 max값을 갱신해줌

코드

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

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

        int N = Integer.parseInt(br.readLine());
        long[] prefix = new long[N + 1];
        Map<Integer, Integer> map = new HashMap<>();

        st = new StringTokenizer(br.readLine());
        long max = 0, diffSum; int cnt = 0, cur;
        for (int i = 1; i <= N; i++) {
            cur = Integer.parseInt(st.nextToken());
            prefix[i] = prefix[i - 1] + cur;
            if (!map.containsKey(cur)) {
                map.put(cur, i);
                diffSum = cur;
            }
            else diffSum = prefix[i] - prefix[map.get(cur) - 1];

            if (max < diffSum) {
                max = diffSum;
                cnt = 1;
            } else if (max == diffSum) {
                cnt++;
            }
        }

        System.out.println(max + " " + cnt);
    }
}

 

알고리즘 문제) BOJ 21956. Treasure

• 링크 : https://www.acmicpc.net/problem/21956

문제 요약

• N개의 소문자 영어 문자열이 존재
• 이때, 문자열에서 연속된 위치에 정확히 K개의 동일한 문자가 나타나는 첫 번째 문자열을 제거
• 이 과정을 더 이상 K개의 연속된 동일한 문자가 나타나지 않을 때까지 반복
• 연속된 위치에서 정확히 K개의 동일한 문자가 나타나는 첫 번째 문자열을 차례로 제거한 후, 그러한 문자열이 더 이상 남아 있지 않을 때의 최종 문자열을 구하세요

시간 제한

• 1초

입력

• 첫 번째 줄에는 두 개의 정수 N과 K
• 두 번째 줄에는 N개의 소문자 영어 문자열

출력

• 모든 가능한 제거가 완료된 후의 소문자 영어 문자열을 출력

접근법

• 문자열 길이가 20만까지 가능하므로, O(N)안에 연산을 마쳐야 함
• 문자열을 순회하면서, 스택이 비어있을 경우 스택에 현재 가리키는 문자와 연속해서 등장한 횟수를 저장 (Char 클래스 생성)
• 만약 스택이 비어있지 않다면, 스택 상단 값의 문자 c 와 현재 가리키는 문자(cur)를 비교했을 때, 같을 경우 스택 상단의 값의 cnt값 + 1로 갱신한다.
  • 이떄, cnt값이 K와 같다면, 해당 글자는 stack에서 제거
• 문자열 끝까지 순회할때까지 위 과정을 반복하다보면, 결국 스택에는 제거할 수 없는 문자들만 남게 된다.
  • 따라서, 해당 값들을 순회하면서, StringBuilder객체에 각 값들의 개수만큼 문자를 삽입하고, 최종적으로 역순으로 출력하도록 함(스택은 LIFO구조라서 가장 최근에 넣은 문자부터 나오기 때문)

코드

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

public class Main {

    static class Char {
        char c;
        int cnt;

        Char(char c, int cnt) {
            this.c = c;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        String str = br.readLine();
        Stack<Char> stack = new Stack<>();

        char cur;
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            cur = str.charAt(i);

            if (!stack.isEmpty() && cur == stack.peek().c) {
                stack.peek().cnt++;

                if (stack.peek().cnt == K) {
                    stack.pop();
                }
            }
            else {
                stack.push(new Char(cur, 1));
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            for (int i = 0; i < stack.peek().cnt; i++) {
                sb.append(stack.peek().c);
            }
            stack.pop();
        }
        System.out.println(sb.reverse());
    }
}