<stdio.han>

백준 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%에서 실패가 나온다...