문제 풀이 시도
처음에 해당 문제의 풀때 커서를 옮기며 문자를 추가하거나 삭제하고 옮기는 작업이 많아 연결리스트를 사용할려고 했다.
그렇게 문제를 풀고나서 예제에 나오는 문제를 모두 대입한 후 정상적인 출력이 나오는 걸 본 뒤 제출을 눌렀지만...
첫번째 시도 이후 코드를 이리저리 고쳤지만 3개 모두 시간 초과로 나오고 나서 온갖 고민을 했다.
우선 먼저 하단에 있던 알고리즘 분류에 스택과 연결 리스트가 나오는걸 보고난 후 스택으로 어떻게 이 문제를 풀어나가야 하는지 고민하던 끝에 결국 힌트를 찾고자 다른 분들이 어떻게 풀었는지 참고 하여 문제를 풀었다.
문제 풀이 과정
2개의 스택을 사용하여 왼쪽 스택에는 문제에서 제시하고 있는 커서가 있는 위치의 왼쪽 값들이 저장 / 삭제 하고 오른쪽 스택에는 커서가 있는 위치의 오른쪽 값들을 저장 / 삭제하는 방식으로 문제를 풀었다.
커서는 다음과 같은 명령어를 받을때 커서가 움직이도록 되어 있다.
아래의 예시를 가지고 문제를 풀어보면 다음과 같은 단계를 가진다.
1. abcd를 입력 받은 후 'a','b','c','d'로 분리하여 Left Stack에 순서대로 저장한다.
2. 3을 입력받아 3번의 명령어를 입력받도록 반복문을 작성한다.
3. P x를 입력받아 x를 현재 커서(Left Stack과 Right Stack 사이라고 생각)의 왼쪽인 Left Stack에 추가한다.
4. L을 입력받아 현재 커서를 왼쪽으로 이동을 해야하므로 현재 커서의 바로 앞에 있는 Left Stack의 마지막 입력값인 X를 Right Stack으로 옮겨준다.
5. P y를 입력받아 y를 현재 커서(Left Stack과 Right Stack 사이라고 생각)의 왼쪽인 Left Stack에 추가한다.
6. 모든 입력이 끝났다면 커서의 왼쪽에 있는 Left Stack의 값들을 하나씩 Right Stack으로 옮긴다.
7. Right Stack에 있는 값들을 모두 하나씩 Pop(a 부터 하나씩 빠진다)하여 합치면 의도하던 abcdyx가 출력되는 것을 볼 수 있다.
해결 후 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Character> leftStack = new Stack<>();
Stack<Character> rightStack = new Stack<>();
String[] split = br.readLine().split("");
for (String word : split) {
leftStack.push(word.charAt(0));
}
int count = Integer.parseInt(br.readLine());
for (int j = 0; j < count; j++) {
String command = br.readLine();
if (command.startsWith("P")) {
leftStack.push(command.split(" ")[1].charAt(0));
} else if ("L".equals(command)) {
if (!leftStack.isEmpty()) rightStack.push(leftStack.pop());
} else if ("D".equals(command)) {
if (!rightStack.isEmpty()) leftStack.push(rightStack.pop());
} else if ("B".equals(command)) {
if (!leftStack.isEmpty()) leftStack.pop();
}
}
while (!leftStack.isEmpty())
rightStack.push(leftStack.pop());
StringBuilder stringBuilder = new StringBuilder();
while (!rightStack.isEmpty())
stringBuilder.append(rightStack.pop());
System.out.println(stringBuilder);
}
}문제 풀이에 사용된 테스트 코드
import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
import static org.junit.jupiter.api.Assertions.*;
class MainTest {
private StringBuilder sb;
private final PrintStream standardOut = System.out;
private final ByteArrayOutputStream outputStreamCaptor = new ByteArrayOutputStream();
@BeforeEach
public void setUp() {
System.setOut(new PrintStream(outputStreamCaptor));
}
@AfterEach
public void tearDown() {
System.setOut(standardOut);
}
@DisplayName("Test Case 1 - abcdyx")
@Test
public void test() throws Exception {
sb = new StringBuilder();
sb.append("abcd").append("\n");
sb.append("3").append("\n");
sb.append("P x").append("\n");
sb.append("L").append("\n");
sb.append("P y");
// Given
ByteArrayInputStream in = new ByteArrayInputStream(sb.toString().getBytes());
System.setIn(in);
// When
Main.main(new String[]{});
// Then
assertEquals("abcdyx", outputStreamCaptor.toString().trim());
}
@DisplayName("Test Case 2 - yxabc")
@Test
public void test2() throws Exception {
sb = new StringBuilder();
sb.append("abc").append("\n");
sb.append("9").append("\n");
sb.append("L").append("\n");
sb.append("L").append("\n");
sb.append("L").append("\n");
sb.append("L").append("\n");
sb.append("L").append("\n");
sb.append("P x").append("\n");
sb.append("L").append("\n");
sb.append("B").append("\n");
sb.append("P y").append("\n");
// Given
ByteArrayInputStream in = new ByteArrayInputStream(sb.toString().getBytes());
System.setIn(in);
// When
Main.main(new String[]{});
// Then
assertEquals("yxabc", outputStreamCaptor.toString().trim());
}
@DisplayName("Test Case 3 - yxz")
@Test
public void test3() throws Exception {
sb = new StringBuilder();
sb.append("dmih").append("\n");
sb.append("11").append("\n");
sb.append("B").append("\n");
sb.append("B").append("\n");
sb.append("P x").append("\n");
sb.append("L").append("\n");
sb.append("B").append("\n");
sb.append("B").append("\n");
sb.append("B").append("\n");
sb.append("P y").append("\n");
sb.append("D").append("\n");
sb.append("D").append("\n");
sb.append("P z").append("\n");
// Given
ByteArrayInputStream in = new ByteArrayInputStream(sb.toString().getBytes());
System.setIn(in);
// When
Main.main(new String[]{});
// Then
assertEquals("yxz", outputStreamCaptor.toString().trim());
}
}
느낀점
Stack 을 이용하여 이렇게 풀이 할 수 있다는 것을 처음알았다.
앞으로 이러한 문제들이 나올때 해당 문제처럼 Stack을 활용할 수 있도록 많은 노력이 필요해 보인다.
또한 각 Collection마다의 시간복잡도, 장단점을 파악하여 활용해야겠다.