2019-03-22 [JAVA]백준 11403번 - 경로 찾기

22 Mar 2019 | java algorithm_study

문제 출처

https://www.acmicpc.net/problem/11403

문제

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다

문제 풀이

우선 그래프를 나타내는 배열 생성

for(int i=0; i<N; i++)
            for (int j=0; j<N; j++)
                graph[i][j] = sc.nextInt();

bfs 메소드 생성

public static void bfs(int graph_x, int graph_y){
        isVisited[graph_y] = false;
        Queue<Integer> q = new LinkedList<>();
        q.offer(graph_y);
  
        while (!q.isEmpty()){
            int tmp = q.poll();
  
            for (int i=0; i<N; i++)
                if(isVisited[i]== false && graph[tmp][i] == 1){
                    q.offer(i);
                    graph[graph_x][i] =1;//경로가 있을 경우 해당 그래플 배열을 1로 바꾼다.
                    isVisited[i] = true;
                }
        }
    }

1일때 해당 정점에 경로가 있을경우 queue에 넣고 큐에서 하나씩 꺼내어 해당 정점에 경로가 있을경우 다시 queue에 넣는다. (정점 방문 체크)
경로가 있을 경우 해당 그래플 배열을 1로 바꾼다.

전체 소스

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Baekjoon_11403 {
    static int[][] graph;
    static boolean[] isVisited;
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

         N= sc.nextInt();
        graph = new int[N][N];

        for(int i=0; i<N; i++){ //입력
            for (int j=0; j<N; j++){
                graph[i][j] = sc.nextInt();
            }
        }

        for(int i=0; i<N; i++){ //bfs
            isVisited = new boolean[N]; //방문 체크 초기화
            for (int j=0; j<N; j++){
                if(graph[i][j] == 1 && isVisited[j] == false){
                    bfs(i, j);
                }
            }
        }

        for(int i=0; i<N; i++){ //출력
            for(int j=0; j<N; j++){
                System.out.print(graph[i][j]+" ");
            }
            System.out.println();
        }

    }
    public static void bfs(int graph_x, int graph_y){
        isVisited[graph_y] = false;
        Queue<Integer> q = new LinkedList<>();
        q.offer(graph_y);

        while (!q.isEmpty()){
            int tmp = q.poll();

            for (int i=0; i<N; i++)
                if(isVisited[i]== false && graph[tmp][i] == 1){
                    q.offer(i);
                    graph[graph_x][i] =1; //경로 존재시 1로 변경
                    isVisited[i] = true;
                }
        }
    }
}

Comment Read more

2019-03-21 [JAVA]백준 11053 - 가장 긴 증가하는 부분 수열

22 Mar 2019 | java algorithm_study

문제출처

https://www.acmicpc.net/problem/11053

풀이

dp => 최대 수열 개수

num	10	20	10	30	20	50
Dp	1	2	1	3	2	4

dp[n]은 n-1까지 수들 중 num[n]보다 작은 값에서 최대 dp+1
num[n]보다 작은 값이 없을 때 dp[n] = 1
출력은 dp중 가장 큰 값

for (int i=2; i<=n; i++){
            for (int j=1; j<i; j++){
                if(num[i]>num[j])
                    dp[i] = Math.max(dp[i], dp[j]+1);
                else
                    dp[i] = Math.max(dp[i], 1);
            }
        }

전체소스

import java.util.Scanner;

public class Baekjoon_11053 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        int n = sc.nextInt();
        int[] num = new int[n+1];
        int[] dp = new int[n+1];
        
        for(int i=1; i<=n;i++)
            num[i] =sc.nextInt();
        dp[1] = 1;

        for (int i=2; i<=n; i++){
            for (int j=1; j<i; j++){
                if(num[i]>num[j])
                    dp[i] = Math.max(dp[i], dp[j]+1);
                else
                    dp[i] = Math.max(dp[i], 1);
            }
        }

        int max = 0;
        for(int i=1; i<=n; i++)
            max = Math.max(max, dp[i]);

        System.out.println(max);
    }
}

Comment Read more

2019-03-21 [JAVA]백준11052번 - 카드 구매하기

22 Mar 2019 | java algorithm_study

문제 출처

https://www.acmicpc.net/problem/11052

풀이

dp[4]를 구할때 경우의 수

card[4] + dp[0]
card[3] + dp[1]
card[2] + dp[2]
card[1] + dp[3]

따라서

for(int i=2; i<=n; i++)
        for(int j=1; j<=i;j++)
            dp[i] =max(dp[i], card[j]+dp[i-j]);

이 때 dp[0] = 0, dp[1] = card[1]

전체 소스

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;

    cin >> n;
    int card[n+1];
    int dp[n+1];

        for(int i=1; i<n+1; i++){
            cin >> card[i];
        }

        for(int i=0; i<n+1; i++)
            dp[i] = 0;
    dp[1] = card[1];

    for(int i=2; i<=n; i++){
        for(int j=1; j<=i;j++){
            dp[i] =max(dp[i], card[j]+dp[i-j]);
        }
    }
    
    cout << dp[n]<< endl;

}

Comment Read more

2019-03-21 [JAVA]백준 10989번 - 수 정렬하기

22 Mar 2019 | java algorithm_study

문제 출처

수 정렬하기 3 : https://www.acmicpc.net/problem/10989

문제 풀이 1

Array 배열 라이브러이 사용 => 시간 초과

풀이 2

10000 크기의 배열 생성
입력값. = 배열 인덱스 => 배열 카운트 up
카운트된 배열 출력

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);

        int n = sc.nextInt();
        int[] array = new int[10001];

        for(int i=0; i<n; i++)
        array[sc.nextInt()]++;


        for(int i=1; i<=10000; i++){
            for(int j=0; j<array[i]; j++)
                System.out.println(i);
        }
    }
}

