[BOJ 길라잡이/Java] 11일차 #5430 AC

2025. 3. 23. 19:36· Languages/Java
목차
  1. 알고리즘 분류
  2. StringBuilder 사용 (실패 코드)
  3. Deque 사용 (성공 코드)

알고리즘 분류

- 구현

- 자료 구조

- 문자열

- 파싱

- 덱

 

새로운 언어 AC에는 두 가지 함수 R(뒤집기)와 D(버리기)가 있다.

R: 배열에 있는 수를 뒤집는다.

D: 첫 번째 수를 버린다. 배열이 비어있는데 D를 사용한 경우 에러가 발생한다.

 

각 테스트 케이스에 대해서 입력으로 주어진 정수 배열에

함수를 수행한 결과를 출력한다.

에러가 발생한 경우에는 error를 출력한다.

 

생각했던 방법은 다음과 같았다.

- 입력된 배열을 앞뒤 '[', ']'를 빼고 stringbuilder에 저장한다.

- 함수 p를 하나씩 돌면서 R이면 stringbuilder.reverse()를 하고,

D이면 ','를 기준으로 split하고 제일 앞에 있는 숫자를 ,와 함께 삭제한다.

이때 stringbuilder의 length가 0이라면 error를 출력한다.

- error가 아니라면 []를 포함해서 결과 배열을 출력한다.

StringBuilder 사용 (실패 코드)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) { // testcase 만큼 반복
            String p = br.readLine(); // 수행할 함수
            int n = Integer.parseInt(br.readLine()); // 배열 수 개수
            StringBuilder arrSb = new StringBuilder();
            boolean isError = false;
            
            String arr = br.readLine();
            for (String c : arr.split("")) {
                arrSb.append(c);
            }

            arrSb.deleteCharAt(0);
            arrSb.deleteCharAt(arrSb.length() - 1);

            for (char func : p.toCharArray()) {
                if (func == 'R') {
                    arrSb.reverse();
                } else if (func == 'D') {
                    String[] arrD = arrSb.toString().split(",");
                    if (arrSb.length() == 0) {
                        sb.append("error\n");
                        isError = true;
                        break;
                    } else {
                        int len = arrD[0].length();
                        arrSb.delete(0, len + 1);
                    }
                }
            }

            if (isError == false) {
                sb.append("[");
                for (int j = 0; j < arrSb.length(); j++) {
                    sb.append(arrSb.charAt(j));
                }
                sb.append("]\n");
            }
        }

        System.out.println(sb);
    }
}

 

그러나 이 방법은 stringbuilder를 사용해 charAt으로 마지막 출력을 하다 보니,

십의 자리 이상인 수를 출력하기가 어려웠고,

O(T * m * n) 즉 테스트케이스 수 * 명령어 길이 * 배열 길이

만큼의 시간이 걸려 시간 초과에 걸렸다.

 

따라서 다른 방법이 필요했고,

Deque를 사용했다.

 

풀이는 다음과 같다.

- String 배열에 앞뒤 []를 빼고 ,를 기준으로 나눈 숫자들을 저장한다.

- Deque에 순서대로 옮긴다.

- 함수 p를 하나씩 돌면서 R이면 booelan isReversed를 반대로 바꾼다.

D이면 1) isReversed가 true라면 뒤에서 poll(), 2) isReversed가 false라면 앞에서 poll()

이때 deque size가 0이라면 에러를 출력한다.

- 에러가 나지 않았다면, deque가 빌 때까지 1) isReversed가 true면 뒤에서 부터 poll(), 2) false면 앞에서부터 poll()

하고 출력한다.

 

