[BOJ/JAVA] 백준 2812번 : 크게 만들기

2812번: 크게 만들기

 

 

---

 

 

 

• 생각

1. N-K부터 0까지 가장 큰 값을 string으로 더 해준다. 더 해줄 때 K는 +1이 되서 해당 값보다 뒤까지 포함 시킬 수 있게하고 포함된 값은 뒤에 값을 포함할때 포함 못하게 해주면 될 것 같다.  ==>> 시간 초과 

 

2. stack으로 구현.

 

 

stack으로 구현한 코드이다. 앞의 수 부터 push 해주며 stack에 맨 앞의 수가 현재 수보다 작은 경우 pop을 해주며 K값을 1씩 빼준다. 이렇게 해줘야지 앞에 작은 수가 있는 경우 포함되지 않음. 이렇게 push를 해주면 가장 앞에있는 큰 수부터 stack에 남게되는데 문제는 입력한 수가 내림차순으로 되어있는 경우 출력해야되는 수보다 stack에 많이들어가게 된다. 이 경우는 맨앞에서부터 N-K개의 수만큼 출력해주었다.

 

 

재채점 결과 위 코드가 틀렸다고 나와서 stack 부분을 deque로 고쳐 정답을 도출함.

 

 

 

• 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int N, K;
	static char[] number;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMaxValue();
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		number = br.readLine().toCharArray();
	}

	private static void FindMaxValue() {
		int temp = K;
		Stack<Character> stack = new Stack<Character>();
		for (int i = 0; i < number.length; i++) {
			// 스택의 맨 뒤의 값이 number[i]보다 작으면 삭제한다.
			// 아래 조건을 만족할 때까지 반복.
			while (temp > 0 && !stack.isEmpty() && stack.peek() < number[i]) {
				stack.pop();
				temp--;
			}
			stack.push(number[i]);
		}

		StringBuilder sb = new StringBuilder();
		if (stack.size() <= K) {
			for (int i = 0; i < stack.size(); i++) {
				sb.append(stack.get(i));
			}
		} else {   		// 앞의 수가 커서 pop을 하지 못한 경우
			for(int i = 0; i < N-K;i++) {
				sb.append(stack.get(i));
			}
		}

		System.out.println(sb);
	}
}

 

 

 

• 수정 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int N, K;
	static char[] number;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMaxValue();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.nextInt();
		K = in.nextInt();
		number = in.nextLine().toCharArray();
		sb = new StringBuilder();
	}

	private static void FindMaxValue() {
        Deque<Character> deque = new ArrayDeque<>();
		for (int i = 0; i < number.length; i++) {
			// 스택의 맨 뒤의 값이 number[i]보다 작으면 삭제한다.
			// 아래 조건을 만족할 때까지 반복.
			while (K > 0 && !deque.isEmpty() && deque.getLast() < number[i]) {
        		deque.removeLast();
				K--;
			}
			deque.addLast(number[i]);
		}

	    while(deque.size() > K) {
	       	sb.append(deque.removeFirst());
	    }
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

• 더 좋은 다른 사람코드

 

 

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int N, K;
	static String number;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMaxValue();
		System.out.println(sb.delete(sb.length() - K, sb.length()));
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.nextInt();
		K = in.nextInt();
		number = in.nextLine();
		sb = new StringBuilder();
	}

	private static void FindMaxValue() {
		for (int i = 0; i < N; i++) {
			if (K == 0) {
				sb.append(number.substring(i));
				break;
			}
			char left = number.charAt(i);
			if (left == '9') {
				sb.append(left);
				continue;
			}
			boolean isReduced = false;
			for (int j = i + 1; j < N && j < i + K + 1; j++) {
				char right = number.charAt(j);
				
				if (left < right) {
					K -= j - i;
					i = j - 1;
					isReduced = true;
					break;
				}
			}
			if (!isReduced) {
				sb.append(left);
			}
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}