[Coding test] 0328_no.3 (java)

2020-03-28

Coding test / 0328_no.3

문제설명

유출 x

풀이

package T0328;

public class t3 {

	public static int solution(int A[]) {
		String s1 = "", s2 = "", s3= "", s4 = "";
		for(int i=0; i<A.length-1; i++) {
			if(i%2 == 0) {
				s1 += "0";
				s2 += "1";
			}
			else {
				s1 += "1";
				s2 += "0";
			}
		}
		
		for(int i=0; i<A.length-2; i++) {
			if(i%2 == 0) {
				s3 += "0";
				s4 += "1";
			}
			else {
				s3 += "1";
				s4 += "0";
			}
		}
		
		//지우지 않고도 조건을 만족하는지
		String a = "";	int answer = -1;	int cnt = 0;
		for(int i=1; i<A.length; i++) {
			if(A[i] > A[i-1])
				a += "0";
			else if(A[i] < A[i-1])
				a += "1";
			else
				a += "-";
		}
		
		if(a.charAt(0) == '0' && a.equals(s1))
			return 0;
		
		else if(a.charAt(0) == '1' && a.equals(s2))
			return 0;
		
		//아닌 경우에
		for(int i=0; i<A.length; i++) {
			int arr[] = new int[A.length-1];
			
			int k = 0;
			for(int j=0; j<A.length; j++) {
				if(i == j)
					continue;
				arr[k++] = A[j];
			}
			
			String s = "";
			for(int j=1; j<A.length-1; j++) {
				if(arr[j] > arr[j-1])
					s += "0";
				else if(arr[j] < arr[j-1])
					s += "1";
				else
					s += "-";
			}
			
			if(s.charAt(0) == '0' && s.equals(s3))
				cnt++;
			else if(s.charAt(0) == '1' && s.equals(s4))
				cnt++;
				
		}
		
		if(cnt != 0)
			answer = cnt;
		
		return answer;
	}
	
	public static void main(String[] args) {
		int a[] = {3,4,5,3,7};
		int b[] = {1,2,3,4};
		int c[] = {1,3,1,2};
		int d[] = {1,1,1,1,1};
		
		System.out.println(solution(d));
	}
}
Read More

[Coding test] 0328_no.2 (java)

2020-03-28

Coding test / 0328_no.2

문제설명

유출 x

풀이

package T0328;

import java.util.Arrays;

public class t2 {

	public static int calc(int n) {
		int remain = 0;
		while(n!=0) {
			remain += n%10;
			n = n/10;
		}
		
		return remain;
	}
	
	public static int solution(int A[]) {
		int arr[][] = new int[82][2];
		
		Arrays.sort(A);
		
		for(int i=0; i<A.length; i++) {
			int n = calc(A[i]);
			
			if(arr[n][0] == 0)
				arr[n][0] = A[i];
			
			else if(arr[n][0] !=0 && arr[n][1] ==0)
				arr[n][1] = A[i];
			
			else if(arr[n][0] !=0 && arr[n][1] !=0) {
				int temp = arr[n][1];
				arr[n][1] = A[i];
				arr[n][0] = temp;
			}
		}
		
		int max = -1;
		
		for(int i=1; i<82; i++) {
			if(arr[i][0] !=0 && arr[i][1] !=0)
				max = Math.max(max, arr[i][0] + arr[i][1]);
		}
		
		return max; // 20억까지는 감당 가능하다 
	}
	
	public static void main(String[] args) {
		int a[] = {51,71,17,42};
		int b[] = {42,33,60};
		int c[] = {51,32,43};
		int d[] = {1000000000,1000000000, 10, 10};
		int e[] = {999999999,999999999};
		
		int f[] = new int[200000];
		
		for(int i=0;i<f.length; i++)
			f[i] = 1000000000;
		
		System.out.println(solution(f));
	}
}
Read More

[Coding test] 0328_no.1 (java)

2020-03-28

Coding test / 0328_no.1

문제설명

유출 x

풀이

package T0328;

import java.util.*;

public class t1 {

	public static int solution(int A[]) {
		int arr[] = new int[100001]; //10만까지 담기위해
		boolean chk[] = new boolean[100001];
		
		int answer = 0;//초기화
		
		Arrays.sort(A);
		
		for(int i=0; i<A.length; i++) {
			int num = A[i];
			
			if(num >100000)
				continue;
			else {
				++arr[num];
				if(arr[num] == num)
					chk[num] = true;
				else
					chk[num] = false;
			}
		}
		
		for(int i=1; i<100001; i++) {
			if(chk[i])
				answer = i;
		}
		
		
		return answer;
	}
	
