글 읽기 - 틀린 부분은 없는 것처럼 보이는데 시간초과를 해결할 수 있는 방법이 있을까요?

sth4881 2년 전 0

게시판에 있는 반례들은 전부 통과합니다.

다만 제가 복잡도를 고려하는 부분이 미숙해서 시간초과가 계속 나네요.

고수분들은 어떻게 푸셨는지 여쭤보고싶습니다.

import java.io.*;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int n = Integer.parseInt(br.readLine());

            ArrayList<Integer> list = new ArrayList<>();
            ArrayList<Integer> answer = new ArrayList<>();
            ArrayList<Character> result = new ArrayList<>();
            for(int i=0; i<n; i++)
                list.add(Integer.parseInt(br.readLine()));

            Stack<Integer> s = new Stack<>();
            int target = 0;
            // 1부터 n까지의 숫자에 대해서
            for(int i=1; i<=n; i++) {
                // 각각의 숫자를 스택에 푸시하고 result에 '+' 추가
                result.add('+');
                s.push(i);
                // 스택에 쌓인 값들에 대해서
                while(!s.isEmpty()) {
                    // 스택에서 맨 위의 값이 현재 처리해야하는 값인 경우
                    if(s.peek().equals(list.get(target))) {
                        // 맨 위의 값을 제거하고 result에 '-' 추가
                        result.add('-');
                        s.pop();
                        // 다음 타겟으로 변경
                        target++;
                    } else break;
                }
            }

            // 도출된 연산 집합을 통해서 스택 수열(answer)을 생성
            s.clear();
            int cnt = 1;
            for(char item : result) {
                if(item=='-') answer.add(s.pop());
                else {
                    s.push(cnt);
                    cnt++;
                }
            }

            // 예제를 통해서 입력받은 스택 수열과 answer를 비교
            if(!answer.containsAll(list)) bw.write("NO\n");
            else {
                for(char item : result)
                    bw.write(item + "\n");
            }

            bw.close();
        } catch(IOException e) {
            e.getStackTrace();
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 부분은 없는 것처럼 보이는데 시간초과를 해결할 수 있는 방법이 있을까요?

sth4881 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말