'algorithm' 카테고리의 글 목록 (36 Page)

코드

성공 코드 : stack을 써서 풀으면 될 것 같아서 stack을 문자열 뒤에서부터 넣어주면서 폭발시켜야될 문자열이 들어오면

폭발 시킨다. 처음 stack을 써봐서 좀 헤매긴했는데, 라이브러리로 stack기능을 바로 쓰게 해줘서 편했다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<Character> ();
        
        String BombedString = br.readLine();
        String bombString = br.readLine(); 

        for(int i = BombedString.length() - 1; i >= 0;  i--){
            stack.push(BombedString.charAt(i));   

            if(stack.size() >= bombString.length() && stack.peek() == bombString.charAt(0)){
                boolean isBomb = true;
                for(int j = 1; j < bombString.length(); j++){
                    if(stack.get(stack.size()-j-1) != bombString.charAt(j)){
                        isBomb = false;
                        break;
                    }
                } 

                if(isBomb){  
                    for(int j = 0; j < bombString.length(); j++) 
                    	stack.pop();
                }
            }
        }
        

        int stackSize = stack.size();
        StringBuilder sb = new StringBuilder();
        
        if(stack.isEmpty()){
               System.out.println("FRULA");
        }else{
               for(int i = 0; i < stackSize; i++) sb.append(stack.pop());
        }

        System.out.println(sb);

    }

}

다른 사람 코드 : 나보다 시간이 두배 더 빠르다. 코드가 기능별로 메소드로 정리해서 보기 좋고 잘 정리되어 있는 느낌.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bomb = br.readLine();
        String answer = solution(str, bomb);
        System.out.println((answer.length() == 0) ? "FRULA" : answer);
    }

    private static String solution(String str, String bomb) {
        char[] result = new char[str.length()];
        int idx = 0;
        for (int i = 0; i < str.length(); i++) {
            result[idx] = str.charAt(i);
            if (isBomb(result, idx, bomb)) idx -= bomb.length();
            idx++;
        }
        return String.valueOf(result, 0, idx);
    }

    private static boolean isBomb(char[] result, int idx, String bomb) {
        if (idx < bomb.length() - 1) return false;
        for (int i = 0; i < bomb.length(); i++) {
            if (bomb.charAt(i) != result[idx - bomb.length() + 1 + i]) return false;
        }
        return true;
    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1629번 : 곱셈 (0)	2020.08.24
[JAVA] 백준 9613번 : GCD 합 (0)	2020.08.24
[JAVA] 백준 1912번 : 연속합 (0)	2020.08.21
[JAVA] 백준 10942번 : 팰린드롬? (0)	2020.08.21
[JAVA] 백준 1747번 : 소수&팰린드롬 (0)	2020.08.20

코드

정답 코드 : dp를 이용해서 풀었다. 그 전에 dp값과 현재 number값을 더한값과 현재 number값을 비교해서 큰값을 dp[i]에 저장 dp[i]와 max를 비교해서 큰값을 max 변수에 저장하면 최종으로 max에 가장 큰 값이 저장된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int [] number = new int[n];
		int [] dp = new int[n];
		
		for(int i=0;i<n;i++)
			number[i]=Integer.parseInt(st.nextToken());
		
	    dp[0] = number[0];
	    int max = number[0];
	    for(int i=1; i<n; i++){
	         dp[i] = Math.max(dp[i-1]+number[i], number[i]);
	           
	         max = Math.max(max, dp[i]);
	    }

	    System.out.println(max);		

    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 9613번 : GCD 합 (0)	2020.08.24
[JAVA] 백준 9935번 : 문자열 폭발 (0)	2020.08.24
[JAVA] 백준 10942번 : 팰린드롬? (0)	2020.08.21
[JAVA] 백준 1747번 : 소수&팰린드롬 (0)	2020.08.20
[JAVA] 백준 1541번 : 잃어버린 괄호 (0)	2020.08.20

코드

실패 코드 : String으로 받아서 빈공간 없게 해준다음 사용했는데 여기서 런타임이 뜬건가..? 아마도 여기서 뜨는 듯.

int[] 배열로 받아서 가져오니까 런타임은 안떴지만, 시간초과가 떴다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		String string = br.readLine().replace(" ","");  //==>>>여기가 런타임의 원인??(추측)
		
		int M = Integer.parseInt(br.readLine());
		
		for(int i=0;i<M;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			System.out.println(isPalindrome(Integer.parseInt(string),a,b));  //==>>여기가 시간초과의 원인
		}

	}
	
	static int isPalindrome(int number,int a, int b) {
		char [] integerToCharArray = String.valueOf(number).toCharArray();
		int temp = (b-a)/2+a;
		for(int i=a-1;i<=temp;i++) {
			if(integerToCharArray[i] != integerToCharArray[--b]) 
				return 0;
		}
		return 1;
	}
}

