Do it! 알고리즘 코딩테스트 (11번 ~ 13번)

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

---

잘못된 풀이

import java.io.*;
import java.util.*;
public class Baek1874 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [] arr = new int [n];
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int [] arr2 = arr.clone();
		
		Arrays.sort(arr2);
		
		Stack<Integer> stack = new Stack<>();
		int i = 0;
		int j = 0;
		
		
		//System.out.println(stack);
		//stack = 1
		while(j != n) {
			if(stack.isEmpty()) {
				stack.push(arr2[i]);
				System.out.println("+");
			}
			if(arr[j] != stack.peek()) {  //i 가 [0] 4 != 1 true
				stack.push(arr2[i + 1]);  // arr2[1] = 2 i = 1
				System.out.println("+");
				i++;
			}
			else if(arr[j] == stack.peek()) {
				stack.pop();
				System.out.println("-");
				j++;
			}
			else {
				System.out.println("NO");
			}
		}
	}
}

---

내가 떠올린 풀이 해설

배열을 하나 더 만들어서 복사해서 정렬한 다음 배열 인덱스 탐색하는 i와 j를 만들어서 문제를 풀려고 했다.

peek으로 스택 최상단에 있는 수와 비교했을 때 복사한 배열의 수와 다르면 push 하고 같으면 pop을 하려고 했다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1874 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int num = 1;
		boolean result = true;
		
		Stack<Integer> stack = new Stack<>();
		StringBuffer bf = new StringBuffer();
		
		for(int i = 0; i < n; i++) {
			int su = arr[i];
			if(su >= num) {
				while(su >= num) {
					stack.push(num++);
					bf.append("+\\n");
				}
				stack.pop();
				bf.append("-\\n");
			}
			else {
				int k = stack.pop();
				if(k < su) {
					System.out.println("NO");
					result = false;
					break;
				}
				else {

					bf.append("-\\n");
				}
			}
		}
		if(result) {
			System.out.println(bf.toString());
		}
	}
}

---

문제점

예제 출력 1번은 내가 짠 코드로 가능했지만 예제 출력 2번은 구현하지 못했다.

인덱스로 배열을 탐색했을 때 인덱스가 다음으로 이동했을 때 비교하기 전 인덱스로 다시 돌아가는 것을 구현하지 못했다.

---

12번 문제 오큰수 구하기

---

잘못된 풀이

import java.io.*;
import java.util.*;
public class Baek17298 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Stack<Integer> stack = new Stack<>();
		//int i = 1;
		stack.push(arr[0]);
		for(int j = 1; j < n; j++) {
			for(int i = 1; i < n; i++) {
				if(stack.peek() < arr[i]) {   
					stack.push(arr[i]);       
					System.out.print(arr[i] + " ");  
					while(stack.size() != 1) {
						stack.pop();                          
					}
					stack.push(arr[i]);
					
				}
				else if(stack.peek() > arr[i]) {
					
				}
				else {
					System.out.print("-1 ");
					//i++;
				}
			}
		}
		br.close();
	}
}

---

내가 떠올린 풀이 해설

위에 풀었던 문제와 비슷한 방식을 떠올렸다. 이중 for문으로 for문이 돌면서 스택에 peek으로 젤 위에 값과 배열의 다음 값을 비교하는데 배열의 값이 크면 스택에 push 했다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek17298 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [] arr = new int[n]; //수열배열 생성 
		int [] answer = new int [n]; //정답 배열 생성 
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Stack<Integer> stack = new Stack<>();
		
		stack.push(0); // 처음에는 항상 스택이 비어 있으므로 최초 값을 push해 초기화 
		for(int i = 1; i < n; i++) {
			//스택이 비어있지 않고 현재 수열이 스택 top 인덱스가 가리키는 수열보다 클 경우 
			while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
				answer[stack.pop()] = arr[i]; // 정답 배열에 오큰수를 현재 수열로 저장하기 
			}
			stack.push(i);  //신규 데이터 push 
		}
		while(!stack.isEmpty()) { //반복문을 다 돌고 나왔는데 스택이 비어 있지 않다면 빌 때까지 
			answer[stack.pop()] = -1; //스택에 쌓인 index에 -1을 넣고 
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for(int i = 0; i < n; i++) {
			bw.write(answer[i] + " ");
		}
		bw.close();
		br.close();
	}
}

---

문제점

위와 똑같은 문제가 있었다. 인덱스로 탐색을 해서 그 전으로 돌아와서 비교하는 법을 모르겠다.

그 전으로 돌아오지 못해 처음 5와 7을 잘 출력이 되는데 그 뒤로부터는 비교할 수가 없어서 -1, -1이 출력됩니다.

풀이를 보면 저번과 같이 BufferedWriter로 출력하는 것을 볼 수가 있는데 System.out.print로 출력을 할시 시간 초과가 발생합니다

---

13번 문제 카드 게임

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2164 {

	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Queue<Integer> que = new LinkedList<>();
		
		for(int i = 1; i <= n; i++) {
			que.offer(i);
		}
		
		while(que.size() != 1) {
			que.poll();
			que.offer(que.poll());
		}
		System.out.println(que.poll());
	}
}

---

내가 떠올린 풀이 해설

큐에 대한 선입 선출의 개념을 알고 있으면 쉽게 풀 수 있는 문제라고 생각한다. 카드의 개수의 최대가 500,000이므로 시간 복잡도의 제약도 크지 않다.

 

 

오늘의 회고

오늘은 자료구조의 알고리즘을 풀어봤는데 조건에 따라 구현하는 방법이 어려웠습니다. 책에 있는 문제들이 기본 문제도 있지만 많이 어려운 문제도 있어 시간이 오래 걸리는 것 같습니다. 알고리즘 공부하면서 느끼는 점은 시간이 지날수록 알고리즘 공부에 대한 방향성이 조금씩은 잡혀가고 있는 것 같습니다. 내일은 오늘 풀었던 문제 복습과 스택, 큐, 덱에 대한 오늘보단 쉬운 5문제를 풀겠습니다.