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

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX_NUM = 100;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[MAX_NUM + 1];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int G = Integer.parseInt(st.nextToken());
            char c = st.nextToken().charAt(0);
 
            arr[G] = (c == 'G') ? 1 : 2;
        }
 
        int answer = 0;
        for(int i = 1 ; i <= MAX_NUM ; i++) {   // 구간 시작점
            if(arr[i] == 0)  continue;
            int g = 0;
            int h = 0;
 
            for(int j = i ; j <= MAX_NUM ; j++) {    // 구간 끝점
                if(arr[j] == 0) continue;
                else if(arr[j] == 1) g++;
                else    h++;
 
                // 조건을 만족할 때, 구간 길이 구해 최댓값과 비교 후 갱신
                if(g == 0 || h == 0 || g == h) {
                    answer = Math.max(answer, j - i);
                }
            }
        }
 
        System.out.println(answer);
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 구간 시작점 i : 1 ~ 100 까지

- 구간 끝점     j : i  ~ 100까지

 

- 시작점과 끝점 둘다 값이 0이면, 패스

- 끝점의 값이 1이거나 2면 G나 H가 들어있다는 거니까 각자 알파벳에 맞는 갯수 + 1

- 한 쪽만 값이 0이거나, 두 알파벳의 갯수가 같은 경우라면, (현재 끝점 - 시작점)과 최댓값을 비교해 갱신한다.

 

 

---

🔺 다른 풀이들

- 3중 for문....

import java.util.Scanner;
 
public class Main {
    public static final int MAX_NUM = 100;
    
    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();
 
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            char c = sc.next().charAt(0);
            
            arr[x] = (c == 'G') ? 1 : 2;
        }
        
        int maxLen = 0;
        for(int i = 0; i <= MAX_NUM; i++) {    // 시작점
            for(int j = i + 1; j <= MAX_NUM; j++) {    // 끝점
                // i와 j 위치에 사람이 있는지 확인
                if(arr[i] == 0 || arr[j] == 0)
                    continue;
                
                // 해당 구간 내 g와 h의 개수 계산
                int cntG = 0;
                int cntH = 0;
                
                for(int k = i ; k <= j ; k++) {
                    if(arr[k] == 1)    cntG++;
                    if(arr[k] == 2)    cntH++;
                }
                
                // 조건 만족 시, 구간 길이 구해 최댓값과 비교
                if(cntG == 0 || cntH == 0 || cntG == cntH) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }
                            
        System.out.print(maxLen);
    }
}

 

 

---

💬 느낀 점

이 문제는 꼬옥 복습을 해야만...

고민하다가 모르겠어서 다른 분 코드 보고 제출했다......

 

 

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

---

(참고)

[코드트리 챌린지] 6주차 ,,?