[백준] 잃어버린 괄호 (java) Greedy

2020-03-02

잃어버린 괄호 (백준> Greedy)

문제설명

세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

풀이

package Greedy;

import java.util.*;

//50min
public class beak_잃어버린괄호 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		
		//처음은 무조건 +부터 시작하니까 -나오기 전까지 더해주고 이 값에서 나중에 나온 값을 빼준다
		String s_split[] = s.split("-"); //- 다 뺴준다    --> +와 숫자가 섞여있다
		
		String tmp[] = s_split[0].split("\\+"); // 첫 - 전 숫자들은 +로만 이루어져있으니까 따로 전부 더한다! -->숫자만 들어있다
		
		int first = 0;
		for(int i=0;i<tmp.length;i++)
			first = first + Integer.parseInt(tmp[i]);
		
		int sum=0;
		for(int i=1;i<s_split.length;i++) {
			tmp = s_split[i].split("\\+");
			for(int j=0; j<tmp.length; j++)
				sum = sum + Integer.parseInt(tmp[j]);
		}
		
		System.out.println(first-sum);
		
	}
}

후기 (50min)

좀 익숙해졌다 싶으면 바로 어려워지는 greedy.. dp… 으아ㅏㅏ

문제가 뭔지도 이해를 못하겠는게 많아지니 원.. 더 열심히 하자 복습도

참고 링크

https://dalconbox.tistory.com/41

[백준] 0 만들기 (java) Recursion

2020-03-02

0 만들기 (백준> Recursion)

문제 링크

문제설명

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 … N을 생각하자.

그리고 ‘+’나 ‘-‘, 또는 ‘ ‘(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1 복사

2
3
7

예제 출력 1 복사

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

풀이

package Recursion;

import java.util.*;

//50min
public class beak_0만들기 {

	static int target = 0;
	
	//sum은 이번에 들어온 now에 부호 붙여주고 세번째 재귀때문에 now를 따로 만들어줘야했다
	//dfs(,, now*10 + (next+1)) 새로 들어온 now에 *10해주고 지금 있는 next+1 해줘야 22 이렇게 들어왔을때, 2*10 + (2+1) 가능 
	static void dfs(int sum,int sign, int num, int now, String c) {
		if(now == target) { // 기저조건 now가 target까지 왔을 때
			
			sum = sum + (num * sign); //내가 가진 sum과 이번에 들어온 num*sign이 0인지 확인한다
			if(sum == 0)
				System.out.println(c);
			return ;
		}

		dfs(sum, sign, num*10 + (now+1), now+1, c + " "+String.valueOf(now+1));
		dfs(sum + (sign* num), 1, now+1, now+1, c + "+" + String.valueOf(now+1));
		dfs(sum + (sign*num), -1, now+1, now+1, c + "-" + String.valueOf(now+1));

		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		sc.nextLine();
		
		for(int i=0;i<n;i++) {
			target = sc.nextInt();
			String c = "1";
			
			dfs(0,1,1,1,c); // sum, sign, num, next, str
			
			System.out.println(" ");
		}
		
	}
}

후기 (50min)

타겟넘버랑 비슷한 문제였고… 변수들도 여러개 비슷하게 설정해주었으나, 나오는 숫자를 바로 string에 넣어서 보낼 생각은 하지 못했다. 좀 더 재귀에 익숙해져야겠다…

[백준] 가장 긴 증가하는 부분 수열 (java) Dynamic_programming

2020-03-02

가장 긴 증가하는 부분 수열 (백준> Dynamic_programming)

문제 링크

문제설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

풀이

package Dynamic_programming;

import java.util.*;

//50min
public class beak_가장긴증가하는부분수열 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[] = new int[n];
		int dp [] = new int[n];
		
		for(int i=0; i<n; i++)
			arr[i] = sc.nextInt();
		
		int max_idx = 1;
		
		dp[0] = 1;
		
		for(int i=1; i<n; i++) {
			dp[i] = 1; // 필수!
			for(int j=0; j<i; j++) {
				if(arr[i]>arr[j] && dp[i] <= dp[j])
					dp[i] = dp[j]+1;
				else if(arr[i] == arr[j])
					dp[i] = dp[j];
				
				max_idx = Math.max(max_idx, dp[i]);
			}
		}
		
		System.out.println(max_idx);
	}
}

후기 (50min)

dp로 풀긴 풀었는데… 내가 푼것도 틀린건 아닌거같은데 뭐가 문제일까 흠

 		int n = sc.nextInt();
		
		int arr[] = new int[n];
		
		for(int i=0; i<n; i++)
			arr[i] = sc.nextInt();
		
		int max = arr[0]; int idx =0; int answer=0;
		while(idx < n-1) {
			if(max < arr[idx+1]){
				max = arr[idx];
				idx = idx+1;
				answer++;
			}
			else
				idx++;

		}//while
 

참고링크

https://developer-mac.tistory.com/71

[백준] 적록색약 (java) Dfs

2020-02-28

적록색약 (백준> Dfs_Bfs)

문제 링크

문제설명

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

풀이

package Dfs_Bfs;

import java.util.*;


//35 min
public class beak_적록색약 {
	
	static void is_dfs(char arr[][], char k, int x, int y) {
		arr[x][y] = 'i';
		
		int dx[] = {0,0,1,-1};
		int dy[] = {1,-1,0,0};
		
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>=0 &&nx<arr.length && ny>=0&&ny<arr.length && arr[nx][ny] == k)
					is_dfs(arr,k,nx,ny);
		}
	}
	
	static void not_dfs(char arr[][], char k, int x, int y) {
		arr[x][y] = 'i';
		
		int dx[] = {0,0,1,-1};
		int dy[] = {1,-1,0,0};
		
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>=0 &&nx<arr.length && ny>=0&&ny<arr.length && arr[nx][ny] == k)
				not_dfs(arr,k,nx,ny);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		char arr[][] = new char [n][n];
		char arr_copy[][] = new char[n][n];
		
		
		sc.nextLine();
		
		for(int i=0; i<n; i++) {
			String a = sc.nextLine();
			for(int j=0;j<n;j++) {
				arr[i][j] = a.charAt(j);
				
				if(a.charAt(j) == 'R')
					arr_copy[i][j] = 'G';
				else
					arr_copy[i][j] = a.charAt(j);
			}
		}
		
		int is = 0;
		int not = 0;
		
		//char 배열 만듦 -> 들어갔다 나오면 'i'로 바꿔주기
		for(int i=0;i<n; i++) {
			for(int j=0; j<n; j++) {
				if(arr[i][j] != 'i') {
					not_dfs(arr,arr[i][j],i,j);
					not++;
				}
			}
		}
		
		//G와 B만 있음
		for(int i=0;i<n; i++) {
			for(int j=0; j<n; j++) {
				if(arr_copy[i][j] != 'i') {
					is_dfs(arr_copy,arr_copy[i][j],i,j);
					is++;
				}
			}
		}
		
		System.out.println(not + " " + is);	
	}
	
}

후기 (35min)

두가지 경우의 dfs로 나누어서 풀었다!!

복습 4

2020-02-27

복습 4