성공 코드 : String으로 받아서 빈공간 없게 해준다음 사용했는데 여기서 런타임이 뜬건가..? 아마도 여기서 뜨는 듯.

==>> int[] 배열로 받아서 가져오니까 런타임은 안떴지만, 시간초과가 떴다.

시간초과는 반복문안에서 바로바로 출력을 해줬는데, 출력을 하는사이 작업을 하지 못해서? 그런 듯해서

StringBuilder로 받아온 값을 append 시킨다음 반복문 빠져나온 뒤 한꺼번에 출력해주었다.

결과는 맞았습니다!!

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] palindrom = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) 			
			palindrom[i] =  Integer.parseInt(st.nextToken());
		
				
		int M = Integer.parseInt(br.readLine());
		StringBuilder result = new StringBuilder();
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			
			result.append(isPalindrome(palindrom,
					Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())) +  "\n");
		}

		System.out.println(result.toString());
	}
	
	static int isPalindrome(int[] palindrom,int a, int b) {
		int temp = (b-a)/2 + a;
		for(int i=a;i<=temp;i++) {
			if(palindrom[i] != palindrom[b--]) 
				return 0;
		}
		return 1;
	}
}

다른 사람 코드 : 시간이 나보다 2배는 빠르게 나온다

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

public class Main {
    static int n;
    static int list[];
    static boolean check[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        list= new int[n+1];
        check =new boolean[n+1][n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            list[i] = Integer.parseInt(st.nextToken());
        }

        solve();
        int q = Integer.parseInt(br.readLine());
        for(int i=0; i<q; i++){
            st = new StringTokenizer(br.readLine());
            int start =Integer.parseInt(st.nextToken());
            int end =Integer.parseInt(st.nextToken());
            if(check[start][end]){
                sb.append(1+"\n");
            }else{
                sb.append(0+"\n");
            }
        }

        System.out.println(sb.toString());


    }
    public static void solve(){
        for(int i=1; i<=n; i++){
            check[i][i] = true;
        }

        for(int i=1; i<n; i++){
            if(list[i]==list[i+1]){
                check[i][i+1] = true;
            }
        }

        for(int i=2; i<n; i++){
            for(int k=1; k<=n-i; k++){
                if(list[k]==list[k+i] && check[k+1][k+i-1]){
                    check[k][k+i] = true;
                }
            }
        }

    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 9935번 : 문자열 폭발 (0)	2020.08.24
[JAVA] 백준 1912번 : 연속합 (0)	2020.08.21
[JAVA] 백준 1747번 : 소수&팰린드롬 (0)	2020.08.20
[JAVA] 백준 1541번 : 잃어버린 괄호 (0)	2020.08.20
[JAVA] 백준 2556번 : 별 찍기 - 14 (0)	2020.08.20

코드

실패 코드 : 입력 값을 +1 하면서 반복문을 돈다. 안쪽에선 소수, 팰린드롬을 체크하며 소수이면서 팰린드롬이면 출력 후 반복문 종료. 결과는 시간 초과

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int input = Integer.parseInt(br.readLine())-1;

		while(true) {
			boolean decimalCheck= false;
			boolean palindromeCheck = true;
			
			input++;
			
			for(int i=2;i<input;i++) {
				if(input%i==0) 
					break;
				if(i==input-1) 
					decimalCheck = true;					
			}
			
			int j=(int)(Math.log10(input)+1)-1;
			for(int i=0;i<(int)(Math.log10(input)+1)/2;i++) {
				if(!Character.toString(Integer.toString(input).charAt(i)).equals(Character.toString(Integer.toString(input).charAt(j)))) {
					palindromeCheck = false;
					break;
				}
			}
			
			
			if(decimalCheck && palindromeCheck) {
				bw.write(input + "\n");
				break;
			}
			
		}
		
		bw.flush();
		bw.close();
	}
}

성공 코드 : 소수와 팰린드롬 체크하는 메소드를 만들어서 boolean으로 넘겨 받아서 체크하게 했다.

