[코드트리/NOVICE MID] G or H 3 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int maxN = 10_000;
 
    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 K = Integer.parseInt(st.nextToken());
 
        char[] arr = new char[maxN + 1];
        int min = maxN;
        int max = 1;
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int pos = Integer.parseInt(st.nextToken());
            char c = st.nextToken().charAt(0);
 
            arr[pos] = c;
            min = Math.min(min, pos);
            max = Math.max(max, pos);
        }
 
        if(K == 1) {
            System.out.println(arr[min] == 'G' ? 1 : 2);
            return;
        }
 
        if(min + K > maxN) {
            int sum = 0;
            for(int i = min ; i <= max ; i++) {
                if(arr[i] == 'G')       sum += 1;
                else if(arr[i] == 'H')  sum += 2;
            }
            System.out.println(sum);
            return;
        }
 
        int score = 0;
        for(int i = 1 ; i <= max - K ; i++) {
            int tmp = 0;
 
            for(int j = i ; j <= i + K ; j++) {
                if(arr[j] == 'G') tmp += 1;
                else if(arr[j] == 'H') tmp += 2;
            }
            score = Math.max(score, tmp);
        }
 
        System.out.println(score);
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- Case1. K가 1이면, 하나만 출력하면 되므로 바로 출력시켜버린다.

- Case2. 해당 위치 + K의 값이 범위를 넘는다면, 그냥 다 더해버린다.

- Case3. 위의 두 경우가 아니라면, 해당 범위를 모두 돌며 해당 구간 내 원소의 합을 구하고, 이 값과 최댓값을 갱신해 비교하며 최댓값을 구한다.

 

 

 

---

🔺 다른 풀이들

입력 받은 문자가 G면, int형 배열에 1을 넣는다.

입력 받은 문자가 H면, int형 배열에 2를 넣는다.

 

모든 구간의 시작점부터 최댓값 - K까지 완전탐색을 진행하며 해당 구간 내 원소의 합을 구한다.

이 값을 최댓값과 비교해 갱신한다.

import java.util.Scanner;
 
public class Main {
    public static final int MAX_NUM = 10_000;
 
    public static int n, k;
    public static int[] arr = new int[MAX_NUM + 1];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        k = sc.nextInt();
 
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            char c = sc.next().charAt(0);
            
            if(c == 'G')    arr[x] = 1;
            else            arr[x] = 2;
        }
        
        int maxSum = 0;
        for(int i = 0 ; i <= MAX_NUM - k ; i++) {
            int sum = 0;
 
            for(int j = i ; j <= i + k ; j++) {
                sum += arr[j];
            }
            maxSum = Math.max(maxSum, sum);
        }
        
        System.out.println(maxSum);
    }
}

 

 

---

💬 느낀 점

삽질을 했다네요.....^^

 

1회독	2회독	3회독	4회독	5회독
V