Deque 사용 (성공 코드)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) { // testcase 만큼 반복
            String p = br.readLine(); // 수행할 함수
            int n = Integer.parseInt(br.readLine()); // 배열 수 개수
            String input = br.readLine();
            String[] arr = input.substring(1, input.length() - 1).split(",");

            Deque<Integer> dq = new LinkedList<>();
            for (int j = 0; j < n; j++) {
                dq.add(Integer.parseInt(arr[j]));
            }
            
            boolean isError = false;
            boolean isReversed = false;

            for (char func : p.toCharArray()) {
                if (func == 'R') {
                    isReversed = !isReversed;
                } else if (func == 'D') {
                    if (dq.isEmpty()) {
                        sb.append("error\n");
                        isError = true;
                        break;
                    }
                    if (isReversed) dq.pollLast();
                    else dq.poll();
                }
            }

            if (!isError) {
                sb.append("[");
                while(!dq.isEmpty()) {
                    sb.append(isReversed ? dq.pollLast() : dq.poll());
                    if (!dq.isEmpty()) sb.append(",");
                }
                sb.append("]\n");
            }
        }

        System.out.println(sb);
    }
}

 

매번 reverse로 뒤집을 필요 없이

현재 배열이 뒤집힌 상태인지 아닌지를 파악해서

뒤에서부터 poll하느냐, 앞에서부터 poll하느냐를 따지는게

이 문제의 킥이었다.

 

이건 O(T * (n+m))의 시간 복잡도를 가지게 된다.

 

Deque는 생각지도 못했고,

reverse를 안쓰고 flag를 쓰는 것도 생각 못했는데

많이 풀다보면 점차 시야가 넓어질 거라고 믿는다.

 

화이팅!

'Languages > Java' 카테고리의 다른 글

[프로그래머스 고득점 Kit/Java] 폰켓몬  (0) 2025.03.23
[프로그래머스 고득점 Kit/Java] 완주하지 못한 선수  (0) 2025.03.23
[BOJ 길라잡이/Java] 10일차 #1158 요세푸스 문제  (0) 2025.03.23
[BOJ 길라잡이/Java] 11일차 #1966 프린터 큐  (0) 2025.03.23
[BOJ 길라잡이/Java] 9일차 #1874 스택 수열  (0) 2025.03.21
  1. 알고리즘 분류
  2. StringBuilder 사용 (실패 코드)
  3. Deque 사용 (성공 코드)
'Languages/Java' 카테고리의 다른 글
  • [프로그래머스 고득점 Kit/Java] 폰켓몬
  • [프로그래머스 고득점 Kit/Java] 완주하지 못한 선수
  • [BOJ 길라잡이/Java] 10일차 #1158 요세푸스 문제
  • [BOJ 길라잡이/Java] 11일차 #1966 프린터 큐
효딩
효딩
개ㄱ발은 기세다. 줄여서 객기.
효딩
hyoding
효딩
전체
오늘
어제
  • 분류 전체보기 (245)
    • SKKU SW (30)
      • Computer Architecture (14)
      • Database (4)
      • Computer Network (3)
      • Operating System (7)
      • Mobile App Programming (2)
    • SuperCoding (68)
    • CS (8)
    • Web Programming (19)
    • Cloud (13)
    • Languages (45)
      • Python (8)
      • Java (37)
    • Supporters (8)
      • MoteMote (6)
      • NHN Cloud (2)
    • Certification (27)
      • Network Advisor (14)
      • ADsP (10)
      • Engineer Information Proces.. (3)
    • Finance (9)
      • 경제금융용어 (3)
    • Woori FISA (14)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 봐
  • 서버배포
  • 서버생성
  • 네트워크관리사 커트라인
  • 서버개발
  • 인프라
  • 네트워크관리사2급 공부방법
  • 네트워크관리사 준비물
  • 클라우드서비스개발
  • 글로벌소프트웨어캠퍼스
  • 우리에프아이에스
  • 네트워크관리사2급 필기
  • 코틀린문법
  • 클라우드
  • apppaas
  • 우리fis아카데미
  • nhn cloud
  • 네트워크관리사 합격
  • K-디지털트레이닝
  • Kotlin
  • 네트워크관리사 후기
  • 앱개발
  • rds local 접속
  • AWS
  • 네트워크관리사2급
  • 클라우드 서비스
  • 코틀린
  • 우리FISA
  • 인프라개발
  • 네트워크관리사

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
효딩
[BOJ 길라잡이/Java] 11일차 #5430 AC
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.