<stdio.han>

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

[정답 코드]

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 w = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        Queue<Integer> truck = new LinkedList<>();
        Queue<Integer> bridge = new LinkedList<>();
        int count = 0;
        int bridgeWeight = 0;
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) {
            truck.add(Integer.parseInt(st.nextToken())); // 트럭의 무게를 큐에 담음
        }

        for (int i = 0; i < w; i++) {
            bridge.add(0); // 현재 다리에 올라와있는 트럭의 무게
        }

        while (!bridge.isEmpty()) { // 현재 다리에 올라와 있는 트럭이 존재하지 않을 때 까지
            count++; // 로직이 진행될 때 마다 시간이 1씩 증가
            bridgeWeight-=bridge.poll(); // 다리에 올라와있는 트럭이 한대 씩 다리에서 내려옴 , queue.poll() : 큐의 맨 앞의 값 추출
            if (!truck.isEmpty()) { // 큐에 담긴 트럭이 존재하지 않을 때 까지
                if (truck.peek() + bridgeWeight <= L) { // 트럭큐에 담긴 맨앞의 값과 현재 다리위에 올라와있는 트럭의 무게의 합이 L 보다 낮을때 , queue.peek() : 큐의 맨 앞의 값 확인
                    bridgeWeight += truck.peek();
                    bridge.add(truck.poll()); // 다리에 한 대 씩 올라감
                } else {
                    bridge.add(0); // 트럭큐에 트럭이 존재하지만 다리의 최대하중 때문에 다리로 못올라갈 경우 truck.poll()은 하지 않는다.
                }
            }
        }
        System.out.println(count);

    }
}

[설명]

이 문제는 큐를 활용하면 쉽게 풀 수 있다. 먼저 다리위에 트럭이 몇개가 존재하는지를 담는 큐 bridge 를 하나 만들고, 다리를 건너기 전의 트럭을 담는 truck 큐를 하나 만들어준다.

bridge 큐가 빌때까지 반복한다. 반복문이 한번 반복될때마다 트럭이 다리위에서 한칸씩 전진하는 구조이다. 

한칸 전진할 때마다 truck 큐를 확인하며 truck 큐를 하나 꺼내 다리위에 올라갔을 때 최대하중을 넘는지 안넘는지 체크하고 넘지않는다면 bridge 큐에 넣고 넘는다면 bridge에 0을 집어 넣는다. 

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

[정답 코드]

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

public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static char[][] graph; // 지도
    static int count; // 섬 근처의 바다의 수
    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 R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        int up = R; // 지도의 가장 위
        int down = 0; // 지도의 가장 아래
        int left = C; // 지도의 가장 왼쪽
        int right = 0; // 지도의 가장 아래쪽

        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (graph[i][j] == 'X') {
                    count = 0;
                    for (int k = 0; k < 4; k++) { // 우 좌 하 상 순서 4방 탐색
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && ny >= 0 && nx < R && ny < C) { // 지도 안에 있을경우
                            if (graph[nx][ny] == '.') { // 근처가 바다일 경우
                                count++;
                            }
                        } else { // 지도의 바깥부분도 바다
                            count++;
                        }
                    }
                    if (count >= 3) { // 바다가 3면 이상일 경우
                        graph[i][j] = 'S'; // 임의의 값 S 로 변경
                    }
                }
                if (graph[i][j] == 'X') { // 지도의 가장 위, 아래, 왼쪽, 오른쪽 의 좌표를 갱신
                    up = Math.min(up, i);
                    down = Math.max(down, i);
                    left = Math.min(left, j);
                    right = Math.max(right, j);
                }
            }
        }

        // 새로운 지도를 그려줌
        for (int i = up; i <= down; i++) {
            for (int j = left; j <= right; j++) {
                char c = graph[i][j];
                if (c == 'X') {
                    bw.write(c);
                } else {
                    bw.write('.');
                }
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[설명]

4방탐색을 활용한 구현문제이다. 지도를 탐색하다가 섬을 만나면 4방탐색을 실시한다. 4방 탐색 dx/dy 기법을 활용해준다.

4방탐색을 하면서 바다의 수를  카운팅해 바다가 3면이상이면 섬을 지도에서 지워준다. 

지도를 탐색해 나아가면서 모든 섬의 좌표를 체크해 지도의 가장 위에 있는 섬, 아래있는 섬.. 등의 좌표를 갱신해 나간다.

탐색이 끝났다면 가장 바깥 부분의 섬의 좌표들을 활용해 새로운 지도를 그려준다.

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로 빠져나온다.

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

[틀린 코드]

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


        int max = 0;
        int answer = 0;
        for (int i = 0; i <= N - X; i++) {
            int tmp = 0;
            for (int j = i; j < i + X; j++) { // X기간동안의 방문자 수의 합
                tmp += visitors[j];
            }
            if (tmp > max) { // X기간동안 최고 방문자수가 갱신될 경우
                answer = 0;
                max = Math.max(tmp, max);
            }
            if (tmp == max) { // 최고방문자수가 max 와 같은 기간 카운팅
                answer++;
            }
        }
        System.out.println(max);
        System.out.println(answer);
    }
}

[정답 코드]

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

        int sum = 0;
        for (int i = 0; i < X; i++) {
            sum += visitors[i];
        }


        int max = sum;
        int answer = 1;
        for (int i = 0; i < N - X; i++) { // 슬라이딩 윈도우

            //한칸 씩 이동
            sum += visitors[i+X];
            sum -= visitors[i];

            if (sum == max) { // 최다 방문자수가 유지될 경우 answer++
                answer++;
            }

            if (sum > max) { // 최다 방문자수가 갱신되었을 경우
                answer = 1;
                max = sum;
            }

        }
        if (max == 0) { // 최대 방문자 수가 0이라면 SAD 출력
            System.out.println("SAD");
        } else {
            System.out.println(max);
            System.out.println(answer);
        }
    }
}

[설명]

이 문제는 슬라이딩 윈도우 기법을 활용해야 한다. 처음에 이 문제를 풀었을때는 이중 for문으로 문제를 풀었었다. 그러자 시간초과 떴다. 그래서 2중for문을 해결하기 위해 for문을 하나로 두고 다시 풀었다.

먼저 입력을 받고 입력받은것중에 슬라이딩 윈도우로직을 사용할 구간만큼 미리 합을 구해놓는다.

그리고 for문을 이용해 한칸씩 이동해 나아가며 합을 계산한다. 

계산한 합이 알고있는 max값보다 클 경우 max값을 갱신하고 answer를 1로 초기화시킨다.

max값과 새로 이동해 계산한 합의 값이 같을 경우 answer를 1 증가시킨다.