📙[Algo] 24/01/20 ~ 24.01.21 알고리즘

알고리즘 문제) BOJ 6472. 고냥이  

16472번: 고냥이

문제 요약

• 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식

시간 제한

• 1

입력

• 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)
• 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력

• 번역기가 인식할 수 있는 문자열의 최대길이를 출력

코드

import java.io.*;

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());

        String str = br.readLine();
        int[] ch = new int[26];

        int ans = 0;
        int s = 0, e = 0, cnt = 1;
        ch[str.charAt(0)-'a']++;
        while (s <= e) {

            if (cnt <= N) {
                ans = Math.max(ans, e - s + 1);
                e++;

                if( e == str.length()) break;

                if(ch[str.charAt(e)-'a'] == 0){
                    cnt++;
                }
                ch[str.charAt(e)-'a']++;
            } else {
                if (ch[str.charAt(s)-'a'] <= 1) {
                    cnt--;
                }
                ch[str.charAt(s)-'a']--;
                s++;
            }


        }

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

 

알고리즘 문제) BOJ 20366. 같이 눈사람 만들래?

20366번: 같이 눈사람 만들래?

문제 요약

• N개의 눈덩이
• 각 눈덩이 지름은 Hi
• 눈사람은 두 개의 눈덩이로 구성
• 눈사람의 키 = 눈덩이 지름의 합
• 눈덩이 N개중 서로 다른 4개를 골라 눈사람 만들었을 때, 둘의 키 차이의 최솟값 구하기

시간 제한

• 2초(200000000)

입력

• N (4≤N≤600)
• 각 눈덩이의 지름 (1≤Hi≤1000000000)

출력

• 두 눈 사람의 키 차이 최솟값 출력

접근법

1. 완전 탐색으로 접근하기
   • 4중 for문으로 일일이 눈덩이를 고르고 최솟값 갱신
   600600600*600 ⇒ 시간초과 발생!!!
2. 최적화 진행하기
   • 일단 엘자의 눈덩이를 선택한다 ⇒ 360000
   • 2 3 4 5 5 10 11
     
     • 5, 5을 선택한 상황
     • 같은 눈덩이를 선택하는 경우는 필터링
   • 2 3 4 10 11
     s             e
   • s→2, e→11
     • s+e = 13
     • 13 > 10
     • e기준 가장 작은 애랑 더한 것이므로, e-=1
   • s→2, e→10
     • s+e = 12
     • 12 > 10
     • e기준 가장 작은 애랑 더한 것이므로, e-=1
   • s→2, e→4
     • s+e = 6
     • 6 < 10
     • s기준 가장 큰 애랑 더한 것이므로, s+=1
   • s→3, e→4
     • s+e = 7
     • 7<10
     • s기준 가장 큰 애랑 더한 것이므로, s+=1
   • s→4, e→4
     • 같은 애를 가리키므로 종료

코드

import java.io.*;
import java.util.Arrays;
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[] snow = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snow[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(snow);

        int elsaSnow, s, e, ans = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                if(i == j) continue;

                elsaSnow = snow[i] + snow[j];

                s = 0; e = N-1;

                while (s < e) {
                    if(s == i || s == j){
                        s++;
                        continue;
                    }

                    if (e == i || e == j) {
                        e--;
                        continue;
                    }

                    ans = Math.min(ans, Math.abs(elsaSnow - (snow[s] + snow[e])));

                    if (snow[s] + snow[e] < elsaSnow) {
                        s++;
                    } else if (snow[s] + snow[e] > elsaSnow) {
                        e--;
                    } else {
                        break;
                    }

                }
            }
        }

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

 

알고리즘 문제) BOJ 22945. 팀 빌딩

22945번: 팀 빌딩

문제 요약

• 개발자 N명 팀 빌딩
• 하나의 팀을 만들려면 개발자 2명이 반드시 모일 것
• 팀 능력치 = (개발자 A와 개발자 B사이 다른 개발자 수) * min(개발자 A의 능력치, B의 능력치)
• 팀 빌딩에서 나올 수 있는 능력치 최댓값?

시간 제한

• 1초

입력

• 개발자 수 N
  • 2≤N≤100,000
• N의 개발자의 각 능력치 xi가 공백으로 구분됨
  • 11≤xi≤10,000 , xi는 정수

출력

• 팀의 능력치 최댓값 출력

접근법

1. 완전 탐색으로 생각하기
   • 일단 순서를 바꾸면 안 됨
   • 2중 for문으로 일일이 모든 경우의 팀 능력치 탐색
     • A개발자 선택 → B개발자 선택
2. 최적화 하기
   1 4 2 5
   s       e 
   • s→1, e→5
     • 능력치 = 2 * 1 = 2
     • 둘 사이에 있는 개발 자 수는 최댓값이므로 남은 경우는 적을 수 밖에 없다.
     • 능력치를 비교했을 때 arr[s] < arr[e]이므로 s를 한 칸 이동
   • s → 4, e→5
     • 능력치 = 1*4 = 4
     • arr[s] < arr[e]이므로 s를 한 칸 이동
   • s → 2, e→5
     • 능력치 = 0*2= 0
     • arr[s] < arr[e]이므로 s를 한 칸 이동
   • s==e이므로 종료
   • s→ 2, e→5
     • 둘 사이에 후보가 없으므로 종료

코드

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

        int s = 0, e = N - 1, ans = 0;
        while (s < e) {

            ans = Math.max(ans, (e - s - 1) * Math.min(arr[s], arr[e]));
            if (arr[s] > arr[e]) {
                e--;
            } else {
                s++;
            }
        }

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