알고리즘

백준 9613번 GCD 합 [ Java ]

9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net gcd의 합이 정수의 범위를 넘어갈 수 있으므로 long 자료형으로 선언해줘야 합니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String..

백준 6588번 골드바흐의 추측 [ Java ]

6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 에라토스테네스의 체를 사용하였습니다. import java.io.*; import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); static boolean isPrime[] = new boolean[1000001]; public static void main(String[] args) throws IOException { BufferedRead..

백준 10824번 네 수 [ Java ]

10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net int를 사용하면 범위가 초과 됩니다. 최대값 20000002000000(2조 20만) int 최댓값 약 21억 long 약 900경 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input[] = br.readLine().split(" "); System.out.print(Long..

백준 11655번 ROT13 [ Java ]

11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); char str[] = br.readLine().toCharArray(); for (char ch : str) { if ('a'

백준 2743번 단어 길이 재기 [ Java ]

2743번: 단어 길이 재기 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. www.acmicpc.net strlen이 생각나는 문제입니다. import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.print(br.readLine().length()); } }

백준 10820번 문자열 분석 [ Java ]

10820번: 문자열 분석 문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = ""; while ((input = br.readLine()) != null) { char s..

백준 1918번 후위 표기식 [ Java ]

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 머릿속으로 스택을 사용해서 푸는과정이 아직 구체적으로 그려지지 않는것 같습니다. 연습이 더 필요할 것 같네요. import java.io.*; import java.util.*; public class Main { static int priority(char ch) { switch (ch) { case '(': return 0; case '+': case '-': return 1; default: return 2; } } public static voi..

백준 1935번 후위 표기식2 [ Java ]

1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위 표기 연산을 해주는 코드를 작성했다. 연산자를 만나면 스택에 숫자를 두 개 꺼내 연산해주고 다시 집어 넣는다. 위 과정을 반복하고 마지막으로 스택에 남아있는 수를 꺼내 포맷에 맞게 출력한다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Stack stack = new Stack();..

백준 17299번 오등큰수 [ Java ]

17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수랑 똑같은 방식에 빈도 비교하는 배열만 추가하였습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Stack stack = new Stack(); StringBuilder sb = new StringBuilder(); BufferedReader br = new BufferedReader(new InputS..

백준 17298번 오큰수 [ Java ]

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오른쪽에 있는 큰 수 중 가장 왼쪽에 수를 찾는건데 가장 먼저 떠오르는 방법은 현재 인덱스부터 오른쪽을 전부 검사하는 것이다. 하지만 이렇게 하면 O(n^2)의 시간복잡도가 나와서 시간초과가 나오게 된다. 스택을 이용하면 O(n)으로 풀 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Stack stack ..