JAVA Doit 알고리즘 코딩테스트 자바 편 - Day3

03 자료구조

 

03-3 투 포인터

---

문제 006 연속된 자연수의 합 구하기

백준 2018번 https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

01단계 <문제 분석하기>

1. 문자열 형태로 입력값을 받음

2. 문자 배열로 변환
3. 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하여 더함

* 문자열을 숫자형으로 변경하려면? 

- 아스키코드에서 같은 의미의 문자와 숫자의 드 값 차이는 48이다. 

- ex) 문자'1'을 숫자 1로 변환하려면 '1'-48 또는 '1'-'0' 으로연산

 

02단계 <손으로 풀어 보기>

 

03단계 <슈도코드 작성하기>

 

04단계 <코드 구현하기>

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 1;
        int start_index = 1;
        int end_index = 1;
        int sum = 1;
        while (end_index != N) {		// 현재 연속 합이 N과 같은 경우
        	if (sum == N) {
        		count++;
        		end_index++;
        		sum = sum + end_index;
    	    } else if (sum > N) {			//현재 연속 합이 N보다 더 큰경우
        		sum = sum - start_index;
        		start_index++;
    	    } else {						//현재 연속 합이 N보다 작은 경우
      		  	end_index++;
        		sum = sum + end_index;
            }
       }
       System.out.println(count);
	}
}

---

문제 007 주몽의 명령

백준 1940번 https://www.acmicpc.net/problem/1940

1940번: 주몽

 

01단계 <문제 분석하기>

1. 문자열 형태로 입력값을 받음

2. 문자 배열로 변환
3. 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하여 더함

* 문자열을 숫자형으로 변경하려면? 

- 아스키코드에서 같은 의미의 문자와 숫자의 드 값 차이는 48이다. 

- ex) 문자'1'을 숫자 1로 변환하려면 '1'-48 또는 '1'-'0' 으로연산

 

02단계 <손으로 풀어 보기>

 

03단계 <슈도코드 작성하기>

 

04단계 <코드 구현하기>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int M = Integer.parseInt(bf.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        int count = 0;
        int i = 0;
        int j = N - 1;
        while (i < j) {
            if (A[i] + A[j] < M) {
                i++;
            } else if (A[i] + A[j] > M) {
                j--;
            } else {
                count++;
                i++;
                j--;
            }
        }
        System.out.println(count);
        bf.close();
    }
}

---

문제 008 '좋은 수' 구하기

백준 1253번 https://www.acmicpc.net/problem/1253

1253번: 좋다

 

01단계 <문제 분석하기>

1. 문자열 형태로 입력값을 받음

2. 문자 배열로 변환
3. 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하여 더함

* 문자열을 숫자형으로 변경하려면? 

- 아스키코드에서 같은 의미의 문자와 숫자의 드 값 차이는 48이다. 

- ex) 문자'1'을 숫자 1로 변환하려면 '1'-48 또는 '1'-'0' 으로연산

 

02단계 <손으로 풀어 보기>

 

03단계 <슈도코드 작성하기>

 

04단계 <코드 구현하기>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int Result = 0;
        long A[] = new long[N];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(A);
        for (int k = 0; k < N; k++) {
            long find = A[k];
            int i = 0;
            int j = N - 1;
            // 투 포인터 알고리즘
            while (i < j) {
                if (A[i] + A[j] == find) {
                    if (i != k && j != k) {
                        Result++;
                        break;
                    } else if (i == k) {
                        i++;
                    } else if (j == k) {
                        j--;
                    }
                } else if (A[i] + A[j] < find) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println(Result);
        bf.close();
    }
}

---

03-4 슬라이딩 윈도우

 

---

문제 009 DNA 비밀번호

백준 12891번 https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

 

01단계 <문제 분석하기>

1. 문자열 형태로 입력값을 받음

2. 문자 배열로 변환
3. 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하여 더함

* 문자열을 숫자형으로 변경하려면? 

- 아스키코드에서 같은 의미의 문자와 숫자의 드 값 차이는 48이다. 

- ex) 문자'1'을 숫자 1로 변환하려면 '1'-48 또는 '1'-'0' 으로연산

 

02단계 <손으로 풀어 보기>

 

03단계 <슈도코드 작성하기>

 

04단계 <코드 구현하기>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int checkArr[];
    static int myArr[];
    static int checkSecret;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int Result = 0;
        char A[] = new char[S];
        checkArr = new int[4];
        myArr = new int[4];
        checkSecret = 0;
        A = bf.readLine().toCharArray();
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            if (checkArr[i] == 0)
                checkSecret++;
        }
        for (int i = 0; i < P; i++) {
            Add(A[i]);
        }
        if (checkSecret == 4)
            Result++;
        // 슬라이딩 윈도우 처리 부분

        for (int i = P; i < S; i++) {
            int j = i - P;
            Add(A[i]);
            Remove(A[j]);
            if (checkSecret == 4)
                Result++;
        }
        System.out.println(Result);
        bf.close();
    }

    private static void Add(char c) {
        switch(c) {
            case 'A':
                myArr[0]++;
                if (myArr[0] == checkArr[0])
                    checkSecret++;
                break;
            case 'C':
                myArr[1]++;
                if (myArr[1] == checkArr[1])
                    checkSecret++;
                break;
            case 'G':
                myArr[2]++;
                if (myArr[2] == checkArr[2])
                    checkSecret++;
                break;
            case 'T':
                myArr[3]++;
                if (myArr[3] == checkArr[3])
                    checkSecret++;
                break;
        }
    }

    private static void Remove(char c) {
        switch(c) {
            case 'A':
                if (myArr[0] == checkArr[0])
                    checkSecret--;
                myArr[0]--;
                break;
            case 'C':
                if (myArr[1] == checkArr[1])
                    checkSecret--;
                myArr[1]--;
                break;
            case 'G':
                if (myArr[2] == checkArr[2])
                    checkSecret--;
                myArr[2]--;
                break;
            case 'T':
                if (myArr[3] == checkArr[3])
                    checkSecret--;
                myArr[3]--;
                break;
        }
    }
}

---

문제 010  최솟값 찾기

백준 11003번 https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

01단계 <문제 분석하기>

1. 문자열 형태로 입력값을 받음

2. 문자 배열로 변환
3. 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하여 더함

* 문자열을 숫자형으로 변경하려면? 

- 아스키코드에서 같은 의미의 문자와 숫자의 드 값 차이는 48이다. 

- ex) 문자'1'을 숫자 1로 변환하려면 '1'-48 또는 '1'-'0' 으로연산

 

02단계 <손으로 풀어 보기>

 

03단계 <슈도코드 작성하기>

 

04단계 <코드 구현하기>

import org.w3c.dom.Node;

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static final Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) throws IOException {
        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 L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Deque<Node> mydeque = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken());
            // 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임

            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(now, i));
            // 범위에서 벗어난 값은 덱에서 제거
            if (mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }
    
    static class Node {
        public int value;
        public int index;
        
        Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}