	public static void main(String[] args) {
		int a[] = {3,8,2,3,3,2};
		int b[] = {7,1,2,8,2};
		int c[] = {5,5,5,5,5};
		int d[] = {3,1,4,1,5};
		
		
		int f[] = new int[100000];
		
		for(int i=0;i<f.length-1; i++)
			f[i] = 100000;
		
		System.out.println(solution(f));
	}
}
Read More

[프로그래머스] N으로 표현 (java) Dynamic_programming

2020-03-27

N으로 표현 (프로그래머스> Dynamic_programming)

문제 링크

문제설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항
  • N은 1 이상 9 이하입니다.
  • number는 1 이상 32,000 이하입니다.
  • 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
  • 최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
N number return
5 12 4
2 11 3
입출력 예 설명

예제 #1 문제에 나온 예와 같습니다.

예제 #2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.


풀이

package Dynamic_programming;

import java.util.*;

public class prog_3_N으로표현 {

	static int answer = -1;
	public static void dfs(int n, int number, int cnt, int prev) {
		int temp = n; //

		if(cnt>8) // 8보다 커지면 -1
			return;
		
		if(number == prev) { //숫자가 같을 때
			System.out.println(cnt + " " + answer + " " + prev);
			if(answer == -1 || answer >cnt) //answer가 -1일때 최초로 바뀌는거니까 or answer가 cnt보다 클 떄
				answer = cnt;
			return;
		}
		
		for(int i=0; i<8-cnt; i++) {
			dfs(n,number, cnt+i+1, prev- temp);
			dfs(n,number, cnt+i+1, prev + temp);
			dfs(n,number, cnt+i+1, prev * temp);
			dfs(n,number, cnt+i+1, prev / temp);
			
			temp = temp*10 + n;
		}
		
	}
	
    public static int solution(int N, int number) {
    	
    	dfs(N,number,0,0);
        return answer;
    }
    
    public static void main(String[] args) {
		System.out.println(solution(5,12));
	}
}

후기 (2h)

혼자 방법으로는 절대 이해해낼 수 없는 문제…. 였다…

Read More

[백준] 문자열 폭발 (java) Stack

2020-03-27

문자열 폭발 (백준> 문자열 & Stack_Queue)

문제 링크

문제설명

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1 복사

mirkovC4nizCC44
C4

예제 출력 1 복사

mirkovniz

예제 입력 2 복사

12ab112ab2ab
12ab

예제 출력 2 복사

FRULA


풀이

package String;

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


public class beak_문자열폭발 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		String pattern = br.readLine();
		
		Stack<Character> stk = new Stack<>();
		
		for(int i=s.length()-1; i>=0; i--) {
			
			stk.push(s.charAt(i));// 일단 넣고
			
			if(stk.peek() == pattern.charAt(0) &&stk.size() >= pattern.length()) {// 같은 경우에는
				boolean ck = false;

					for(int j=0; j<pattern.length(); j++) {
						if(pattern.charAt(j) != stk.get(stk.size()-1-j)) {
							ck = true;
							break;
						}
					}
					
					if(ck == false) { // 같다는거니까 패턴만큼 pop
						for(int j=0; j<pattern.length(); j++)
							stk.pop();
					}
				
			}
		}//for
	
		if(stk.size() ==0)
			System.out.println("FRULA");
		else {
			int size = stk.size();
			for(int i=0; i<size; i++)
				System.out.print(stk.pop());
		}
		
	}
}

후기 (40min)

사실 replace로 풀면 문제가 쉽게 풀리는데 시간초과가 계속 떠서 탈락…

문자를 뒤에서부터 스택에 넣고 푸쉬 팝하는 방식으로 풀면 쉽게 풀 수 있었다!!

이걸 어떻게 생각해 내는지… 우앙

  • 처음 푼 방법
 public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s = bf.readLine();
		String pattern = bf.readLine();
		
		while(true) {
			boolean ck = false;
			
			if(s.length() == 0){
				System.out.println("FRULA");
				break;
			}
			else {
				if(s.contains(pattern))
					s = s.replaceAll(pattern, ""); // 소름... 치환한거 다시 넣어줘야지
				else {
					System.out.println(s);
					break;
				}
			}
			
		}//while
	}
Read More