풀이 3

BufferedReader , BufferedWriter 사용

전체 소스

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

public class Baekjoon_10989 {
    public static void main(String[] args) throws IOException {
        Scanner sc =new Scanner(System.in);

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] array = new int[10001];

        for(int i=0; i<n; i++)
        array[Integer.parseInt(br.readLine())]++;


        for(int i=1; i<=10000; i++){
            for(int j=0; j<array[i]; j++)
                bw.write(i+"\n");
        }

        br.close();
        bw.close();
    }
}

Comment Read more

2018-07-11 [JAVA] 백준 1406번 - 에디터

11 Jul 2018 | java algorithm_study

문제 출처

https://www.acmicpc.net/problem/1406

풀이법

cursor의 위치를 파악하여 string의 concat, substring을 활용

import java.util.Scanner;

public class Baekjoon_1406 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        int n = sc.nextInt();
        int cursor = str.length();
        String tmp, input;
        char ch;

        for (int i = 0; i < n; i++) {
            input = sc.next();
            ch =input.charAt(0);
            if (ch == 'L') {
                if (cursor > 0)
                    cursor = cursor-1;
            } else if (ch == 'D') {
                if (cursor < str.length())
                    cursor = cursor+1;
            } else if (ch== 'B') {
                if (cursor == 0) { //커서가 맨 앞일 때
                } else if (cursor == str.length()) { //문자열 끝에 커서
                    str = str.substring(0, str.length() - 1);
                    cursor  =cursor-1;
                } else {
                    tmp = str.substring(0, cursor - 1);
                    str = tmp.concat(str.substring(cursor));
                    cursor  =cursor-1;
                }
            } else if (ch == 'P') {
                input = sc.next();
                if (cursor == 0) { //커서가 맨 앞일 때
                    str = input.concat(str);
                    cursor  =cursor+1;
                } else if (str.length() == cursor) { //문자열 끝에 커서
                    cursor  =cursor+1;
                    str = str.concat(input);
                } else {
                    tmp = str.substring(0, cursor);
                    tmp = tmp.concat(input);
                    str = tmp.concat(str.substring(cursor));
                    cursor  =cursor+1;
                }
            }
        }
        System.out.println(str);
    }
}

=> 메모리 초과

풀이법

stackA, stackB 두 개의 스택을 이용하여 문제해결
커서를 기준으로 왼쪽은 stackA 오른쪽은 stackB (코드 상은 StackA = st, StackB = st_tmp)
L => 커서 왼쪽으로 이동시 stackA의 top -> stackB
D => 커서 왼쪽으로 이동시 stackB의 top -> stackA
P => 커서 왼쪽에 입력 stackA에 push
B => 커서의 왼쪽 삭제 stackA pop으로 삭제

스택 활용

import java.util.Scanner;
import java.util.Stack;

public class Baekjoon_1406 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        int n = sc.nextInt();
        String input;

        Stack<Character> st = new Stack<>();
        Stack<Character> st_tmp = new Stack();

        for (int i=0; i< str.length(); i++){
            st.push(str.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            input = sc.next();
            if (input.charAt(0) == 'L') { //커서 왼쪽이동
                if(!st.empty())
                    st_tmp.push(st.pop());
            } else if (input.charAt(0) == 'D') { //커서 오른쪽이동
                if(!st_tmp.isEmpty()){
                    st.push(st_tmp.pop());
                }
            } else if (input.charAt(0)== 'B') { //커서 왼쪽 삭제
                if(!st.isEmpty()){
                    st.pop();
                }
            } else if (input.charAt(0) == 'P') { //커서 왼쪽 입력
                input = sc.next();
                st.push(input.charAt(0));
            }
        }
//출력
        while (!st.isEmpty()){ //stack의 LIFO 성질 때문에 stack_tmp에 이동후 출력
            st_tmp.push(st.pop());
        }
        while (!st_tmp.isEmpty()){
            System.out.print(st_tmp.pop());
        }
        System.out.println();
    }
}

=> 메모리 초과

풀이

Scanner 대신 BufferedReader 사용

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

public class Baekjoon_1406 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str = br.readLine();
        int n = Integer.parseInt(br.readLine());
        String input;

        Stack<Character> st = new Stack<>();
        Stack<Character> st_tmp = new Stack();

        for (int i=0; i< str.length(); i++){
            st.push(str.charAt(i));
        }

        for (int i = 0; i < n; i++) {
            input = br.readLine();
            if (input.charAt(0) == 'L') {
                if(!st.empty())
                    st_tmp.push(st.pop());
            } else if (input.charAt(0) == 'D') {
                if(!st_tmp.isEmpty()){
                    st.push(st_tmp.pop());
                }
            } else if (input.charAt(0)== 'B') {
                if(!st.isEmpty()){
                    st.pop();
                }
            } else if (input.charAt(0) == 'P') 
                st.push(input.charAt(2));
            
        }

        while (!st.isEmpty()){
            st_tmp.push(st.pop());
        }
        while (!st_tmp.isEmpty()){
            System.out.print(st_tmp.pop());
        }
        System.out.println();
    }
}

=> 해결

Comment Read more

Older Newer

Develope Story

2019-03-22 [JAVA]백준 11403번 - 경로 찾기

문제

입력

출력

2019-03-21 [JAVA]백준 11053 - 가장 긴 증가하는 부분 수열

2019-03-21 [JAVA]백준11052번 - 카드 구매하기

2019-03-21 [JAVA]백준 10989번 - 수 정렬하기

2018-07-11 [JAVA] 백준 1406번 - 에디터