0x04강 문제. 에디터, 키로거

JUN·2024년 5월 28일

에디터 연결 리스트 키로거

codingTest

목록 보기

8/23

📌 서론.

연결 리스트에 대해 배우고 해당 개념을 응용할 수 있는 문제를 풀어보았다.

📚 오늘의 문제.

📝 문제 1. 에디터

링크 : https://www.acmicpc.net/problem/1406

문제 설명

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때 마지막에 에디터에 있는 출력하는 문제.

문제 풀이

명령어를 담는 자료는 배열로 진행하고
에디터 객체 생성 → ArrayList 로 생성하면 좋을듯.
하지만 그럴 필요도 없다. StringBuilder 를 사용하면 되니깐

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

public class arrTest {

  public static void main(String[] args) throws IOException {
    // Input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder initStr = new StringBuilder(br.readLine());
    int m = Integer.parseInt(br.readLine()); // 입력할 정수의 개수
    String[] cmdList = new String[m];

    for (int i = 0; i < m; i++) {
      cmdList[i] = br.readLine();
    }
    br.close();

    int cursor = initStr.length();

    for (String command : cmdList) {
      char cmd = command.charAt(0);
      switch (cmd) {
        case 'L':
          if (cursor > 0) {
            cursor--;
          }
          break;
        case 'D':
          if (cursor < initStr.length()) {
            cursor++;
          }
          break;
        case 'B':
          if (cursor > 0) {
            initStr.deleteCharAt(cursor - 1);
            cursor--;
          }
          break;
        case 'P':
          char argument = command.charAt(2); // P 명령어 뒤에 오는 첫 번째 문자
          initStr.insert(cursor, argument);
          cursor++;
          break;
      }
    }

    // Output
    System.out.println(initStr.toString());
  }
}

시간초과가 떠서 확인해보니 StringBuilder 객체인 initStr가 삽입 삭제 연산시에 동적 배열처럼 O(n)의 시간이 걸려 시간을 잡아먹는 것이었다.

삽입 삭제 시 상수 시간이 걸리는 LinkedList로 initStr를 구성해줬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {

  public static void main(String[] args) throws IOException {
    // Input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String initialStr = br.readLine();
    int m = Integer.parseInt(br.readLine()); // 입력할 정수의 개수
    String[] cmdList = new String[m];

    for (int i = 0; i < m; i++) {
      cmdList[i] = br.readLine();
    }
    br.close();

    // LinkedList 사용
    LinkedList<Character> list = new LinkedList<>();
    for (char c : initialStr.toCharArray()) {
      list.add(c);
    }

    ListIterator<Character> iterator = list.listIterator(list.size());

    for (String command : cmdList) {
      char cmd = command.charAt(0);
      switch (cmd) {
        case 'L':
          if (iterator.hasPrevious()) {
            iterator.previous();
          }
          break;
        case 'D':
          if (iterator.hasNext()) {
            iterator.next();
          }
          break;
        case 'B':
          if (iterator.hasPrevious()) {
            iterator.previous();
            iterator.remove();
          }
          break;
        case 'P':
          char argument = command.charAt(2); // P 명령어 뒤에 오는 첫 번째 문자
          iterator.add(argument);
          break;
      }
    }

    // Output
    StringBuilder result = new StringBuilder();
    for (char c : list) {
      result.append(c);
    }
    System.out.println(result.toString());
  }
}

🔑 키워드.

1. `initStr.deleteCharAt(cursor - 1)`

시간 복잡도: O(N)
- StringBuilder의 deleteCharAt 메서드는 내부적으로 배열을 사용하여 문자열을 저장합니다. 배열에서 문자를 삭제하려면 해당 인덱스 이후의 모든 문자를 한 칸씩 앞으로 이동해야 하므로 시간 복잡도는 O(N)입니다. 여기서 N은 initStr의 현재 길이입니다.

2. `initStr.insert(cursor, argument)`

시간 복잡도: O(N)
- StringBuilder의 insert 메서드는 특정 위치에 문자를 삽입합니다. 이 경우, 삽입 위치 이후의 모든 문자를 한 칸씩 뒤로 이동해야 하므로 시간 복잡도는 O(N)입니다.

📝 문제 2. 키로거

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

문제 설명

각 TC 당 비밀번호를 입력한 로그가 주어진다.

해당 로그를 분석해서 비밀번호를 유추해내는 문제.

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {

  public static void main(String[] args) throws IOException {
    // TC 분리
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine()); // TC개수

    // 각 TC 당 하나씩 처리.
    for (int test_case = 1; test_case <= T; test_case++) {
      // Input
      LinkedList<Character> keyLogList = new LinkedList<>();
      String keyLog = br.readLine();
      ListIterator<Character> cursor = keyLogList.listIterator();

      for (char c : keyLog.toCharArray()) {
        switch (c) {
          case '>':
            if (cursor.hasNext()) {
              cursor.next();
            }
            break;
          case '<':
            if (cursor.hasPrevious()) {
              cursor.previous();
            }
            break;
          case '-':
            if (cursor.hasPrevious()) {
              cursor.previous();
              cursor.remove();
            }
            break;
          default:
            cursor.add(c);
            break;
        }
      }

      // Output
      StringBuilder sb = new StringBuilder();
      for (char c : keyLogList) {
        sb.append(c);
      }
      System.out.println(sb.toString());
    }
    br.close();
  }
}

🔑 키워드.

스트링을 LinkedList에 초기화하는법. ArrayList도 같은 방법으로 초기화할 수 있음.

for 루프 사용

LinkedList<Character> list = new LinkedList<>();
      String keyLog = br.readLine();
      for (char c : keyLog.toCharArray()) {
        list.add(c);
      }

Collections 의 addAll 사용

import java.util.LinkedList;
import java.util.Collections;

String keyLog = br.readLine();
LinkedList<Character> list = new LinkedList<>();
Collections.addAll(list, keyLog.chars().mapToObj(c -> (char) c).toArray(Character[]::new));

스트림사용

import java.util.LinkedList;
import java.util.stream.Collectors;

String keyLog = br.readLine();
LinkedList<Character> list = keyLog.chars()
                                   .mapToObj(c -> (char) c)
                                   .collect(Collectors.toCollection(LinkedList::new));

JUN

순간은 기록하고 반복은 단순화하자 🚀

이전 포스트

0x04 강_연결 리스트 문제 - 요세푸스 문제

다음 포스트

0x04강 문제. 에디터, 키로거

codingTest

📌 서론.

📚 오늘의 문제.

📝 문제 1. 에디터

🔑 키워드.

1. `initStr.deleteCharAt(cursor - 1)`

2. `initStr.insert(cursor, argument)`

📝 문제 2. 키로거

🔑 키워드.

0x04 강_연결 리스트 문제 - 요세푸스 문제

바킹독 0x04 강 - 연결 리스트

0개의 댓글

0x04강 문제. 에디터, 키로거

codingTest

📌 서론.

📚 오늘의 문제.

📝 문제 1. 에디터

🔑 키워드.

1. initStr.deleteCharAt(cursor - 1)

2. initStr.insert(cursor, argument)

📝 문제 2. 키로거

🔑 키워드.

0x04 강_연결 리스트 문제 - 요세푸스 문제

바킹독 0x04 강 - 연결 리스트

0개의 댓글

1. `initStr.deleteCharAt(cursor - 1)`

2. `initStr.insert(cursor, argument)`