반응형
이번 글에서는 4949번 문제를 통해 스택을 활용,
괄호의 균형을 맞춰완벽한 문장을 나타내 보자.


 

 

문제 핵심

  • 문자열은 ( ),  [ ] 이 두 소괄호와 대괄호가 짝을 이루어야 한다.
  • 1 : 1 매칭만 가능하다.
  • 공백 이후의 . 과 같은 괄호가 없는 문장도 균형 잡힌 문자열이다.
  • (, [ 이 나온 후에 ), ] 가 나와야 짝이 이루어 진다. 
    • ] [ 은 짝이 아닌 경우 

풀이 과정

먼저 우리가 찾아야 할 것은 괄호들이다.

이는 StringTokenizer를 활용해 볼 예정이다. ( 물론 chatAt()을 사용하면 더 빠르다. )

다음 자료구조 스택에 대한 글과 split과 StringTokenizer비교에 관한 글을 참고하면 좋을 것 같다.

 

 

스택 ( 자료구조 ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후

p-coding.tistory.com

 

 

[ JAVA ] 문자열 자르기 Splite VS StringTokenizer

문자열을 특정 구분자로 분리할 수 있는 StringTokenizer와 Splite을 사용하던 중구체적인 차이점이 무엇인지 궁금하여 조사하게 되었다.메모리에서 장점을 가진다고 하지만 정확히 어떤구조로 작용

p-coding.tistory.com

 

 

1. 괄호 문자 저장

먼저 StringTokenizer를 통해 소괄호, 대괄호를 기준으로 문자를 나눈다.

그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.

true로 설정하면 구분자도 Token에 포함된다.

stringTokenizer = new StringTokenizer(sentence,"([)]",true);

 

2. 괄호 문자 찾아 균형확인하기

1. 구분자에 포함된 토큰 중에 괄호를 찾는다.

2. (, [ 라면 스택에 넣는다

3 - 1. ], ) 라면 스택에서 꺼내 비교한다

3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리

while(stringTokenizer.hasMoreTokens()) {

    String token = stringTokenizer.nextToken();

    if (token.equals("(") || token.equals("[")) {
        push(token);
    }
    else if (token.equals(")")) {
        if (!pop().equals("(")) {
            isPerfect = false;
            break;
        }
    }
    else if (token.equals("]")) {
        if (!pop().equals("[")) {
            isPerfect = false;
            break;
        }
    }
}

 

 

3. 스택에 남아있는 값 확인

마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.

if (!delimStack.isEmpty()) isPerfect = false;

 

스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때,
다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다.
이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이
다양한 방법으로 풀어보는 것을 추천한다.



전체 코드

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

public class Main {

    private static LinkedList<String> delimStack;

    private static void push(String delim){
        delimStack.addLast(delim);
    }

    private static String pop(){
        return delimStack.isEmpty() ? " " : delimStack.removeLast();
    }


    public static void main(String[] args) throws IOException {
        delimStack = new LinkedList<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        boolean isPerfect;
        StringTokenizer stringTokenizer;

        while (true) {
            isPerfect = true;
            delimStack.clear();
            String sentence = bufferedReader.readLine();

            if(sentence.equals(".")) break;

            stringTokenizer = new StringTokenizer(sentence,"([)]",true);


            while(stringTokenizer.hasMoreTokens()) {

                String token = stringTokenizer.nextToken();

                if (token.equals("(") || token.equals("[")) {
                    push(token);
                }
                else if (token.equals(")")) {
                    if (!pop().equals("(")) {
                        isPerfect = false;
                        break;
                    }
                }
                else if (token.equals("]")) {
                    if (!pop().equals("[")) {
                        isPerfect = false;
                        break;
                    }
                }
            }

            if (!delimStack.isEmpty()) isPerfect = false;


            stringBuilder.append(isPerfect ? "yes\n" : "no\n");
        }

        System.out.println(stringBuilder);
    }
}
반응형
반응형
이번 글에서는 백준 28278번 문제를 통해
스택(자료구조)를 구현하고 활용해 보자.

문제 핵심

  • N : 명령의 수 ( 1 <= N <= 1,000,000 )
  • 명령 1 ~ 5 까지 주어진다.
  • 1. Push
  • 2. Pop
  • 3. Size
  • 4. IsEmpty
  • 5. Peek
  • 명령은 하나씩 주어진다.

풀이 과정

다음 문제는 스택을 구현하고 처리하는 과정이라고 할 수 있다.

 

1. 함수 구현하기

1 ~ 5의 명령어와 같이 스택에 필요한 함수들을 구현하자.

	private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }

 

문제에 맞게 명령어들을 변형하여 함수를 구현하였다.

2. 구현한 함수 활용하기 ( Main 작성 )

  • 문제를 다음과 같이 풀었지만, 1 ~ 5의 단순한 숫자나 문자열로 처리할 경우 Switch문이 더 적합하며 범위 계산이나 null 값 계산 등이 아니라면 Switch문으로 처리하는 것이 좋아 보인다.
  • List 는 JAVA의 LinkedList<> 클래스를 활용하였다.
    • ArrayList or List를 활용해서 사용할 수 있기도 하지만, 미리 만들어두는 구조보다는 문제제목과 같은 자료구조에 맞춰서 사용하였다.
private static final LinkedList<Integer> list = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

 

 

스택 ( 자료구조 ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후

p-coding.tistory.com

 

백준에서는 여러 프로그래밍 언어 중 Java가 비교적 느린 편이기 때문에, 많은 사람이 속도 최적화에 집중하거나 단순히 문제를 해결하는 데만 초점을 맞춰 코드를 작성하는 경우가 많다. (물론 브론즈 ~ 실버 수준의 문제에서는 속도 차이가 크게 중요하지 않다.)

하지만 이러한 문제의 핵심은 스택을 직접 구현하고 이해하는 것에 있다.


예를 들어, 명령어가 4일 때 list.isEmpty() ? 1 : 0을 사용하면 간편하게 해결할 수 있다.
그러나 이는 LinkedList 클래스의 isEmpty() 메서드를 활용한 것이지,
우리가 구현해야 할 스택의 isEmpty()가 아니다.

비록 같은 기능을 수행하지만, 개념적으로 다른 의미를 가진다.


즉,
문제를 통과하는 것에만 집중하기보다는, 정확한 개념을 이해하고 접근하는 것이 더 중요하다.


전체 코드

물론 다음 코드도 완벽하지는 않다.

package org.example;

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

public class Main {

    private static final LinkedList<Integer> list = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

    private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }
}
반응형
반응형
이번 글에서는 백준 17103번 문제를 통해 소수 찾기 알고리즘인 에라토스테네스의 체를 활용,
이를 통해 소수를 찾고 짝수를 소수의 합으로 나타내보자.

문제 핵심

  • N : 짝수
    • 2 < N <= 1,000,000
  • 두 개의 소수의 합이다.
  • 순서만 다른 것은 같은 파티션이다.

풀이 과정

다음 문제는 소수를 먼저 찾아서 합을 구하면된다.

즉, 에라토스테네스의 체를 활용 소수를 효율적으로 구할 수 있다.

 

소수 찾기 ( 에라토스테네스의 체 ) - JAVA

에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.( 고대 그리수 수학자 에라토스테네스가 발견 ) 알고리즘다음과 같은 알고리즘을 따른다.0 ~ 50 까지의 수를 찾고자 할

p-coding.tistory.com

 

1. 소수 찾기

먼저 소수를 분별한다. ( max값을 찾아서 할 수 있지만 최대값 1,000,000인 점을 감안 미리 1,000,000까지 소수를 찾는다. )

    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

 

2. 골드 바흐 파티션 구성

1. 양쪽에서 숫자를 줄여가며 소수 체크를 한다. ( 이 때 양쪽에서 검사하기 때문에 절반만 사용한다. )

2. 둘 다 소수일 때 count를 증가시킨다.

3. count를 반환한다.

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }

 

 

 


