본문 바로가기

분류 전체보기

 (56)
[Baekjoon] 백준 11536번: 줄 세우기 (JAVA) 문제 11536 11536번: 줄 세우기 이름이 증가하는 순으로 나타나면 INCREASING, 감소하는 순이면 DECREASING을 한 줄에 출력한다. 만약 위의 두 경우가 아니라면 NEITHER를 출력한다. www.acmicpc.net [ 문제 풀이 ] 입력받은 문자열이 내림차순인지 오름차순인지, 아니면 내림차순도 오름차순도 아닌 것인지 체크하는 문제입니다. 먼저, 입력받은 문자열을 String[] 배열에 저장하고, 0번째 인덱스와 1번째 인덱스를 확인해서 오름차순인지 내림차순인지 확인합니다. isIncrease 라는 boolean 타입의 변수를 생성하여 오름차순이면 true, 내림차순이면 false로 저장합니다. 이후 1번째 인덱스부터 (String[] 배열의 길이 - 1) 만큼 순회하며 정렬 기준이..
[Baekjoon] 백준 2992번: 크면서 작은 수 (JAVA) 문제 2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net [ 문제 풀이 ] 순열 문제로, DFS를 활용하면 됩니다. depth 매개변수를 통해서 숫자가 모두 조합되었을 때 즉, depth가 X의 길이와 같아졌을 때, 정수 X보다 크고 현재 min 값보다 작으면 min을 현재 조합된 숫자로 업데이트해줍니다. X보다 큰 수 중 작은 값을 min이라고 하고, 초기값은 Integer.MAX_VALUE로 초기화해줍니다. [ 코드 ] import java.io.*; public class Main..
[Baekjoon] 백준 17413번: 단어 뒤집기 2 (JAVA) 문제 17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net [ 문제 풀이 ] '' 안에 있는 문자열은 그대로 두고, '' 밖에 있는 문자열들만 뒤집어서 출력해야 하는 문제입니다. 일단 문자열을 뒤집어서 출력하기 위해서는 FILO(First In Last Out) 성격인 Stack을 이용해야 합니다. 그러면 '' 은 어떻게 해야 할까요? 일단 '' 는 쌍을 이루기 때문에 '>' 만 신경 써주면 됩니다. 문자열을 순회하면서 '>' 문자를 만났을 때, flag를 false로 바꾸..
[Baekjoon] 백준 5052번: 전화번호 목록 (JAVA) 백준 5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net [ 문제 풀이 ] 프로그래머스에도 있는 문제로, 2가지 방법으로 풀 수 있습니다. 먼저 HashSet을 활용하여 String 클래스에 있는 substring()을 이용하여 풀어보겠습니다. HashSet에 전화번호를 저장하고, String[] 에도 저장하여 저장한 번호들을 하나씩 순회하며 0번째 인덱스부터 문자열을 잘라가며 잘린 앞부분의 문자열과 같은 문자열이 있는지 확인하면 됩니다. String[] phonesArr = ne..
[Baekjoon] 백준 11656번: 접미사 배열 (JAVA) 문제 11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net [ 문제 풀이 ] 문자열을 앞에서부터 하나씩 잘라서 뒷부분을 ArrayList에 저장한 후, 정렬해주면 됩니다. String 클래스의 substring()을 활용하여 인덱스를 매개변수로 해서 차례대로 접미사들을 구합니다. Collections.sort()로 ArrayList를 정렬해준 후, 출력해줍니다. ArrayList 대신, String[]을 활용하여 배열에 저장해주는 방법도 있습니다. 이 경우에는 정렬할 때 Arrays.sort()을 사용하면 됩니다. [ 코드 ] 1) ArrayList 사용 import java.io.*..
[Baekjoon] 백준 9935번: 문자열 폭발 (Java) 문제 9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [ 문제 풀이 ] N의 길이가 1,000,000이므로 시간복잡도를 고려해야 합니다. O(N)의 시간복잡도를 가질 수 있도록 해야 하기 때문에 replaceAll()과 같은 함수는 사용할 수 없습니다. 문자열의 길이만큼 처음부터 순회하며 Stack에 하나씩 넣은 다음, 폭발 문자열의 길이보다 클 때 폭발 문자열의 길이만큼 반복하여 폭발 문자열과 같은 것이 있는지 확인합니다. 없을 경우 flag를 false로 바꾸고, 반복문을 break..
[Baekjoon] 백준 9251번: LCS (JAVA) 문제 9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [ 문제 풀이 ] LCS는 DP를 활용하여 풀 수 있습니다. DP의 가장 큰 특징은 DP 배열의 값들이 모두 답이어야 한다는 것입니다. 즉, 미리 구해둔 답을 이용해서 다음에 올 답을 계산하는 것입니다. 이 문제에서 각 문자열의 길이를 구하여 dp[][] 이차원 배열을 만들면, 아래 그림과 같습니다. 위의 2차원 배열을 순회하면서 각 위치에서 문자를 비교하여 최대로 겹치는 순열을 찾아 개수를 넣어주면 됩..
[Baekjoon] 백준 1316번: 그룹 단어 체커 (JAVA) 문제 1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net [ 문제 풀이 ] 주어진 문자열을 한 단어씩 순회하면서 연속해서 나오는 문자들을 확인합니다. 연속해서 나온 문자들 중에 한 문자라도 떨어져서 나타나면 그룹 단어가 아닙니다. kin의 경우 k, i, n이 연속해서 나타나므로 그룹단어입니다. 이를 고려해보았을 때, 다음과 같이 생각할 수 있습니다. 1. 문자열을 순회하면서 연속으로 나오는 문자들을 DFS 탐색을 통해 확인해줍니다. 2. HashSet을 이용하여 해당 문..

티스토리툴바