<stdio.han>

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

[정답 코드]

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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;

        while (left <= N && right <= N) {
            if (sum >= S) {
                answer = Math.min(answer, right - left);
                sum -= arr[left++];
            } else if (sum < S) {
                sum += arr[right++];
            }
        }
        System.out.println(answer==Integer.MAX_VALUE ? 0 : answer);
    }
}

[설명]

투포인터 알고리즘을 활용한다.

sum 이 S보다 작을 경우 sum += arr[right++]를 하고

sum이 S보다 크거나 같을 경우 sum -= arr[left--]를 해준다. 그리고 동시에 right - left를 해주어 더 작은값을 출력해준다.

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

[정답 코드]

import org.w3c.dom.html.HTMLParagraphElement;

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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int answer = 0;

        for (int i = 0; i < N; i++) {
            int left = 0;
            int right = N - 1;
            int target = arr[i];
            while (left < right) {
                int sum = arr[left] + arr[right];
                if (sum == target) { // sum이 target과 같을 경우
                    if (left != i && right != i) { // left와 right가 같은 수가 아닐경우
                        answer++;
                        break;
                    } else if (left == i) { // 현재 탐색하려는 숫자를 사용하면 안됨
                        left++;
                    } else { // 현재 탐색하려는 숫자를 사용하면 안됨
                        right--;
                    }
                } else if (sum < target) { //sum이 target보다 작을 경우
                    left++;
                } else { // sum이 target보다 클 경우
                    right--;
                }
            }
        }
        System.out.println(answer);
    }
}

[설명]

투 포인터로 풀었다. 배열을 입력받은 후 arr[left] 와 arr[right]를 더한값을 target 과 비교해가며 left를 늘리고 right를 줄이며 탐색한다.

                    if (left != i && right != i) { // left와 right가 같은 수가 아닐경우
                        answer++;
                        break;
                    } else if (left == i) { // 현재 탐색하려는 숫자를 사용하면 안됨
                        left++;
                    } else { // 현재 탐색하려는 숫자를 사용하면 안됨
                        right--;
                    }

 여기서 else if 구문과 else 구문이 이해가 너무안가서 1시간 넘게 이해를 못하고있었다. 

예를 들어 현재 3번 인덱스를 target으로 두고 탐색하고있을 때, 3번인덱스 + X인덱스를 더한값을 찾으려고 했을 경우라는 의미이다. 3번인덱스를 찾으려는데 3번인덱스를 더해서 찾는건 말이 안되기 때문이다.

백준 17609번: 회문[JAVA]

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

[정답 코드]

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

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

        // 문자열의 개수를 나타내는 정수 T
        int T = Integer.parseInt(st.nextToken());
        // 문자열을담는 배열
        String[] arr = new String[T];
        String str = "";

        //문자열 입력받은 후 배열에 저장
        for (int i = 0; i < T; i++) {
            str = br.readLine();
            System.out.println(palindrome(0, str.length()- 1, str, 0));
        }
    }

    // 로직
    private static int palindrome(int start, int end, String s, int check) {
        // 문자 삭제를 2번이상 할 경우 바로 2를 반환
        if (check >= 2) {
            return 2;
        }

        // start 포인터와 end 포인터가 만나거나 지나치기 전까지 반복
        while (start < end) {
						// 같을 경우 포인터 한칸 진행
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                // ex) abbab 같은 경우 두 경우를 비교해 더 작은 수를 반환
                return Math.min(palindrome(start + 1, end, s, check + 1), palindrome(start, end - 1, s, check + 1));
            }
        }
        return check;
    }
}

[정리]

투 포인터 알고리즘과 재귀함수를 활용해 풀었다. 처음엔 재귀함수 없이 while 문과 for 문으로 해결하려고 했지만 반례를 발견할 때 마다 코드가 한줄 한줄 추가되더니 스파게티 코드가 되었다. 몇시간 동안 수정 후 반례 abbab 를 만났을 때 왼쪽 문자를 제거했을 경우와 오른쪽 문자를 제거했을 경우 두 가지 모두를 생각해야 한다는 걸 깨닫고 수정하려 했지만 이미 코드는 난장판이 되어있었다. 그래서 싹 다 지우고 혼자 해결하는것을 포기하고 구글링을하며 반정도 클론코딩을 하며 해결했다. 4시간 정도 걸려서 풀었지만 막상 풀고나니 처음 시작을 제대로 했더라면 금방 풀수있는 문제였다.

백준 15961번: 회전 초밥[JAVA]

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

[정답 코드]

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

        // N=접시의 수, d=초밥의 가짓수, k=연속해서 먹는 접시의 수, c=쿠폰 번호
        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // 회전 초밥 배열
        int[] dishes = new int[N];
        for(int i=0;i<N;i++){
            dishes[i] = Integer.parseInt(br.readLine());
        }

        //먹은 초밥 배열 먹으면 1, 안먹으면 0
        int[] eat = new int[d+1];

        // 0번부터 k개 먹었을 경우 상태
        int cnt = 0;
        for(int i=0;i<k;i++){
            if(eat[dishes[i]] == 0) {
                cnt++;
            }
            eat[dishes[i]]++;
        }

        // 먹을 수 있는 초밥의 가짓수의 최댓값, 기본 값은 0번부터 k개 먹었을 경우의 최대값
        int max = cnt;

        //투포인터 초기화
        int start = 1;
        int end = k;

        //로직
        while(true){
            if(eat[dishes[start-1]] == 1) { // start-1 초밥이 이미 먹은 초밥이라면 cnt--
                cnt--;
            }
            // else 아니라면 그대로
            //먹은 초밥 배열 --
            eat[dishes[start-1]]--;

            //새로운 초밥이 먹은 초밥이라면 cnt++
            if(eat[dishes[end]] == 0) {
                cnt++;
            }
            // else 아니라면 그대로
            //새로 먹은 초밥 배열 ++
            eat[dishes[end]]++;

            if(eat[c] == 0) { //쿠폰초밥을 안먹었다면 max, cnt+1 중 큰 수
                max = Math.max(max, cnt+1);
            } else { //쿠폰초밥을 이미 먹었다면 그냥 비교
                max = Math.max(max, cnt);
            }

            start++;
            end++;
            if(end==N) { //end포인터가 배열끝까지 갔을 경우 처음으로
                end = 0;
            }
            if(start==N) { //start 포인터가 배열 끝까지 갔을 경우 종료
                break;
            }
        }
        System.out.println(max);

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

[정리]

투 포인터 알고리즘을 이용해 푸는 문제이다. 시작지점과 끝지점 포인터를 만들어 창문이 움직이듯이 정해진 범위를 이동해 가며 푸는 문제이다. 슬라이딩 윈도우 알고리즘이라고도 부른다.

백준 2531번과 N의 범위를 제외하고 똑같은 문제이다. 이유는 모르겠지만 2531번 문제에서는 96%에서 실패가 나온다...