[SWEA] #8275 햄스터, #1210 Ladder1, #1218 괄호 짝짓기 (java)

#8275 햄스터

문제로가기

 

문제 이해,  해결 방법 고안

 

 

 

 

이 문제는 중복 순열 (순서가 있어야 하고, 숫자가 중복으로 들어갈 수 있음)이다.

중복 순열 중에서 m에 맞는 조건들을 다 만족하는 것을 출력하는 구현 문제이기도 하다.

 

처음 푸는데 1시간 이상 걸렸고, 한번 더 풀어보는데도 30분 이상은 걸렸다. 마지막에 출력에 신경 써야 TestCase를 다 만족시킬 수 있다.

어차피 순열로 나오는 배열들은 오름차순으로 나오기 때문에 이 조건은 신경쓰지 않아도 됐었다!

그리고 나는 마지막에 최종 나오는 (출력해야 하는) 후보를 res 배열에 담았는데 n이 1이 될 수 있기도 때문에 초기화를 null로 해주는 것도 처리해줘야 한다 ~!

 

애증의 햄스터 코드는 아래에 있다.

import java.io.*;
import java.util.*;

public class SWEA8275햄스터 {
    private static int T,n,x,m;
    private static int[] l_arr,r_arr,s_arr;
    private static int[] candidate; //n개의 후보
    private static int[] ham; //우리 안에 든 햄스터
    private static int[] res;
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(input.readLine());
        for(int t=1; t<=T; t++){
            tokens = new StringTokenizer(input.readLine());
            n = Integer.parseInt(tokens.nextToken());
            x = Integer.parseInt(tokens.nextToken());
            m = Integer.parseInt(tokens.nextToken());

            candidate = new int [n];
            res = null;
            ham = new int[x+1];
            l_arr = new int[m];
            r_arr = new int[m];
            s_arr = new int[m];
            for(int i=0; i<m; i++){
                tokens = new StringTokenizer(input.readLine());
                l_arr[i] = Integer.parseInt(tokens.nextToken());
                r_arr[i] = Integer.parseInt(tokens.nextToken());
                s_arr[i] = Integer.parseInt(tokens.nextToken());
            }
            //0부터 X까지 햄스터 우리에 들어갈 수 있는 최대 수
            for(int i=0; i<=x; i++){
                ham[i] = i;
            }
            permutatoin(0);
            output.append("#").append(t);
            if (res == null) {  // 기록을 만족하는 배치가 없는 경우
                output.append(" -1\n");
            } else {
                for (int r : res) {
                    output.append(" ").append(r);
                }
                output.append("\n");
            }
        }
        System.out.print(output);
    }
    private static void permutatoin(int cnt){ //n개의 배열를 만듬
        boolean flag = true;
        int sum = -1;
        if(cnt == n){
            //candiate 배열 나온 거 중에서 m 리스트를 만족하는 것만 선별
            for(int i=0; i<m; i++){
                int s=0;
                for(int j=l_arr[i]-1; j<r_arr[i]; j++){
                    s+=candidate[j];
                }
                if(s != s_arr[i]) {
                    flag = false;
                }
            }
            if(flag){ //m의 리스트를 다 만족하는 것 중에서
                // 배열의 합을 구함
                sum = arrSum(candidate); //현재수 합의 수
                //넣어있는 것보다 후보가 더 크다면,
                //같은거는 생각 안해줌, 어차피 오름 차순으로 넣기 때문에 신경X
                if(arrSum(res) < sum){
                    res = candidate.clone(); // 넣기
                }
            }
            //System.out.println(Arrays.toString(res));
            return;
        }
        //햄스터 마리 중에서 후보 배열을 만듬
        for(int i=0; i<ham.length; i++){
            candidate[cnt] = ham[i];
            permutatoin(cnt+1);
        }
    }
    //배열의 합을 구하는 함수
    private static int arrSum(int can[]){
        int sum=0;
        if(can == null){
            return -1;
        }
        else{
            for(int i=0; i<can.length; i++){
                sum += can[i];
            }
            return sum;
        }
    }
}

 

#1210 Ladder1

문제로가기

문제이해

문제를 보고 어떠한 카테고리 필요없이 완탐, 구현으로 가보자는 생각이 들었다.

목적지가 주어지니 출발지를 출력하는 문제이다.

 

해결 방법 고안

목적지를 먼저 좌표를 구하고 그 좌표가 출발지까지 도착할 때 index를 구한다.

출발지는 여러개이나 목적지는 1개이기 때문에 목적지에서 출발지를 구하는 것이 유리하다고 생각했다.

왼쪽에 길이 있으면 최대한 왼쪽으로, 오른쪽 길이 있으면 최대한 오른쪽으로 가면 된다. 이런 문제는 너무 복잡하게 생각하지 말고 "구현"에만 집중하면 될 것 같다.

 

 

코드는 아래에

