<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/1931

[난이도]

- Silver 1

[알고리즘]

- 그리디

[코드]

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));
        int N = Integer.parseInt(br.readLine());
        int[][] meetings = new int[N][2];

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

        // 끝나는 시간을 기준으로 정렬, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int count = 0;
        int lastEndTime = 0;

        for (int i = 0; i < N; i++) {
            if (meetings[i][0] >= lastEndTime) {
                lastEndTime = meetings[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

[풀이]

정렬을 할 때 끝나는 시간을 기준으로 오름차순 정렬을 해준다.

그 후 현재시간이 0이라고 할 때 해당 배열의 시작 시간이 현재시간보다 크거나 같을 경우 현재시간을 해당 배열의 끝나는시간으로 변경해준다. 변경될 때 마다 count를 늘려준다.

https://www.acmicpc.net/problem/20310

[25점 정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        char[] words = br.readLine().toCharArray();
        int countZero = 0;
        int countOne = 0;

        for (char word : words) {
            if (word == '0') {
                countZero++; // 0의 개수를 카운팅
            } else {
                countOne++; // 1의 개수를 카운팅
            }
        }
        for (int i = 0; i < countZero / 2; i++) { // 0의 개수의 절반을 날린것을 먼저 출력
            bw.write("0");
        }
        for (int i = 0; i < countOne / 2; i++) { // 1의 개수의 절반을 날린것을 뒤에 출력
            bw.write("1");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[100점 정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String words = br.readLine();
        int countZero = 0;
        int countOne = 0;

        for (int i = 0; i < words.length(); i++) {
            if (words.charAt(i) == '0') { // 0의 개수 카운팅
                countZero++;
            } else { // 1의 개수 카운팅
                countOne++;
            }
        }
        countZero/=2; // 0의 개수 카운팅 한것의 절반을 날림
        countOne/=2; // 1의 개수 카운팅 한것의 절반을 날림
        
        // 1 제거 로직
        int i = 0;
        while (countOne != 0) {
            if (words.charAt(i) == '1') { // 해당 인덱스의 가 1일 경우
                words = words.substring(0, i) + words.substring(i + 1); // i번 인덱스를 제거한다
                countOne--;
                i = -1; // i번 인덱스를 제거할 경우 i를 다시 초기화 해주어야 인덱스가 꼬이지 않는다
            }
            i++;
        }

        // 0 제거 로직
        int j = words.length() - 1;
        while (countZero != 0) {
            if (words.charAt(j) == '0') { // 해당 인덱스의 가 0일 경우
                words = words.substring(0, j) + words.substring(j + 1); // j번 인덱스를 제거한다
                countZero--;
                j = words.length(); // j번 인덱스를 제거할 경우 j를 다시 초기화 해주어야 인덱스가 꼬이지 않는다
            }
            j--;
        }
        System.out.println(words);

        bw.flush();
        bw.close();
        br.close();
    }
}

[설명]

이 문제는 그리디 알고리즘과 문자열을 잘 다뤄야한다. 먼저 처음에 25점 짜리 정답은 문제를 잘못이해해 0과 1의 개수를 카운팅 한후 0과1을 단순 재배열해 0의 개수의 절반만큼 0출력 후 나머지 1의 개수의 절반만큼 1출력했다. 그 결과 25점짜리 정답을 맞았다.

다시 문제를 보니 입력받은 문자열을 다 뜯어서 재배치하는것이 아니라 입력받은 문자열에서 0과 1을 제거해 사전순으로 출력하는것이다.

1을 제거하는 로직을 보면 for문이 아닌 while문으로 작성한 이유는 for문으로 작성할 경우 String.substring() 으로 해당 인덱스의 문자를 제거할 경우 제거한 인덱스만큼 문자열이 줄어들어 i가 바라보는 인덱스와 검사해야할 문자열의 인덱스가 꼬이는 경우가 발생하기 때문에 while문으로 작성했다. String.substring()으로 문자열을 수정했을 경우 i를 초기화시켜 다시 처음부터 문자열을 체크했다. 지금보니 문자열을 i = -1 이런식으로 처음으로 초기화시킬 필요없이 수정한 인덱스 바로 뒤로 초기화시켜도 되는것같다.

https://www.acmicpc.net/problem/19941

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        char[] arr = br.readLine().toCharArray();
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] == 'P') { // 사람일 경우
                int startIndex = Math.max(i - K, 0); // 0보다 작으면 안됨
                int endIndex = Math.min(i + K, N - 1); // 배열의 끝을 넘어가면 안됨
                for (int j = startIndex; j <= endIndex; j++) {
                    if (arr[j] == 'H') {
                        count++;
                        arr[j] = 'X'; // 햄버거가 있다면 햄버거자리를 임의의 문자로 대체
                        break;
                    }
                }
            }

        }
        System.out.println(count);
    }
}

[설명]

이 문제는 그리디 알고리즘 문제이다. 슬라이딩 윈도우 처럼 시작인덱스와 끝인덱스를 설정한 후 이동해 나아가면 햄버거를 찾고, 햄버거를 찾았다면 다른 사람이 햄버거를 중복으로 찾는 경우가 발생할 수 있기 때문에 햄버거를 찾았다면 임의의 문자로 대체하고 break로 빠져나온다.