소수 체크에서 Math.sqrt(number)를 통해 시간을 단축시켰다.

결과는 맞았습니다!!

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int input = Integer.parseInt(br.readLine());
		if(input==1) {
			System.out.println(2);
			System.exit(0);
		}

		while(true) {
					
			if(isDecimal(input) && isPalindrome(input)) {
				System.out.println(input);
				break;
			}			
			input++;
		}
	}
	
	static boolean isDecimal(int number) {
		for(int i=2;i<=(int)Math.sqrt(number);i++) {
			if(number%i==0) 
				return false;
		}
		return true;
	}
	
	
	static boolean isPalindrome(int number) {
		char [] integerToCharArray = String.valueOf(number).toCharArray();
		int length = integerToCharArray.length-1;
		for(int i=0;i<=integerToCharArray.length/2;i++) {
			if(integerToCharArray[i] != integerToCharArray[length--]) 
				return false;
		}
		return true;
	}
}

다른 사람의 코드 : 시간이 빠르게 나오길래 가지고 왔다.

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

public class Main {
	private static boolean[] prime_num;
	public static void main(String[]args)throws IOException
	{
		prime_num= new boolean[1004001];
		prime_num[1]=true;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		if(n <=7) {
			Eratosthenes(10);
			for(int i = n; i<=10;i++) {
				if(!prime_num[i]) {
					System.out.println(i);
					break;
				}
			}
			}
		else {			
			   Eratosthenes(1004000);
				for(int i = n; i<=1004000;i++) {
					if(!prime_num[i]&&isPalindrome(i)==true) {
						System.out.println(i);
						break;
					}
				}
			}
		}
	
	private static void Eratosthenes(int n) {
		for(int i = 2; i*i <= n; i++) {
			if(prime_num[i]==false) {
				for(int k = i*i; k<=n; k+=i)
					prime_num[k]=true;
			}
		}
	} 
	private static boolean isPalindrome(int num) {
		String s = Integer.toString(num);
		if(s.length()%2==0) { 
			int i = 0;
			int j = s.length()-1;
			while(i<j) {
				if(s.charAt(i)!=s.charAt(j))
					return false;
				i++;
				j--;
			}
		}
		else { //홀수일 경우 
			int i =0 ;
			int j = s.length()-1;
			while(i!=j) {
				if(s.charAt(i)!=s.charAt(j)) 
					return false;
				i++;
				j--;
			}
		}
		return true;
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1912번 : 연속합 (0)	2020.08.21
[JAVA] 백준 10942번 : 팰린드롬? (0)	2020.08.21
[JAVA] 백준 1541번 : 잃어버린 괄호 (0)	2020.08.20
[JAVA] 백준 2556번 : 별 찍기 - 14 (0)	2020.08.20
[JAVA] 백준 2877번 : 4와 7 (0)	2020.08.20

코드

성공 코드 : 괄호가 어디있던 첫번째 -기준으로 앞은 다 더해주고 뒤는 다 빼주면 최소값이 된다는 생각으로 풀었다.

결과는 맞았습니다!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String input = br.readLine();
		String[] minusSplit = input.split("-");
		int sum=0;
		
		for(int index=0;index<minusSplit.length;index++) {
			String[] number = minusSplit[index].split("[+]");
			for(int index2=0;index2<number.length;index2++) {
				if(index==0)
					sum+=Integer.parseInt(number[index2]);
				else
					sum-=Integer.parseInt(number[index2]);
			}
		}
		bw.write(sum + "\n");
		
		bw.flush();
		bw.close();
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 10942번 : 팰린드롬? (0)	2020.08.21
[JAVA] 백준 1747번 : 소수&팰린드롬 (0)	2020.08.20
[JAVA] 백준 2556번 : 별 찍기 - 14 (0)	2020.08.20
[JAVA] 백준 2877번 : 4와 7 (0)	2020.08.20
[JAVA] 백준 2750번 : 수 정렬하기 (0)	2020.08.19

코드

성공 코드 : 그냥 입력한 수의 꽉찬 정사각형 별찍기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				bw.write("*");
			}
			bw.write("\n");
		}
		
		bw.flush();
		bw.close();
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1747번 : 소수&팰린드롬 (0)	2020.08.20
[JAVA] 백준 1541번 : 잃어버린 괄호 (0)	2020.08.20
[JAVA] 백준 2877번 : 4와 7 (0)	2020.08.20
[JAVA] 백준 2750번 : 수 정렬하기 (0)	2020.08.19
[JAVA] 백준 1790번 : 수 이어 쓰기 2 (0)	2020.08.19

