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

03 자료구조

03-5 스택과 큐

 

스택(Stack)

- 삽입과 삭제 연산이 후입선출(LIFO) 로 이뤄지는 자료구조

 

스택 용어

1. 위치

- top : 삽입과 삭제가 일어나는 위치

2. 연산

- push : top 위치에 새로운 데이터를 삽입하는 연산

- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

- peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적

 

큐(Queue)

- 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조

 

큐 용어

1. rear : 큐에서 가장 끝 데이터를 가리키는 영역

2. front : 큐에서 가장 앞의 데이터를 가리키는 영역

3. add : reat 부분에 새로운 데이터를 삽입하는 연산

4. poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산

5. peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

 

- 너비 우선 탐색에서 자주 사용

 

우선순위 큐(Priorty Queue)

- 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

- 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치

- 일반적으로 힙을 이용해 구현하는데 힘은 트리 종류 중 하나

 

---

문제 011 스택으로 오름차순 수열 만들기

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

1874번: 스택 수열

 

01단계 <문제 분석하기>

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

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

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

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

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

 

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

 

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

 

04단계 <코드 구현하기>

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        
        for (int i = 0; i < N; i++) {
        	A[i] = sc.nextInt();
        }
        
        Stack<Integer> stack = new Stack<>();
        StringBuffer bf = new StringBuffer();
        
        int num = 1;
        boolean result = true;
        for (int i = 0; i < A.length; i++) {
        	int su = A[i];
            if (su >= num) {
            	stack.push(num++);
                bf.append("+\n");
            }
            stack.pop();
            bf.append("-\n");
        	}
        	else {
        		int n = stack.pop();
            
            	if (n > su) {
                	System.out.println("NO");
	                result = false;
    	            break;
        	    }
            	else {
            		bf.append("-/n");
                }
            }
        }
        if (result) System.out.println(bf.toString());
    }
}

---

문제 012 오큰수 구하기

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

17298번: 오큰수

 

01단계 <문제 분석하기>

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

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

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

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

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

 

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

 

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

 

04단계 <코드 구현하기>

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferReader bf = new Buffered(new InputStreamReader(System.in);
        int n = Integer.parseInt(bf.readLine());
        int[] A = new int[n];
        int[] ans = new int[n];
        
        String[] str = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
        	A[i] = Integer.parseInt(str[i]);
        }
        Stack<Integer> myStack = new Stack<>();
        myStack.push(0);

		for (int i = 1; 1 < n; i++) {
        	while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
            	ans[myStack.pop()] = A[i];
            }
       		myStack.push(i);
        }
        while (!myStack.empty()) {
        	answer[myStack.pop()] -1;
        }
        BufferedWriter bw = new Buffered(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++) P
          	bw.write(ans[i] + " ");
        }
        bw.write("/n");
        bw.flush();
    }
}

---

문제 013 카드 게임

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

2164번: 카드2

 

01단계 <문제 분석하기>

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

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

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

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

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

 

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

 

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

 

04단계 <코드 구현하기>

import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        Queue<Integer> myQueue = new LinkedList<>();
        int N = sc.nextInt();
       
        for (int i = 1; i <= N; i++) {
        	myQueue.add(i);
        }
        
        while (myQueue.size() > 1) {
        	myQueue.poll();
            myQueue.add(myQueue.poll());
        }
        System.out.println(myQueue.poll());
    }
}

 

---

문제 014 절댓값 힙 구현하기

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

11286번: 절댓값 힙

 

01단계 <문제 분석하기>

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

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

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

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

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

 

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

 

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

 

04단계 <코드 구현하기>

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());
        PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) -> {
        	int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);
            if (first_abs == second_abs)
            	return o1 > o2 ? 1 : -1;
            else 
            	return first_abs - second_abs;
       	});
        for (int i = 0; i < N; i++) {
       		int request = Integer.parseInt(br.readLine());
            if( request == 0) {
            	if (MyQueue.isEmpty())
                	System.out.println("0");
            	else
                	System.out.pritnln(MyQueue.poll());
           	} else {
            	myQueue.add{request);
            }
        }
    }
}