https://www.acmicpc.net/problem/1406
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
코드설명
연결리스트, 링크드리스트를 사용하여 해결할 수 있습니다.
문제가 문제에서 요구하는대로 구현하면 되는 문제이지만, 놓칠 수 있는 부분이 많습니다.
놓칠 수 있는 부분들을 설명해보면,
1. 'L' 명령어는 왼쪽으로 이동하는 것만 신경씁니다. 만약 'L' 명령어시 커서가 맨 왼쪽에 있는 상황이라면 왼쪽으로 이동하지 못하므로 작업을 처리하지 않습니다.
2. 'R' 명령어도 'L' 명령어와 같습니다.
연결리스트 시간복잡도
연결리스트는 크기를 정할필요 없이, 동적으로 사이즈가 정해지기에 배열처럼 연속된 메모리 주소를 할당받지 않습니다.
데이터의 삽입, 삭제는 O(1) 의 시간복잡도입니다.
하지만, 탐색은 O(N)의 시간복잡도를 가집니다.
배열을 사용하여 진행했다면,
데이터의 삽입, 삭제는 O(N)의 시간복잡도입니다.
탐색은 O(1)의 시간복잡도를 가집니다.
코드
정답코드
- 'P'일때 current.left == null일떄 current.right.left = newNode를 추가해준 코드 ( 맨 앞에 새롭게 추가하는 경우 오른쪽 Node를 새로운 Node에 연결시켜주어야합니다. )
- 커서의 이동을 'L'과 'D'로 이동시킬때,
- 'L' : 왼쪽으로 이동할시 왼쪽에 아무것도 없으면 이동시키면 안됩니다. ( 오른쪽이 null이든, 다른 경우든 전혀 상관없으므로 해당 로직을 처리합니다. 즉, 만약 왼쪽이 NULL이면 아무것도 안하고 넘어갑니다. )
- 'R' : 오른쪽으로 이동할시 오른쪽에 아무것도 없으면 이동시키면 안됩니다. ( 왼쪽이 null이든, 다른 경우든 전혀 상관없으므로 해당 로직을 처리합니다. 즉, 만약 오른쪽이 NULL이면 아무것도 안하고 넘어갑니다. )
- StringBuilder로 처리해야 시간초과가 나지 않습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M;
public static String word;
public static Node current = null;
public static Node root = new Node(' ',null,null);
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
word = st.nextToken();
current = root;
for(int i=0;i<word.length();i++) {
current.right = new Node(word.charAt(i), current, null);
current = current.right;
}
Node temp = root.right;
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
char operation = st.nextToken().charAt(0);
if(operation =='L') {
//현재 커서가 맨 왼쪽에 잇을시. 왼쪽으로 가는것이므로 오른쪽은 신경안씁니다.
if(current.left == null) {
continue;
}
//현재 커서가 맨 오른쪽에 있을시
else if(current.right == null) {
current = current.left;
}
else {
current = current.left;
}
}
else if(operation == 'D') {
//현재 커서가 맨 오른쪽에 있을시, 오른쪽으로 가는것이므로 오른쪽만 신경씁니다.
if(current.right == null) {
continue;
}
//현재 커서가 맨 왼쪽에 있을시
else if(current.left == null) {
current = current.right;
}
//일반적인 상황
else {
current = current.right;
}
}
else if(operation == 'P') {
char newWord = st.nextToken().charAt(0);
Node newNode = new Node(newWord, null, null);
//만약 커서가 맨 왼쪽에 있을때 추가한다면,
if(current.left == null) {
newNode.left = current;
newNode.right = current.right;
current.right.left = newNode; //맨 앞에 새롭게 추가하는 경우 오른쪽 Node를 새로운 Node에 연결시켜주어야합니다.
current.right = newNode;
current = newNode;
}
//만약 커서가 맨 오른쪽에 있을떄 추가한다면,
else if(current.right == null) {
newNode.left = current;
newNode.right = current.right;
current.right = newNode;
current = newNode;
}
//만약 커서가 중간에 있을떄 추가한다면,
else {
newNode.left = current;
newNode.right = current.right;
current.right.left = newNode;
current.right = newNode;
current = newNode;
}
}
else if(operation =='B'){
//현재 위치의 left가 null이면, 시작점입니다.
if(current.left == null) {
continue;
}
//현재 위치의 right가 null이면, 끝점입니다.
else if(current.right == null) {
current = current.left;
current.right = null;
}
else {
current.left.right = current.right;
current.right.left = current.left;
current = current.left;
}
}
}
StringBuilder sb = new StringBuilder();
temp = root.right;
while(temp !=null) {
// System.out.print(temp.value);
sb.append(temp.value);
temp = temp.right;
}
System.out.println(sb);
}
}
class Node{
char value;
Node left;
Node right;
public Node(char value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
- 'L' 혹은 'D'를 실행할떄 해당 방향이 null인지가 가장 중요하므로 각 방향만 체크합니다. 이동방향의 반대도 체크할시 단어가 1개일때 반대방향도 null입니다.
- StringBuilder를 사용하지 않아 시간초과가 납니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M;
public static String word;
public static Node current = null;
public static Node root = new Node(' ',null,null);
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
word = st.nextToken();
current = root;
for(int i=0;i<word.length();i++) {
current.right = new Node(word.charAt(i), current, null);
current = current.right;
}
Node temp = root.right;
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
char operation = st.nextToken().charAt(0);
if(operation =='L') {
// System.out.println("BEFORE LEFT MOVE:"+current.value);
//현재 커서가 맨 왼쪽에 잇을시. 왼쪽으로 가는것이므로 오른쪽은 신경안씁니다.
if(current.left == null) {
continue;
}
else {
current = current.left;
}
}
else if(operation == 'D') {
//현재 커서가 맨 오른쪽에 있을시, 오른쪽으로 가는것이므로 오른쪽만 신경씁니다.
if(current.right == null) {
continue;
}
//일반적인 상황
else {
current = current.right;
}
}
else if(operation == 'P') {
char newWord = st.nextToken().charAt(0);
Node newNode = new Node(newWord, null, null);
//만약 커서가 맨 왼쪽에 있을때 추가한다면,
if(current.left == null) {
newNode.left = current;
newNode.right = current.right;
current.right.left = newNode;
current.right = newNode;
current = newNode;
}
//만약 커서가 맨 오른쪽에 있을떄 추가한다면,
else if(current.right == null) {
newNode.left = current;
newNode.right = current.right;
current.right = newNode;
current = newNode;
}
//만약 커서가 중간에 있을떄 추가한다면,
else {
newNode.left = current;
newNode.right = current.right;
current.right.left = newNode;
current.right = newNode;
current = newNode;
}
}
else if(operation =='B'){
//현재 위치의 left가 null이면, 시작점입니다.
if(current.left == null) {
// System.out.println("why working?");
continue;
}
//현재 위치의 right가 null이면, 끝점입니다.
else if(current.right == null) {
current = current.left;
current.right = null;
}
else {
current.left.right = current.right;
current.right.left = current.left;
current = current.left;
}
}
}
temp = root.right;
while(temp !=null) {
System.out.print(temp.value);
temp = temp.right;
}
}
}
class Node{
char value;
Node left;
Node right;
public Node(char value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
- 오답코드
- 2% 에서 틀리는 코드. 이유는 L 혹은 D를 실행할때 한가지의 단어만 있으면 시작이자 끝이기에 에러가 납니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M;
public static String word;
public static Node current = null;
public static Node root = new Node(' ',null,null);
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
word = st.nextToken();
current = root;
for(int i=0;i<word.length();i++) {
current.right = new Node(word.charAt(i), current, null);
current = current.right;
}
Node temp = root.right;
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
char operation = st.nextToken().charAt(0);
if(operation =='L') {
// System.out.println("BEFORE LEFT MOVE:"+current.value);
//현재 커서가 맨 왼쪽에 잇을시. 왼쪽으로 가는것이므로 오른쪽은 신경안씁니다.
if(current.left == null) {
continue;
}
//현재 커서가 맨 오른쪽에 있을시
else if(current.right == null) {
current = current.left;
}
//현재 커서가 중간에 존재할시 (맨앞, 맨뒤 아닐시)
else {
current = current.left;
}
}
else if(operation == 'D') {
//현재 커서가 맨 오른쪽에 있을시, 오른쪽으로 가는것이므로 오른쪽만 신경씁니다.
if(current.right == null) {
continue;
}
//현재 커서가 맨 오른쪽에 있을시
else if(current.left == null) {
continue;
}
//일반적인 상황
else {
current = current.right;
}
}
else if(operation == 'P') {
char newWord = st.nextToken().charAt(0);
Node newNode = new Node(newWord, null, null);
//만약 커서가 맨 왼쪽에 있을때 추가한다면,
if(current.left == null) {
newNode.left = current;
newNode.right = current.right;
current.right.left = newNode;
current.right = newNode;
current = newNode;
}
//만약 커서가 맨 오른쪽에 있을떄 추가한다면,
else if(current.right == null) {
newNode.left = current;
newNode.right = current.right;
current.right = newNode;
current = newNode;
}
//만약 커서가 중간에 있을떄 추가한다면,
else {
newNode.left = current;
newNode.right = current.right;
current.right.left = newNode;
current.right = newNode;
current = newNode;
}
}
else if(operation =='B'){
//현재 위치의 left가 null이면, 시작점입니다.
if(current.left == null) {
// System.out.println("why working?");
continue;
}
//현재 위치의 right가 null이면, 끝점입니다.
else if(current.right == null) {
current = current.left;
current.right = null;
}
else {
current.left.right = current.right;
current.right.left = current.left;
current = current.left;
}
}
}
temp = root.right;
while(temp !=null) {
System.out.print(temp.value);
temp = temp.right;
}
}
}
class Node{
char value;
Node left;
Node right;
public Node(char value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
https://www.acmicpc.net/board/view/15983
글 읽기 - 자바 - 1406번 에디터 문제ㅠㅠ 제 코드에 무슨 문제가 있을까요..?
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 2304 창고 다각형 - 구현 + 그리디 JAVA (0) | 2023.08.08 |
|---|---|
| [백준] 5397 키로거 - 연결리스트 + 링크드리스트 JAVA (0) | 2023.08.08 |
| [백준] 11501 주식 - 탐욕법(Greedy, 그리디) + 우선순위큐(PriorityQueue)JAVA (0) | 2023.08.07 |
| [백준] 1927 최소 힙 - 우선순위큐(PriorityQueue) JAVA (0) | 2023.08.07 |
| [백준] 19941 햄버거 분배 - 그리디(탐욕법, Greedy) JAVA (0) | 2023.08.07 |