[코딩테스트] [4949] 균형잡힌 세상 & [2812] 크게 만들기

균형잡힌 세상

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

160431

54943

42320

32.936%

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

문제풀이

이 문제는 2종류의 괄호가 섞인 문자열이 주어졌을 때, 문자열 안의 괄호가 올바른지 판단하는 문자이다.

여러 문자열들이 들어오지면 괄호외의 문자는 불필요하다.

즉, 괄호 종류가 2개인 올바른 괄호 문자열을 찾는 문제이다.

0. 입력받기

이 문제는 마지막에 온점이 들어올때까지 입력을 받는 문제이다.

Scanner의 hashNext메서드를 사용하여 입력을 받으면 된다.

'.' 이 입력받았을때 종료하면 된다.

1. 괄호가 잘 닫혔는지 판단하기

opend 배열을 만들어서 (이나 [일때 opend에 추가해준다.

만약 )이나 ]이 와서 닫힌다면 잘 닫히는지 판단하여 isVaild를 업데이트 해주자.

            char[] opend = new char[line.length];
            int topIndex = -1;
            boolean isVaild = true;

            for (char ch : line) {
                if ( ch == '('  || ch == '[' ) {
                    opend[++topIndex] = ch ;
                } else if ( ch == ')' || ch == ']' ) {
                    if (topIndex < 0 || !isMatch(opend[topIndex], ch)) {
                        isVaild = false;
                        break;
                    }
                    topIndex--;
                }
            }

    static boolean isMatch(char open, char close) {
        if (open == '(' && close == ')')
            return  true;
        if (open == '[' && close == ']')
            return true;
        return false;
    }

크게 만들기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

37214

10874

7903

28.494%

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다

문제풀이

이 문제는 K개의 자리수들을 지워야 하는데 지워야할 수 중 가장 큰 수는 남겨두고 작은 수를 지우면 되는 문제이다.

입력받기

일단 숫자의 개수, 지울 숫자의 개수, N자리 숫자를 입력 받자.

        int N = sc.nextInt(); // 숫자의 개수
        int K = sc.nextInt(); // 지울 숫자의 개수
        String number = sc.next(); // N자리 숫자

지울 숫자 로직 작성

언제 어떤 숫자를 지워야할지 로직을 작성하여 제거하자.

스택 자료구조를 이용해서 지워야할 숫자가 있다면 스택에서 제거를 하고 지워야할 숫자가 없다면 스택에 추가해주자.

        for (int i = 0; i < N; i++) {
            char current = number.charAt(i);

            // 스택이 비어있지 않고, 현재 숫자가 스택의 top보다 크고, 제거할 숫자가 남아있다면
            while (!stack.isEmpty() && K > 0 && stack.peek() < current) {
                stack.pop(); // 스택의 top을 제거
                toRemove--; // 제거할 숫자 개수 감소
            }

            stack.push(current); // 현재 숫자를 스택에 추가
        }

출력

스택에 있는 결과들을 출력해주면 된다.

이 때 조심해야할 것이 내림차순으로 정렬된 숫자 경우 지워야할 부분이 없을 수도 있으니 N - K개를 출력해주자.

        for (int i = 0; i < N - K; i++) {
            System.out.print(stack.get(i)); // 결과 출력
        }