미리 찾아둔 소수를 활용하고 반복문을 효율적으로 사용하면 비교적 쉬운 문제이다.
1,000,000 이하의 소수는 미리 생성해도 처리 가능하지만,
숫자가 매우 커질 경우에는 입력값의 최대값을 기준으로 소수를 구하는 것이 더 효율적이다.

이번 문제는 두 수의 합이 N이 되어야 하므로, 다음과 같은 방식이 적합하다.다만, 이전에 선택 정렬 문제에서 사용한 인덱스를 활용한 방식으로 데이터를 저장하는 방법도 고려할 수 있다.

 

전체 코드

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

public class Main {

    private static boolean[] isPrime;

    public static void main(String[] args) throws IOException {
        solve();
    }

    private static void solve() throws IOException {

        sieveOfEratosthenes(1000000);

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0;i<N;i++){
            int num = Integer.parseInt(bufferedReader.readLine());
            String result = String.valueOf(findGBPartitions(num));
            stringBuilder.append(result)
                    .append("\n");
        }

        System.out.println(stringBuilder);
    }


    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }
}

 

반응형
반응형
이번 글에서는 백준 28116번 문제를 통해 선택 정렬 알고리즘을 활용하고,
이를 통해 성능 최적화 방안을 탐구해보려 한다.
선택 정렬의 기본 개념을 바탕으로 문제 해결 과정과 효율성을 높이는 방법을 단계별로 살펴보자.

 

