[백준 5397] 키로거 (JAVA)

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

5397번: 키로거

 

 

이번 포스팅에서는 스택을 활용하기 좋은 문제를 다뤄보도록 하겠다.

 

먼저 문제 분석을 하자면,

 

입력받은 문자열중 < , > , - , 그 이외의 문자인경우로 나눠 다른 동작을 수행하게 한 후

최종 결과를 출력해주면 된다.

 

화살표의 경우엔 커서를 의미하고 - 의 경우 문자 지우기, 그 이외의 문자의 경우 입력을 의미하는데

 

각 문자에 따라 스택을 활용해 표현하면 다음과 같이 표현이 가능하다.

 

우선 처음 입력받는 부분을 stack1이라고 편의상 표현하고 커서를 옮겼을때

커서의 오른쪽에 해당되는 이미 입력받은 문자열을 저장할 부분을 stack2라고 표현하도록 하겠다.

 

< : stack1 pop & stack2 push

> : stack2 pop & stack1 push

- : stack1 pop

나머지 : stack1 push

 

간단한 예시를 들자면 "A<M" 이란 입력이 주어진다면

 

key	A	<	M
process	stack1.push(A)	temp = stack1.pop() stack2.pop(temp)	stack1.push(M)
result	stack1 : A stack2 :	stack1 : stack2 : A	stack1 : M stack2 : A

 

 

위 표와 같은 과정을 거쳐 "MA"로 출력시키면 된다.

즉 한 문자당 많아야 두번의 연산만 거치면 모든 문자에 대한 연산을 수행한 결과를 가져올수 있다.

 

그럼 바로 코드로 풀이해 보도록 하겠다.

 

먼저 필드로 스택2개를 사용하므로 이차원 배열로 하나 그리고 스택의 top을 관리해줄 배열하나

출력할 결과값을 저장할 StringBuilder를 선언해주겠다.

 

class BOJ5397Sol {
	
	private char[][] stack;
	private int[] top;
	private StringBuilder sb;
    
}

 

 

그리고 입력부와 매 테스트 케이스마다 stack을 초기화 해 줄 메소드를 선언해 주도록 하겠다.

 

 

	private void clear() { top[0] = top[1] = 0; }
	
	private void init() throws IOException {
		stack = new char[1_000_000][2];
		top = new int[2];
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		while(n-- > 0) {

		}
		in.close();
	}

 

 

이때 각 테스트 케이스 마다 입력값을 받아 원하는 출력값을 세팅할 메소드와

초기화 메소드를 넣어 주도록 하겠다.

 

 

	
	private void init() throws IOException {
		stack = new char[1_000_000][2];
		top = new int[2];
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		while(n-- > 0) {
			clear();
			setPass(in.readLine());
		}
		in.close();
	}

 

 

아직 입력값을 받아 출력값을 세팅할 메소드인 setPass 메소드는 선언하지 않았으므로 빨간줄이

뜰것이다.

 

따라서 임의로 이름만 지정해 놓을수 있게 setPass 메소드와 출력값을 가져올 메소드인 getPass 메소드를

선언해주도록 하겠다.

 

	private void setPass(String input) {

	}
	
	String getPass() { return sb.toString(); }

 

 

이 객체를 생성하면서 입력을 받을수 있도록 생성자에서 입력부를 호출한다.

이때 StringBuilder 객체도 한번만 생성가능하도록 같이 생성해준다.

 

	BOJ5397Sol() {
		sb = new StringBuilder();
		try {
			init();
		} catch(IOException e) {
			e.printStackTrace();
		}
	}

 

 

이제 이차원 배열로 선언해두었던 스택의 push,pop,isEmpty 메소드를 선언해주도록 하겠다.

이 세개 메소드는 모두 stack1에서 연산할건지 stack2에서 연산할건지에 대한 인덱스를 인자로 받는다.

 

	private boolean isEmpty(int stackIdx) {

	}
	
	private void push(char val, int stackIdx) {

	}
	
	private char pop(int stackIdx) {

	}

 

먼저 isEmpty 메소드의 경우 top이 0을 가리키는지로 간단히 확인이 가능하다.

지정한 스택이 비어있다면 top은 0을 가리킬것이다.

 

	private boolean isEmpty(int stackIdx) {
		return top[stackIdx] == 0;
	}

 

 

