[백준] 5397번 키로거 자바

문제

 

5397번: 키로거

 

 

문제 풀이

 

처음에 ArrayList와 idx변수 하나를 이용해서 list의 인덱스 번호를 옮겨가면서 값을 삽입하는 방법으로 진행을 했는데 시간초과가 떴다. 그래서 구글링해본 결과, Stack을 이용하는 방법과 ListIterator를 이용하는 방법 두 가지가 있었다.

두 가지 모두 풀이에 적용해 보았다.

 

먼저 ListIterator를 이용하는 방법은 기존 ArrayList에서 index를 바꿔나가는 방법과 로직을 동일하게 사용하고 사용 자료구조와 함수만 바꿨다. 아 근데 바꿨는데도 시간초과가 떠서 list값을 바로 출력하지 않고 SringBuilder를 사용했더니 시간초과가 뜨지 않았다. (ArrayList + StringBuilder는 그래도 시간초과뜸)

 

* ListIterator사용방법

  - ListIterator인터페이스는 Iterator인터페이스를 상속받아 여러 기능을 추가한 List제공 인터페이스

  - Iterator인터페이스는 한 방향으로만 이동할 수 있음

  - ListIterator인터페이스는 양방향으로 탐색하면서 추가,검색,삭제를 위한 기능 제공

LinkedList<T> list = new LinkedList<>();
ListIterator<T> itr = list.listIterator();

 

* 주요 메소드

 

메소드	설명
nextIndex()	현재 커서 기준으로 다음 index반환 (초기값 0)
previousIndex()	현재 커서 기준으로 이전 index반환 (초기값 -1)
next()	리스트의 다음 데이터 반환, 리스트 내 커서 위치를 다음 방향으로 이동
previous()	리스트의 이전 데이터 반환, 리스트 내 커서 위치를 이전 방향으로 이동
remove()	next(), previous()로 반환된 가장 최근 데이터를 리스트에서 삭제
add(e)	리스트의 nextIndex() 위치에 e추가
hasNext()	리스트에 다음 데이터가 존재하면 true
hasPrevious()	리스트에 이전 데이터가 존재하면 true
set(e)	next(), previous()로 반환된 가장 최근 데이터를 e로 대체

 

 

스택을 이용하는 방법은 두 개의 스택을 이용해서 화살표(< , >) 에 따라 두 개의 스택에 번갈아 넣어주면 된다.

만약 'BP<' 이런 문자열이 들어왔을 경우 B, P를 스택1에 잘 쌓아오다가 '<'로 인하여 BP사이에 다른 글자가 들어갈 수가 있으므로 <를 만났을 때 P를 스택2로 옮겨둔다. 이런 식으로 또 '<' 를 만나면 스택1에 있는 글자를 스택2로 옮기고 다시 '>'를 만나면 스택2에 있던 글자를 스택1으로 옮겨둔다. 그래서 기본 글자는 스택1에만 쌓으면서 화살표에 따라 옮겨주는 방법이다. 그리고 '-'를 만났을 때는 스택1의 글자를 지워주고(스택에 글자가 있을 경우만), 마지막에 끝났을 때 스택2에 남아있는 글자를 모두 옮겨주면 끝난다.

 

 

소스 코드

 

1) ListIterator이용

 

public class b_5397 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		String str;
		
		for(int i = 0; i < t; i++) {
			str = sc.next();
			solution(str);
		}
		
		sc.close();
	}
	
	public static void solution(String str) {
		LinkedList<Character> lnklist = new LinkedList<>();
		ListIterator<Character> list = lnklist.listIterator();
		
		for(int i = 0; i < str.length(); i++) {
			char ch = str.charAt(i);
				
			switch(ch) {
			case '<':
				if(list.nextIndex() > 0)
					list.previous();
				break;
				
			case '>':
				if(list.nextIndex() < lnklist.size())
					list.next();
				break;
				
			case '-':
				if(list.nextIndex() > 0) {
					list.previous();
					list.remove();
				}
				break;
				
			default:
				list.add(ch);
				break;
			}
			
			/*
			if(ch == '<') {
				if(idx > 0)
					idx--;
			}
			else if(ch == '>') {
				if(idx < list.size())
					idx++;
			}
			else if(ch == '-') {
				if(idx > 0) {
					idx--;
					list.remove(idx);
				}
			}
			else {
				list.add(idx, ch);
				idx++;
			}
			*/
		}
		
		StringBuilder sb = new StringBuilder();
		for(char c: lnklist)
			sb.append(c);
		System.out.println(sb.toString());
	}

}