코드

실패 코드 : contains를 통해 해당 문자가 없으면 count를 해주며 count가 K랑 같아졌을 때, 출력 후 반복문을 빠져나오는 식으로 하였다. 결과는 메모리초과

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		int K = Integer.parseInt(br.readLine());
		
		int count = 0;
		int i=1;
		while(true) {
			if(!Integer.toString(i).contains("0")
					&& !Integer.toString(i).contains("1")
					&& !Integer.toString(i).contains("2")
					&& !Integer.toString(i).contains("3")
					&& !Integer.toString(i).contains("5")
					&& !Integer.toString(i).contains("6")
					&& !Integer.toString(i).contains("8")
					&& !Integer.toString(i).contains("9"))
				count++;
				
			if(count==K) {
				System.out.println(i);
				break;
			}
			i++;
		}
	}
}

성공 코드 : 4와 7로만 나타내는 K번째 수를 입력하면 된다. 여기서 4와 7를 0과 1로만 바꿔서 생각하면 2진수와 같다.

약간 다른점은 3일때 00이 아닌 10이 된다.

해결법은 입력한 수를 +1 한 뒤 2진수로 바꾸면 3일때 100이 된다.

여기서 맨 앞에 1을 제외시키면 00이 되어서 3일때 44로 정상적으로 바뀌게 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String s = Integer.toBinaryString(Integer.parseInt(br.readLine())+1).replace('0','4').replace('1', '7');
		for(int i=1;i<s.length();i++) 
			bw.write(s.charAt(i));
		
		bw.flush();
		bw.close();
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1541번 : 잃어버린 괄호 (0)	2020.08.20
[JAVA] 백준 2556번 : 별 찍기 - 14 (0)	2020.08.20
[JAVA] 백준 2750번 : 수 정렬하기 (0)	2020.08.19
[JAVA] 백준 1790번 : 수 이어 쓰기 2 (0)	2020.08.19
[JAVA] 백준 5567번 : 결혼식 (0)	2020.08.19

코드

앞의 인덱스의 수 보다 뒤의 인덱스의 수가 더 적으면 swap해주는 식으로 풀었다.

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int N = Integer.parseInt(br.readLine());
        
        int [] number = new int[N+1];
        for(int i=0;i<N;i++)
        	number[i] = Integer.parseInt(br.readLine());
        
        for(int i = 0;i<N;i++) {
        	for(int j=1;j<N;j++) {
                if(number[j] < number[j-1]) {
                    int temp = number[j];
                    number[j] = number[j-1];
                    number[j-1] = temp;
                }
        	}
        }
        
        for(int i=0;i<N;i++)
        	System.out.println(number[i]);
	}
}

Arrays.sort를 쓰면 더 빠르고 짧게 정렬할 수 있다.

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int N = Integer.parseInt(br.readLine());
        
        int [] number = new int[N];
        for(int i=0;i<N;i++)
        	number[i] = Integer.parseInt(br.readLine());
       
        Arrays.sort(number);
        
        for(int i=0;i<N;i++)
			System.out.println(number[i]);
		
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 2556번 : 별 찍기 - 14 (0)	2020.08.20
[JAVA] 백준 2877번 : 4와 7 (0)	2020.08.20
[JAVA] 백준 1790번 : 수 이어 쓰기 2 (0)	2020.08.19
[JAVA] 백준 5567번 : 결혼식 (0)	2020.08.19
[JAVA] 백준 1748번 : 수 이어 쓰기1 (0)	2020.08.19

선장 일지

algorithm

[JAVA] 백준 9935번 : 문자열 폭발

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1912번 : 연속합

'algorithm' 카테고리의 다른 글

[JAVA] 백준 10942번 : 팰린드롬?

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1747번 : 소수&팰린드롬

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1541번 : 잃어버린 괄호

'algorithm' 카테고리의 다른 글

[JAVA] 백준 2556번 : 별 찍기 - 14

'algorithm' 카테고리의 다른 글

[JAVA] 백준 2877번 : 4와 7

'algorithm' 카테고리의 다른 글

[JAVA] 백준 2750번 : 수 정렬하기

'algorithm' 카테고리의 다른 글

+ Recent posts

티스토리툴바