push 메소드는 입력할 값을 같이 인자로 받아 지정한 스택에 저장후 top을 증가시키면 된다.

 

	private void push(char val, int stackIdx) {
		stack[top[stackIdx]++][stackIdx] = val;
	}

 

 

pop 메소드는 지정한 스택의 top을 감소시킨후 해당하는 값을 리턴해준다.

 

	private char pop(int stackIdx) {
		return stack[--top[stackIdx]][stackIdx];
	}

 

 

 

이제 입력받은 문자열중 현재 문자에 따라 분기를 나눠

위에서 언급한 명령으로 진행하는 메소드를 선언해주도록하겠다.

 

	private void order(char val) {
		switch (val) {
		case '<':

			break;
		case '>':

			break;
		case '-':
			if(!isEmpty(0)) { pop(0); }
			break;
		default:
			push(val,0);
			break;
		}
	}

 

이때 화살표에 해당하는 문자는 공통적으로 pop연산 수행 후 push 연산을 수행하므로

하나의 메소드로 묶어서 관리해주도록 하겠다.

 

	private void arrowProcess(int start, int end) {
		if(isEmpty(start)) return;
		push(pop(start),end);
	}

 

인자로 받는 값들은 스택의 인덱스가 될것이다.

'<' 문자의 경우 (0,1)로 '>'문자의 경우 (1,0)으로 인자를 받는다.

 

그럼 order 메소드도 화살표 명령어에 따른 메소드 호출을 마저 작성해준다.

 

	private void order(char val) {
		switch (val) {
		case '<':
			arrowProcess(0,1);
			break;
		case '>':
			arrowProcess(1,0);
			break;
		case '-':
			if(!isEmpty(0)) { pop(0); }
			break;
		default:
			push(val,0);
			break;
		}
	}

 

 

이제 이전에 임의로 선언해두었던 setPass 메소드를 작성해주도록 하겠다.

인자로 받은 현재 입력값을 문자 단위로 쪼개서 order 메소드를 호출해 스택에 저장 후

stack1은 순차적으로 값을 가져오고

stack2는 pop연산의 반복으로 모든 데이터를 StringBuilder 객체에 저장하면 된다.

 

 

	private void setPass(String input) {
		for(char val : input.toCharArray()) { order(val); }
		for(int i = 0; i < top[0]; i++) { sb.append(stack[i][0]); }
		while(!isEmpty(1)) { sb.append(pop(1)); }
		sb.append('\n');
	}

 

 

이제 모든 코드 작성이 마무리 되었으니 객체를 생성해 실행하면,

 

 

예제에 대해 정확한 답을 내는것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package boj5;

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

public class Boj5397 {
	
	/*
	 * 2개의 스택사용
	 * < : stack1 pop & stack2 push
	 * > : stack2 pop & stack1 push
	 * - : stack1 !is empty stack1 pop
	 */
	
	public static void main(String[] args) {
		BOJ5397Sol instance = new BOJ5397Sol();
		System.out.print(instance.getPass());
	}
}

class BOJ5397Sol {
	
	private char[][] stack;
	private int[] top;
	private StringBuilder sb;
	
	BOJ5397Sol() {
		sb = new StringBuilder();
		try {
			init();
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
	
	private void clear() { top[0] = top[1] = 0; }
	
	private void init() throws IOException {
		stack = new char[1_000_000][2];
		top = new int[2];
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		while(n-- > 0) {
			clear();
			setPass(in.readLine());
		}
		in.close();
	}
	
	private boolean isEmpty(int stackIdx) {
		return top[stackIdx] == 0;
	}
	
	private void push(char val, int stackIdx) {
		stack[top[stackIdx]++][stackIdx] = val;
	}
	
	private char pop(int stackIdx) {
		return stack[--top[stackIdx]][stackIdx];
	}
	
	private void arrowProcess(int start, int end) {
		if(isEmpty(start)) return;
		push(pop(start),end);
	}
	
	private void order(char val) {
		switch (val) {
		case '<':
			arrowProcess(0,1);
			break;
		case '>':
			arrowProcess(1,0);
			break;
		case '-':
			if(!isEmpty(0)) { pop(0); }
			break;
		default:
			push(val,0);
			break;
		}
	}
	
	private void setPass(String input) {
		for(char val : input.toCharArray()) { order(val); }
		for(int i = 0; i < top[0]; i++) { sb.append(stack[i][0]); }
		while(!isEmpty(1)) { sb.append(pop(1)); }
		sb.append('\n');
	}
	
	String getPass() { return sb.toString(); }
}