자바

[백준] 9012 - 괄호 (자바/Java) 스택 Stack 괄호 검사

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..

[SWEA] 1216 - 회문 2 (자바/Java)

처음에는 각 행과 열에서 0과 99에서 시작해서, 두 값이 같으면 start와 end를 1씩 감소 시키고, 아닌 경우에는 start와 end 중 하나만 감소시키며 검사하려고 하였는데, 재귀로 구현하였더니 case가 너무 많고 예외처리가 잘 안되어서 무한 루프가 일어났다. 두 값이 같지 않을 경우 start를 1 증가시키거나, end를 1 증가시키면서 값을 찾아야 하는데, 그 과정에서 최대 길이인 회문을 찾는 과정을 보장하지 못하였다. 그래서 이중 for문에서 값을 하나하나 돌며, 해당 index값을 중앙값으로 하는 최대 회문의 길이를 찾고, 그 중 가장 긴 회문의 길이를 반환하였다. 이 과정에서 회문의 길이가 홀수, 짝수인 경우가 있는데, 홀수인 경우는 해당 index에서 일정값만큼 빼고 더해주며 회문을..

[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합

N과 M은 순열, 조합, 중복순열, 중복조합을 연습할 수 있는 문제이다. 순열과 조합은 재귀를 사용하여 풀 수 있다. 1. 순열 순열에서 nPr은, N개의 수에서 가능한 r개의 수를, 순서대로 나열하는 것이다. 순열에는 순서가 존재하기 때문에 1 2 3과 3 2 1은 다른 경우로 취급한다. 이를 재귀와 dfs를 활용하여 풀면 다음과 같다. cnt는 dfs의 깊이를 의미한다. cnt가 M이 되면 M개의 순열이 완성되었다는 의미이므로 함수를 return 한다. 또한 순열은 중복을 허용하지 않기 때문에 순열에 포함되었는지 여부를 확인할 boolean check 배열이 필요하다. 배열의 처음부터 for문을 돌며 방문하지 않은 노드일 경우 check를 true로 바꾸고, 다시 깊이 cnt를 +1 한 다음, 재귀적..

[백준] 2527 - 직사각형 (자바/Java)

문제 2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다. 이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x

[SWEA] 1210 - Ladder (자바/Java)

사다리타기에 따라 정답으로 이어지는 시작점을 찾는 문제다. 정답에서부터 위로 올라가는 방식으로 구현하면 된다. 먼저 목적지의 row, col 좌표를 변수에 설정하고, 오른쪽이나 왼쪽 그리고 위로 올라가도록 구현한다. 이때 주의할 점은 위로 가는 것보다 오른쪽 왼쪽이 1인지를 먼저 검사해야 한다. 오른쪽, 왼쪽으로 가고 있다면 반대방향으로 돌아가서는 안된다. 이때 2를 고려하지 않아서 무한루프에 빠지는 문제가 발생했다. 그래서 dir 변수를 지정해줘서 오른쪽, 왼쪽으로 가는 경우는 반대방향이 아닐 경우에만 이동하도록 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_1210_Ladder { static int[][] ladder = ..

[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java)

주어진 N개의 수에서 가능한 두 수의 곱 중, 가장 큰 단조 증가 수를 찾는 문제이다. 먼저 가능한 두 수의 곱을 이중 for문으로 찾고, 그 수가 단조 증가하는지를 찾으면 된다. 단조 증가 여부를 찾기 위해 정수형 숫자를 String으로 바꿔주고, 각 자리수를 돌며 앞의 자리수가 뒤의 자리수보다 클 경우 false를 return하였다. 또한, 단조 증가하는 수가 없을 경우 -1을 출력하기 위해, result의 초기값을 -1로 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_6190_단조증가 { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..

[SWEA] 1954 - 달팽이 숫자 (자바/Java)

2차원 배열의 순회를 활용한 문제이다. while 문을 활용해서 해당 방향의 index를 채우고, array의 끝을 만나거나 이미 방문된 노드를 만났을 때는 방향을 바꾸어 주었다. 각 방향을 1~4로 두고 switch문으로 케이스를 정하였다. case 1: 오른쪽으로 이동: row는 그대로, col을 증가 case 2: 아래로 이동: col은 그대로, row를 증가 case 3: 왼쪽으로 이동: row는 그대로, col을 감소 case 4: 위로 이동: col은 그대로, row를 증가 그리고 1에서 더 나아갈 방향이 없으면 2로, 2에서 3으로 재귀적으로 snail함수를 수행하도록 하였다 그리고 함수를 실행하였을 때 이미 그 칸이 칠해져있다면, 모든 칸이 칠해진 경우이므로 return으로 종료조건을 주었..

[백준] 2567 - 색종이 2 (자바/Java)

문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 ..

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[백준] 2407 - 조합 (자바/Java) BigInteger 클래스

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 굳이 재귀로 팩토리얼을 구하지 않아도 간단하게 풀 수 있지만, 수의 범위가 커서 BigInteger 클래스를 사용해야 한다. package BOJ0809; import java.math.BigInteger; import java.util.Scanner; public class BOJ_2407_조합 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); BigInteger n = new BigInteger(Integer.toString(sc.nextInt())); BigInteger ..