백준(2812번) - 크게 만들기(Java) (자료구조)

 코드가 크게 2번 정도 바뀐 문제이다. 문제 푸는 방식은 전부 똑같았다.

 

 현재 위치(i)의 숫자와 다음 위치(i+1)의 숫자를 비교해 현재 위치가 더 작을 경우 현재 위치의 숫자를 제외시켜 주는 문제이다.

<시간초과 문제>

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


public class Main
{
	static int n, k;
	static ArrayList<Character> list;
	static String str;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		str = br.readLine();
		list = new ArrayList<>();
		
		for(int i = 0 ; i < n ; i++)
		{
			list.add(str.charAt(i));
		}
		
		while(k > 0)
		{
			boolean delete = false;
			
			for(int i = 0 ; i < list.size()-1 ; i++)
			{
				if(list.get(i) < list.get(i+1))
				{
					delete = true;
					list.remove(i);
					break;
				}
			}
			
			if(!delete) list.remove(list.size()-1);	//올바르게 정렬되어 있으니 뒷 숫자를 잘라준다.
			
			k--;
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0 ; i < list.size() ; i++)
		{
			sb.append(Integer.toString(list.get(i)-'0'));
		}
		
		System.out.println(sb);
	}
}

 ArrayList로 구현을 하다 보니, 이런 모양이 되었다.

<72%>

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


public class Main
{
	static int n, k;
	static Stack<Character> stack;
	static String str;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		str = br.readLine();
		stack = new Stack<>();
		
		for(int i = 0 ; i < str.length() ; i++)
		{
			while(!stack.isEmpty() && stack.peek() < str.charAt(i) && k > 0)
			{
				k--;
				stack.pop();
			}
			
			stack.push(str.charAt(i));
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(char ch : stack)
		{
			sb.append(ch);
		}
		
		System.out.println(sb);
	}
}

조금 더 간소화되어 <시간 초과> 문제는 해결됐으나 크게 보는 문제는 2가지였다.

1. Stack으로 해결할 수 있는 문제가 아니었다는 점

2. 올바르게 들어오면 뒷자리를 잘라주지 못한다는 점

 

처음에 Deque도 앞 뒤 자유롭게 삽입, 삭제가 가능해 고려대상이었으나, Stack으로 될 것 같아 시도했지만 72% 잘리는 것을 보고 Deque로 전환했다.

 

<문제>

https://www.acmicpc.net/problem/2812

 

<소스코드>

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


public class Main
{
	static int n, k;
	static Deque<Character> dq;
	static String str;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		str = br.readLine();
		dq = new ArrayDeque<>();
		
		for(int i = 0 ; i < str.length() ; i++)
		{
			while(!dq.isEmpty() && dq.getLast() < str.charAt(i) && k > 0)
			{
				k--;
				dq.removeLast();
			}
			
			dq.addLast(str.charAt(i));
		}
		
		StringBuilder sb = new StringBuilder();
		
		while(dq.size() > k)
		{
			sb.append(dq.removeFirst());
		}
		
		System.out.println(sb);
	}
}