문제 핵심

  • 이 배열은 N까지의 정수가 정확히 한 번씩 등장한다. 즉 중간에 빠진 정수나 중복된 수가 존재하지 않는다.
  • 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다
  • 이 과정에서 교환이 이루어질 때 이동한 거리를 각각 저장한다.
  • N : 배열의 길이

풀이 과정

이전의 선택정렬의 문제와 같이 2중 반복을 통해 풀었다. 하지만 이번의 N의 최대길이가 다르다.

지난 번 23881번 문제에서는 N이 10,000 즉, O(N^2)의 시간 복잡도를 가지더라도 10,000,000의 연산을 한다.

하지만 이번 문제는 N이 500,000으로 어마 어마한 숫자다. 특히 자바로 문제는 푸는 나에게는 더욱 더 좋지 않은 상황이다. 

    private static void solve() {

        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                 if(arr[j] < arr[minIndex]) {
                     minIndex = j;
                 }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;

                int distance = minIndex - i;
                arrSwapCount[arr[minIndex] - 1] += distance;
                arrSwapCount[arr[i] - 1] += distance;
            }
        }
    }

 

[ 문제 ] 시간 초과

그렇다면 위 코드는 아무리 줄여나가도 2중 반복이라는 한계로 시간초과의 문제를 해결할 수 없다. 어떻게 해야 할까?

한 개의 반복문에 모두 녹여내야 한다. 코드 몇 줄 최적화 시킨다고 해서 나아질 문제가 아닌 것이다. 

 

문제 해결

문제를 고민하던 중, 제한 조건에 있던 "각 정수는 N까지 정확히 한 번씩 등장한다"는 점이 눈에 들어왔다. 이 조건을 활용하면 인덱스를 이용한 접근이 가능하다고 판단했다. 이를 바탕으로, "위치를 저장하는 배열과 기존의 정렬 대상 배열을 비교하며 값을 처리할 수 있을 것"이라는 아이디어를 떠올렸다. 그 후, 이 규칙을 기반으로 점차 로직을 구체화하며 코드를 작성했다.

 

과정은 다음과 같다. ( 백준 두 번째 예시값 )

 

1. 초기화 단계

먼저 주어진 배열이 다음과 같이 저장되고, 값의 위치를 저장하는 배열로 두개를 선언한다.

 

0부터 시작하는 특성으로 num - 1을 선언하였으나

헷갈리지 않게 사용하려면 배열을 N + 1 만큼 사용하고 0 인덱스를 제외하여 사용하면 된다.

아래 그림에 실제 가르키는 값은 다음과 같다. 제외하고 봐도 무방하다.

    private static int[] arr;
    private static int[] numLocations;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }

 

그림과 같이 저장된다.

 

2. 알고리즘 단계

위 그림을 보면 감이 올지도 모른다.

한 개의 반복문에서 index를 활용하여 매치 시키고, 위치에 있어야 할 값과 맞지 않는다면

해당 위치에 있는 값원래 있어야 하는(순서에 맞는) 값을 찾고 거리값을 구한다. 

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[numLocations[arr[i]]] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }

i = 0 일때

0 = 0 ( 실제로는 1 = 1 ) 이므로 위치에 맞게 존재한다.

i = 1 일때 ( num - 1 인 것을 감안해야 한다 )

위 그림과 같이 i = 1 ( 두 번째 위치) 에 1 (2) 이 있어야 한다.

그렇다면 numLocation[1] 을 통해 원래 있어야 하는 값의 위치를 찾는다.

왼쪽부터 정렬하며 오기 때문에 i값은 항상 작다. 때문에 numLocation[i] - i를 통해 거리를 계산 할 수 있다.

또한, 값의 교환이 할 필요는 없고, i 값에 해당하는 상태는 이제 필요없기 때문에 이 후 계산할 곳에만 값을 넣어준다.

이 후 distance의 값을  moveCount 배열에 더해주면 정수마다 이동한 거리 값이 계산된다.

 

나머지도 위를 통해 문제를 해결할 수 있다.

 

선택 정렬이라고 해서 무조건 2중 반복문을 사용하는게 아닌
그 틀은 그대로 유지하며 다르게 풀어나갈 수 있다는 것
활용하는 것이 가장 중요하다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int[] arr;
    private static int[] numLocations;
    private static int[] moveCounts;

    public static void main(String[] args) throws IOException {
        prepre();
        solve();
        Arrays.stream(moveCounts).forEach(num -> System.out.print(num + " "));
    }

    private static void prepre() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        arr = new int[N];
        numLocations = new int[N];
        moveCounts = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }
    }

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[i] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }
}
반응형

+ Recent posts