코딩테스트

1. 백준 1253

정렬과 투 포인터를 이용

[풀이] 실패 : 음의 정수도 포함인 것을 간과하여 문제 풀이에 실패

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) numbers[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(numbers);

        int count = 0;
        for (int i = 0; i < N; i++) {
            int start = 0;
            int end = i-1;
            while (start < end) {
                if (numbers[start] + numbers[end] == numbers[i]) {
                    count++;
                    break;
                } else if (numbers[start] + numbers[end] < numbers[i]) {
                    start++;
                } else {
                    end--;
                }
            }
        }
        System.out.println(count);
    }
}

 

[맞은 풀이]

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) numbers[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(numbers);

        int count = 0;
        for (int i = 0; i < N; i++) {
            int start = 0;
            int end = N-1;
            while (start < end) {
                if (numbers[start] + numbers[end] == numbers[i]) {
                    if (start != i && end != i) {
                        count++;
                        break;
                    } else if (start == i) {
                        start++;
                    } else {
                        end--;
                    }
                } else if (numbers[start] + numbers[end] < numbers[i]) {
                    start++;
                } else {
                    end--;
                }
            }
        }
        System.out.println(count);
    }
}

 

2. 백준 12891

슬라이딩 윈도우 알고리즘 이용

[풀이] 시간 초과 : 슬라이딩 윈도우 알고리즘을 모르는 상태로 풀이하여 중복되는 로직으로인해 시간 초과됨

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

        String DNA = br.readLine();

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

        int count = 0;
        for (int i = 0; i <= S - P; i++) {
            int[] B = new int[4];
            for (int j = i; j < i + P; j++) {
                if (DNA.charAt(j) == 'A') {
                    B[0]++;
                } else if (DNA.charAt(j) == 'C') {
                    B[1]++;
                } else if (DNA.charAt(j) == 'G') {
                    B[2]++;
                } else {
                    B[3]++;
                }
            }
            count++;
            for (int k = 0; k < 4; k++) {
                if (A[k] < B[k]) {
                    count--;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

 

[맞은 풀이]

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

public class Main {
    static int[] B = new int[4];
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int count = S - P + 1;

        String DNA = br.readLine();

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

        for (int i = 0; i < P; i++) {
            Add(DNA.charAt(i));
        }

        for (int i = 0; i <= S - P; i++) {

            if (i != 0) {
                Remove(DNA.charAt(i-1));
                Add(DNA.charAt(i+P-1));
            }

            for (int j = 0; j < 4; j++) {
                if (A[j] > B[j]) {
                    count--;
                    break;
                }
            }
        }
        System.out.println(count);
    }

    private static void Add(char a) {
        if (a == 'A') {
            B[0]++;
        } else if (a == 'C') {
            B[1]++;
        } else if (a == 'G') {
            B[2]++;
        } else {
            B[3]++;
        }
    }

    private static void Remove(char a) {
        if (a == 'A') {
            B[0]--;
        } else if (a == 'C') {
            B[1]--;
        } else if (a == 'G') {
            B[2]--;
        } else {
            B[3]--;
        }
    }
}

 

3. 백준 11003

[풀이] 시간 초과 : 얼추 비슷하게 알고리즘을 생각했지만 정렬부분에서 시간초과가 났음 (시간복잡도 → n*nlogn → n^2)

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

        st = new StringTokenizer(br.readLine());

        List<Long> A = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            A.add(Long.parseLong(st.nextToken()));
        }

        List<Long> B = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            if (i - L + 1 > 0) {
                B.remove(A.get(i-L));
            }
            B.add(A.get(i));

            if (i == N - 1) {
                System.out.print(min(B));
            } else {
                System.out.print(min(B) + " ");
            }
        }
    }

    public static Long min(List<Long> A) {
        A.sort(Comparator.naturalOrder());
        return A.get(0);
    }
}

 

[다른풀이] 정렬 방식의 알고리즘을 바꿔서 시간복잡도를 낮춤

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        Deque<Node> deque = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            while (!deque.isEmpty() && deque.getLast().value > num) {
                deque.removeLast();
            }
            deque.addLast(new Node(num, i));

            if (deque.getFirst().index <= i - L) {
                deque.removeFirst();
            }
            bw.write(deque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

    static class Node {
        public int value;
        public int index;

        public Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}