백준 1940, 1253, 12891(JAVA)

- start, end 2개의 포인트로 범위 지정해서 범위대로 이동하는 해결법으로 푸는 문제들이다. 

- 오름차 순으로 정렬해서 사용하자

 

📌 백준 1940

 

📌 투 포인터 이동 원칙

- 찾고자 하는 합이 기준치보다 큰 경우에는 end쪽을 줄이고, 작은 경우에는 start쪽을 올린다(증가) : while문안에서 이 조건을 검사

- 15000이 넘지 않는 재료의 개수, 시간 제한 2초이기에 정렬을 사용할 수 있음

 

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

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 m = Integer.parseInt(br.readLine()); // 엔터 기준으로 입력되기 때문에 바로 readLine후 parse
        int [] materials = new int[n];
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            materials[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        Arrays.sort(materials); // 배열 정렬
        int start = 0;
        int end = n-1;
        int count = 0;

        while (start < end) {
            if (materials[start] + materials[end] > m) {
                end--;
            } 
            else if (materials[start] + materials[end] < m) {
                start++;
            } 
            else {
                count++;
                start++;
                end--;
            }
        }

        System.out.println(count);
    }
}

 

---

 

📌 백준 1253

📌 자기 자신이 좋은 수에 포함되면 안 된다. 그래서 start와 end가 각각 i와 같은지 다른지 여부를 판단해야 한다. 이 부분 빼먹어서 실수했다. 

📌 start와 end가 만나면 더 이상 수를 찾을 수 없으므로 종료조건을 이걸로 줄 것. 

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int count = 0;
        long numbers[] = new long[num];

        for (int k = 0; k < num; k++) {
            numbers[k] = sc.nextLong();
        }
        Arrays.sort(numbers);
        for (int i = 0; i < num; i++) {
            int start = 0;
            int end = num-1;
            while (start < end) {
                if (numbers[start] + numbers[end] == numbers[i]) {
                    if (start != i && end != i) {
                        count++;
                        break;
                    } 
                    else if (start == i) {
                        start++;
                    } 
                    else if (end == i) {
                        end--;
                    }
                } 
                else if(numbers[start] + numbers[end] > numbers[i]) {
                    end--;
                }
                else {
                    start++;
                }
            }
        }

        System.out.println(count);

    }
}

 

---

 

📌 백준 12891

<tmi> 

너무 복잡해서 (?) 코드 한줄한줄에 썼다. 실버2도 힘든 코딩 실력.................................

풀다가 막혀서 책 해설을 좀 찾아봤는데, removeChar함수 부분에서 stateArray와 checkArray 같은지 판별 후 checkCondition을 먼저 감소시켰어야 했는데 순서를 뒤집어서 틀렸었다. 답이 어쩐지 계속 안 나왔었다...^_^

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

public class Main {
    static int checkArray[];
    static int stateArray[]; // ACGT 순서
    static int checkCondition;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer= new StringTokenizer(reader.readLine());

        int wholeLen = Integer.parseInt(stringTokenizer.nextToken()); // 전체 문자열 길이
        int partLen = Integer.parseInt(stringTokenizer.nextToken()); // 부분 문자열 길이
        
        int result = 0;
        checkCondition = 0;

        char charArray[] = new char[wholeLen]; // 전체 문자열 입력받을 배열
        charArray = reader.readLine().toCharArray();

        checkArray = new int[4]; // ACGT 각각 몇개 들어있어야 하는지 조건 저장 위한 배열
        stateArray = new int[4]; // 지금 읽은 부분 문자열에 ACGT 몇개씩 들어있는지 상태 저장하기 위한 배열

        stringTokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < 4; i++) {
            checkArray[i] = Integer.parseInt(stringTokenizer.nextToken());
            if (checkArray[i] == 0) {
                checkCondition++; // 만약 한 글자 아예 없어도 된다! 이 경우라면 condition 증가
            }
        }

        for (int j = 0; j < partLen; j++) {
            readChar(charArray[j]); // 맨 처음 초기 partLen 만큼 먼저 읽어주고, 그 다음 한 칸씩 이동. 
        }
        if (checkCondition == 4) {
            result++; // 처음 partLen만큼 읽었는데 만족한다면 일단 result 증가.
        }

        for (int i = partLen; i < wholeLen; i++) { 
            int start = i - partLen; // 시작 부분, 이동하면서 맨 앞은 버리기 때문에 얘는 제거가 필요;
            readChar(charArray[i]); // partLen위치부터 한 칸씩 이동하면서 읽음, 이 반복문에서 i가 마지막 인덱스
            removeChar(charArray[start]);
            if (checkCondition == 4) {
                result++; // 한 칸 이동할 때마다 checkCondition 만족하나 안하나 검사
            }
        }

        System.out.println(result);
        
        reader.close();
    }

    public static void readChar(char element) {
        switch(element) {
            case 'A' :
                stateArray[0]++;
                if (stateArray[0] == checkArray[0]) {
                    checkCondition++;
                }
                break;

            case 'C' :
                stateArray[1]++;
                if (stateArray[1] == checkArray[1]) {
                    checkCondition++;
                }
                break;

            case 'G' :
                stateArray[2]++;
                if (stateArray[2] == checkArray[2]) {
                    checkCondition++;
                }
                break;

            case 'T' :
                stateArray[3]++;
                if (stateArray[3] == checkArray[3]) {
                    checkCondition++;
                }
                break;
        }

    }

    public static void removeChar(char element) {
        switch(element) {
            case 'A' :
                if (stateArray[0] == checkArray[0]) {
                    checkCondition--; // 현재까지의 상태가 문제 조건을 담은 배열과같을 경우에만 먼저 check조건 감소(읽으면서 증가시켰던것)
                }
                stateArray[0]--; // 그러고 나서 state 감소해야함..! 먼저 state감소시키면 정확하게 checkCondition 조정불가. 
                break;

            case 'C' :
                if (stateArray[1] == checkArray[1]) {
                    checkCondition--;
                }
                stateArray[1]--;
                break;

            case 'G' :
                if (stateArray[2] == checkArray[2]) {
                    checkCondition--;
                }
                stateArray[2]--;
                break;

            case 'T' :
                if (stateArray[3] == checkArray[3]) {
                    checkCondition--;
                }
                stateArray[3]--;
                break;
        }

    }
}