import java.io.*;
import java.util.*;
public class SWEALadder1 {
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        for(int T=1; T<=10; T++){
            int t = Integer.parseInt(input.readLine());
            int ladder[][] = new int[100][100];
            int c = -1;
            //사다리 저장, [row][column]에서 c 찾기
            for(int i=0; i<100; i++){
                tokens =new StringTokenizer(input.readLine());
                for(int j=0; j<100; j++){
                    ladder[i][j] = Integer.parseInt(tokens.nextToken());
                    if(ladder[i][j]==2){
                        c = j;
                    }
                }
            }
            //[99][c]에서 위로 올라가서
            //[0][정답]이 되는 것을 찾기
            int row = 99;
            while(row > 0){
                //왼쪽으로 가는 방향이 있고, 가는길(1)이 있다면
                if(c-1 >=0 && ladder[row][c-1]==1){
                    //왼쪽 길이 끝날때까지 왼쪽으로 가기
                    while(c-1 >=0 && ladder[row][c-1]==1){
                        c--;
                    }
                }
                //오른쪽 길이 있다면 오른쪽으로 가기
                else if(c+1<=99 && ladder[row][c+1]==1){
                    //왼쪽 길이 끝날때까지 왼쪽으로 가기
                    while(c+1<=99 && ladder[row][c+1]==1){
                        c++;
                    }
                }
                //둘다 없다면 그냥 위로 올라가기
                row--;
            }
            output.append("#").append(t).append(" ").append(c).append('\n');
        }
        System.out.print(output);
    }
}

 

 

 

 

 

 

 

 

 

 

 

#1218 괄호 짝짓기

문제로가기

 

문제 이해

괄호가 입력으로 주어지는데 이 괄호의 짝이 맞으면 1, 맞지 않으면 0을 출력한다.

 

해결 방법 고안

stack을 이용한다. stack은 LIFO 구조로 괄호의 짝을 파악하는 것이 유리하다.

<, (, [, { 왼쪽 괄호가 나오면 stack에 push하고, >, ), ], } 오른쪽 괄호가 나오면 stack에 pop한다.

그 대신 오른쪽 괄호가 나오면 그 전 괄호가 왼쪽 괄호와 짝이 맞아야 한다.

1. 왼쪽 괄호가 나오면 실행을 중단하고 바로 0을 출력한다.

2. 반복이 끝나고 stack이 비어있지 않으면 0을 출력한다.

3. 스택이 비어있고 실행이 중단되지 않은 상태에만 1을 출력한다.

 

삽질

삽질 1: 처음에 StringTokenizer로 String str에 바로 넣고  str.charAt(i) 구조로 반복문을 돌렸더니 이상하게 출력되더라 ? ,, 왜 그런지 모르겠다. 지금은 잘 되는데.. 그래서 String에 넣는게 아니라 String str[] 배열을 만들어서 넣었다.

String arr[] = str.split[] 이 방법으로 넣을 수 있었다.

 

삽질 2: pre라는 String을 만들어서 전에 문자열을 넣으려고 했다. 나는 arr에서 몇번데 index를 pre에 넣어야 할까 고민했는데 고민할 필요도 없이 그냥 stack.peek()를 사용하면 됐었다. 호호.. stack peek는 바로 위에있는 것을 가리키기 때문이다.

 

코드는 아래에

import java.io.*;
import java.util.*;
 
 
public class Solution {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static int n;
 
    public static void main(String[] args) throws IOException {
 
        for(int test=1; test<11; test++){
            boolean flag = true;
            n = Integer.parseInt(input.readLine());
            tokens = new StringTokenizer(input.readLine());
            String str =tokens.nextToken();
            Stack<String> stack = new Stack<>();
            String arr[] = str.split("");
            String pre = arr[0];
            for(int i=0; i<arr.length; i++){
                if(arr[i].equals("(") || arr[i].equals("[") || arr[i].equals("<") || arr[i].equals("{")){
                    stack.push(arr[i]);
                    pre = arr[i];
                }
                else if(arr[i].equals(")")){
                    if(pre.equals("(")){
                        stack.pop();
                        if(!stack.isEmpty()){
                            pre = stack.peek();
                        }
                    }
                    else{
                        flag = false;
                        break;
                    }
                }
                else if(arr[i].equals("}")){
                    if(pre.equals("{")){
                        stack.pop();
                        if(!stack.isEmpty()){
                            pre = stack.peek();
                        }
 
                    }
                    else{
                        flag = false;
                        break;
                    }
                }
                else if(arr[i].equals("]")){
                    if(pre.equals("[")){
                        stack.pop();
                        if(!stack.isEmpty()){
                            pre = stack.peek();
                        }
 
                    }
                    else{
                        flag = false;
                        break;
                    }
                }
                else if(arr[i].equals(">")){
                    if(pre.equals("<")){
                        stack.pop();
                        if(!stack.isEmpty()){
                            pre = stack.peek();
                        }
                    }
                    else{
                        flag = false;
                        break;
                    }
                }
            }
            output.append("#").append(test).append(" ");
            //스택이 비어있지 않거나 flag가 false이라면 0출력
 
            if(!stack.isEmpty() || !flag){
                output.append(0).append("\n");
 
            }
            else output.append(1).append("\n");
        }
        System.out.println(output);
    }
}