백준 5430번 AC - 자세한 풀이(Java)

🧩 문제 정보

• 문제: https://www.acmicpc.net/problem/5430
• 난이도: 골드 5
• 유형: 구현, 자료구조

NewCodes의 풀이

• 스스로 풀었는가: O
• 다시 풀어볼 문제인가: O
• 풀이 시간: 60분 + a
• 제출 횟수: 6회
• 선택 언어: Java
• 풀이 환경: IntelliJ IDEA CE (코드 자동완성 기능 X)

---

📝 풀이 정보

요구사항 정리

• R - 뒤집기
• D - 첫 번째 수 버리기 (배열 비어있다면 에러)

풀이 설계

 : 문제의 요구사항, 흐름이 크게 복잡하지 않아서 풀이 전에 별도로 설계하진 않았습니다. (안 한 걸 후회합니다... 뒤에서 그 이유가 나옵니다.)

통과한 코드 (실전 풀이)

 : 실전 풀이를 보고 싶으신 분은 해당 코드를 참고해 주세요! 그다음은 리팩토링한 코드를 첨부했으니 좀 더 정돈된 코드를 보고 싶으신 분은 넘겨주세요! 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 입력 받기
        int t = Integer.parseInt(br.readLine()); // 테스트의 개수
        for (int i = 0; i < t; i++) {
            String p = br.readLine(); // 함수
            int n = Integer.parseInt(br.readLine()); // 배열 원소 개수
            String temp = br.readLine();
            String[] arr = temp.substring(1, temp.length() - 1).split(",");

            Deque<Integer> q = new ArrayDeque<>();
            if (!arr[0].isEmpty()) {
                for (int j = 0; j < arr.length; j++) {
                    q.offer(Integer.parseInt(arr[j]));
                }
            }

            sb.append(AC(p, q)).append("\n");
        }

        System.out.println(sb.toString());
    }

    public static String AC(String p, Deque<Integer> q) {
        boolean isReversed = false;

        for (char operand : p.toCharArray()) {
            if (operand == 'R') {
                if (isReversed) {
                    isReversed = false;
                } else {
                    isReversed = true;
                }
            } else if (operand == 'D') {
                if (q.isEmpty()) {
                    return "error";
                }

                if (isReversed) {
                    q.pollLast();
                } else {
                    q.pollFirst();
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            if (isReversed) {
                sb.append(q.pollLast());
            } else {
                sb.append(q.pollFirst());
            }
            sb.append(",");
        }
        if (sb.length() > 1) { // 이거 감싸줘야 해!!
            sb.deleteCharAt(sb.length() - 1);
        }

        return "[" + sb.toString() + "]";
    }
}

/*
R - 뒤집기
D - 첫 번째 수 버리기 (배열 비어있다면 에러)

검색
문자열 자르기, 배열 뒤집기, sb 마지막 문자 삭제, sb 뒤집기

큐를 활용해도 됐었겠네..

1. 시간 초과..
n * p -> 1억 초

아 배열을 바꾸는 게 아니라
포인터를 따로 두면 됨. 삭제 포인터 !
그리고 마지막에 포인터가 뒤에 가 있으면 그때 뒤집어 주면 됨.

2. 스트링 인덱스 에러..
-> R []일 때 감싸주지 않아서

3. 틀렸습니다?
-> 엣지케이스가 있나보다. 내 방식에 대한 문제점?
-> 52분째 안 풀리니.. 블로그 검색해봄
블로그 봐도 안 보이네. 실수가..
*/

 

풀이 시행착오

1. 시간 초과

 : 1초의 제한 시간을 지키지 못해 '시간 초과'가 떴습니다. 풀이 설계를 안 하고 들어가서 시간 복잡도를 고려하지 못했습니다. 이는 제 실수였습니다. 아무리 쉬워 보이고 눈에 잘 들어오는 문제라도 풀이 설계는 성실히 했어야 했는데 말이죠. 

 

시간제한에 걸린 원인은 '뒤집는 함수(R)'에 있었습니다. 뒤집는 함수가 나올 때마다 배열을 뒤집는 건 비효율적이었습니다. 테스트 개수가 최대 100개이고, 수행할 함수가 최대 100000개이며, 배열의 최대 길이가 100000입니다. 그렇기에 1초라는 시간제한에 걸릴 수밖에 없었습니다.

 

배열을 직접 여러 번 뒤집지 않고도 실행 결과를 얻을 수 있는 방법을 알아냈고, 이에 따라 시간 복잡도를 줄였습니다. 이와 관련해 자세한 건 '풀의 의도 설명'에서 다루겠습니다. 

 

 

2. 런타임 에러

 : 원인은 배열이 []과 같은 빈 배열로 입력되는 케이스였습니다. 마지막에 배열을 출력할 때, StringBuilder에 각 원소마다 ', '을 append했습니다. 그리고 마지막 원소에는 ', '을 빼기 위해 deleteCharAt(sb.length() - 1) 메서드를 사용했습니다.

 

하지만 이는 빈 배열로 입력되었을 때 에러가 생깁니다. 빈 배열이면 sb에 들어있는 게 없기에 deleteCharAt(-1)이 되어버립니다. 그래서 StringIndexOutOfBounds 에러가 생겼던 것입니다. 

 

이러한 에러는 deleteCharAt메서드를 if (sb.length() > 1) 절로 감싸서 해결해주었습니다.

 

3. 틀렸습니다

 : 여기서 다소 시간을 잡아먹었습니다. 16%까지 갔는데 갑자기 '틀렸습니다'가 나오길래 엣지케이스가 있을 거라고 생각했습니다. 그래서 제 코드를 여러 번 읽어봤는데 도저히 틀린 점을 못 찾아냈습니다. 그래서 해당 문제 풀이는 잠시 멈추고 다른 문제를 먼저 풀다가 이틀 뒤에 다시 코드를 살펴봤습니다. 

 

원인은 sb.reverse() 메서드에 있었습니다. 저는 마지막에 배열을 뒤집는 연산을 진행할 때, reverse() 메서드를 이용했습니다. 이게 얼핏 보면 '배열 뒤집는 연산에서 reverse() 써도 되는 거 아니야?'라고 생각할 수도 있지만, 이건 위험한 행동입니다.

 

배열에서 각 원소가 한 자릿 수일 때는 가능합니다. 하지만, 두 자릿수부터는 reverse() 메서드로 풀면 안 됩니다. 예를 들어 "12,64"를 뒤집으면 "46,21"이 되기에 각 원소를 보면 전혀 다른 숫자가 되어버립니다. 이걸 간과하고 reverse를 사용해버렸네요 ㅠㅠ

 

해결은 deque.pollLast()를 통해 해결했습니다. 꼭 극단적인 값만이 예외 케이스가 아니라 자릿수 또한 변수가 될 수 있다고 느꼈습니다. 역시 처음에 풀이 설계를 꼼꼼히 안 하니 이런 디테일이 떨어지지 않았나 싶네요.

 

풀이 의도 설명

 : 해당 풀이에서 포인트는 크게 두 가지입니다. 

 

첫 번째는 자료구조 Deque입니다. 해당 자료구조를 통해서 함수의 연산 대상인 배열을 담았습니다. 이는 배열을 뒤집는 연산을 할 때 유리하다는 특징이 있습니다. pollLast()를 통해 모든 원소를 새 배열에 옮겨 담는다면 뒤집어진 배열을 얻을 수 있습니다. 

 

두 번째는 isReserved를 통해 뒤집기 연산을 간단화한 것입니다. 시간 복잡도를 줄이기 위해서 배열을 뒤집는 함수(R)가 나왔을 때, 정말 뒤집는 게 아니라 포인터만 바꾸도록 하는 방식으로 변경했습니다.

 

포인터가 앞에 있을 때, 즉 isReversed가 false일 때는 삭제 함수(D)를 실행시키면 배열에서 제일 앞에 있는 요소가 삭제됩니다. 반면에 포인터가 뒤에 있을 때, 즉 isReversed가 true일 때는 삭제 함수(D)를 실행시키면 배열에서 제일 뒤에 있는 요소가 삭제됩니다.

 

마지막으로 함수 실행이 모두 끝났을 때 포인터가 뒤에 있으면 Deque에서 pollLast() 메서드를 통해 뒤집도록 했습니다. 이를 통해 뒤집기 연산을 최소화할 수 있고, 시간 효율을 크게 가져올 수 있습니다. 

 

 

리팩토링한 코드 (정돈된 풀이)

 : 좀 더 보기 편하도록 문제 풀이 이후 리팩토링했습니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 받기
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine()); // 테스트의 개수
        for (int i = 0; i < t; i++) {
            String p = br.readLine(); // 함수
            int n = Integer.parseInt(br.readLine()); // 배열 원소 개수
            String temp = br.readLine();
            String[] arr = temp.substring(1, temp.length() - 1).split(",");

            Deque<Integer> deque = new ArrayDeque<>();
            if (n != 0) {
                for (int j = 0; j < arr.length; j++) {
                    deque.offer(Integer.parseInt(arr[j]));
                }
            }

            sb.append(AC(p, deque)).append("\n");
        }

        System.out.println(sb);
    }

    public static String AC(String p, Deque<Integer> deque) {
        boolean isReversed = false;

        for (char operand : p.toCharArray()) {
            if (operand == 'R') {
                isReversed = !isReversed;
            } else if (operand == 'D') {
                if (deque.isEmpty()) {
                    return "error";
                }

                if (isReversed) {
                    deque.pollLast();
                } else {
                    deque.pollFirst();
                }
            }
        }

        // String 변환
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (!deque.isEmpty()) {
            if (isReversed) {
                sb.append(deque.pollLast());
            } else {
                sb.append(deque.pollFirst());
            }
            sb.append(",");
        }

        if (sb.length() > 1) {
            sb.deleteCharAt(sb.length() - 1);
        }
        sb.append("]");

        return sb.toString();
    }
}

---

🎯 풀이 피드백

1. 검색한 것 정리

• 문자열 자르기: s.substring(int startIndex, int endIndex)
  • startIndex(포함), endIndex(미포함)
• StringBuilder 마지막 문자 삭제: sb.deleteCharAt(sb.length() - 1)
• sb 뒤집기: sb.reverse()
  
  

2. 풀이 설계할 때 고려할 것

• 문제 쉽고 흐름 보이더라도 풀이 설계 꼭 하자.
• 시간 초과 신경 쓰자. 시간 복잡도 계산!!
• 예외적인 케이스 고려하자. (테케에 의존하지 말자. 테케 수가 많더라도.)
• 가급적이면 종이에 써서 생각하자.
• 알고리즘뿐만 아니라 자료구조도 신경 써서 선택하자.