山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.22 括弧の対応

アルゴリズムの問題

No.22 括弧の対応 - yukicoder

括弧の対応に関する問題で、結構悩みました(´・ω・`)

方針

・括弧を一つずつ配列に格納します。 ・配列先頭から調べて、")"が初めて出現したときの配列の要素番号をiとします。 ・配列のi番目の要素を0で置き換えます。 ・i-1から0に向かって配列の要素を調べて、"("が初めて出現したときの配列の要素をjとします。 ・配列のj番目の要素を0で置き換えます。 ・このときiとjは括弧の対応となり、K=iならばjが、K=jならばiが答えとなります。

感想

もっと計算速度が速い方法があるそうなので、調べてみます。

コード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Parentheses {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        //
        K = K - 1;
        String str = null;
        BufferedReader input = new BufferedReader (
                new InputStreamReader (System.in));
        try {
            str = input.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        scanner.close();
        List<String> list = Arrays.asList(str.split(""));


        int count = 0;
        boolean flag1 = true;
        while(flag1) {
            count ++;
            if(count > 20) {
                break;
            }
            for(int i = 0; i < N; i++) {
                if(list.get(i).equals(")")) {
                    list.set(i, "0");
                    for(int j = i - 1; j > -1; j--) {
                        if(list.get(j).equals("(")) {
                            list.set(j, "0");
                            if(i == K) {
                                System.out.println(j + 1);
                                flag1 = false;
                            }else if(j == K) {
                                flag1 = false;
                                System.out.println(i + 1);
                            }
                            break;
                        }
                    }
                }
                if(flag1 == false) {
                    break;
                }
            }
        }
    }
}

追記

(2018年9月25日)

スタックを使うことでもっと簡単に書けるようです。しかし、最初に書いたコードはやばいな。

コード

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Exec0022 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        String S = scan.next();

        scan.close();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        K--;
        for(int i = 0; i < N; i++) {
            char c = S.charAt(i);
            if(c == '(') {
                stack.push(i);
            }else {
                int k = stack.pop();
                if(i == K) {
                    System.out.println(k + 1);
                    break;
                }else if(k == K) {
                    System.out.println(i + 1);
                }
            }
        }
    }
}