[백준 - 2800] 골드5 - 괄호 제거 (문자열)

www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 1. 유형 부분집합, 스택 2. 풀이 1) 괄호를 아래와 같이 쌍별로 분류한다. ( ( ) ( ) ) 1 2 2 3 3 1 2) 부분집합 배열을 처음부터 탐색하면서 '(' 괄호가 나오면 선택, 비선택을 나누어 부분집합을 구한다 3. 코드 import java.io.*; import java.util.*; public class Main { static String str; sta..

→2020.10.25

알고리즘/백준

[백준 - 5052] 골드4 - 전화번호 목록(문자열)

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. 유형 문자열 2. 풀이법 문자열 길이가 작은 순으로 정렬한다 set을 이용해서 들어있는 문자를 탐색한다 3. 코드 package 문자열; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Com..

→2020.10.25

알고리즘/백준

[백준 - 9935] 골드4 - 문자열 폭발

www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 1. 유형 stack, 문자열 2. 풀이법 12ab112ab2ab 12ab 이 값이 입력값으로 주어진다면, 폭탄의 마지막 문자가 b 니깐, b를 만났을때만 폭탄 길이만큼 앞을 탐색해 주는 식으로 풀었다. 그럼에도 불구하고, 계속 시간초과가 났는데 StringBuilder를 쓰니깐 해결되었다. 3. 코드 package 문자열; import java.io.BufferedReader; import ja..

→2020.10.25

알고리즘/백준

[백준 - 11000] 골드5 - 강의실 배정

www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 1. 유형 그리디, 커스텀 정렬 2. 풀이 시작 시간 기준 오르차순 정렬을 한다. 우선순위큐에 처음 값을 넣고나서 끝나는 시간보다 현재 시작시간이 같거나 크면, 큐에 넣어주는 식으로 고친다. 3. 풀이 package 그리디; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; public class back_11..

→2020.10.22

알고리즘/백준

[백준 - 2812] 골드5 -크게 만들기

www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 유형 그리디 2. 풀이 스텍에 순차적으로 넣으면서 시작한다. peek값보다 지금 넣는 값이 더 크다면 더 큰 값이 나올 때까지 계속 pop을 한다 3. 코드 package 그리디; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Stack; import java.util.StringTok..

→2020.10.20

알고리즘/백준

[백준 - 17615] 실버1 - 볼 모으기

www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주�� www.acmicpc.net 1. 유형 그리디 2. 풀이 RRBRBB가 있을때, 맨 뒤에서 시작하는 경우와 맨 앞에서 시작하는 경우 두가지로 나눠서 생각한다. RR부터 시작하면 뒤에R과 B의 갯수를 세어준다. 3과 1이 나오고, 그중 최소값을 저장 BB부터 탐색 시작하면 뒤에 R이 3개 B가 1개 나온다. 그중 최소값을 저장 그 두개를 비교한다. 3. 코드 package 그리디; import java.uti..

→2020.10.19

알고리즘/백준

[백준 - 16235] 골드4 - 나무재테크

www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 로직이 쉽게 생각나서 별로 어렵지 않은 문제인줄 알았다. 하지만 시간초과 때문에 많이 고생한 문제다. 결국 지인 찬스 remove를 쓰면 안된다는걸 알게됐다. ArrayList에서 remove로 제거하고, 땡겨오는 과정 때문에서 n번의 연산이 생겨서 쓰면 안된다. 처음 짠 로직에서 remove만 빼줬더니 시간초과를 해결했다. 1. 유형 시뮬 2. 풀이 나무 클래스를 만들어서 4계절을 탐색해주면 ..

→2020.10.19

알고리즘/백준

[백준 - 16236] 골드5 - 아기상어

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 1. 유형 bfs, 시뮬레이션, 우선순위큐 2. 풀이 bfs돌릴때마다 잡은 물고기를 우선순위큐에 넣는다. 그러고나서 bfs가 끝난 후, poll()을 한 값은 가장 가까우면서, 위에있고, 왼쪽에 있는 물고기이다 상어(9)를 찾고나서 맵을 0으로 갱신해주는걸 잊지말자. 3. 코드 package 구현.삼성역태; import java.util.LinkedList; import java.util.Priori..

→2020.10.16

알고리즘/백준

[백준 - 17143] 골드2 - 낚시왕

www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 1. 유형 시뮬레이션, 우선순위 정렬, 깊은 복사 2. 풀이 크기순으로 내림차순 정렬 하나씩 탐색하면서 시뮬레이션 돌린다 처음 풀이는 시간초과가 났다. 싸이클을 생각해주지 않아서 이다. for (int i = 0; i < sharks.length; i++) { if(sharks[i].d

→2020.10.15

알고리즘/백준

[백준 - 17140 ] 골드4 이차원 배열과 연산(시뮬)

www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 1. 유형 시뮬레이션 2. 풀이 리스트에 관련 정보를 다 집어 넣고 우선순위에 맞게 정렬해 주는 것이 중요하다. 3. 코드 package 구현.삼성역태; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class back_17140이차원배열과_연산 { static class Pair i..

→2020.10.14

알고리즘/백준

[백준 - 19237] 골드3 - 어른 상어

www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이시간 : 2시간 50분 1. 유형 시뮬레이션, 깊은복사, 탐색 2. 풀이 한번에 이동한다는 말을 집중해야한다. 이런 문제는 임시 배열을 만들고, 임시배열 안에서 값을 수정해야한다. 그리고 탐색을 마친다음 원래 배열에 복사하는 식으로 풀이를 해야한다. 3. 코드 package 구현.삼성역태; import java.util.Scanner; public class ba..

→2020.10.14

알고리즘/백준

[백준 - 19236] 골드3 - 청소년 상어

1. 유형 시뮬레이션, 재귀 2. 풀이 상어가 이동할 수 있는 곳이 여러곳이기 때문에 dfs를 사용해야 한다. 이동 할때마다 새로운 맵이 필요해서 깊은 복사를 해야한다. 3. 코드 package 구현.삼성역태; import java.util.Scanner; public class back_청소년상어 { static int ans=0; static int dr[] = {-1,-1,0,1,1,1,0,-1}; static int dc[] = {0,-1,-1,-1,0,1,1,1,}; static class Pair{ int r,c,d; public Pair(int r,int c,int d) { this.r=r; this.c=c; this.d=d; } } public static void main(String[]..

→2020.10.13

알고리즘/백준

[백준 - 4889] 실버1 - 안정적인 문자열(그리디)

www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우� www.acmicpc.net 1. 유형 그리디 2. 풀이 스택을 이용한 그리디 문제이다. '{'이 나오면 바로 push를 한다. '}' 이 나올때마다 스택이 비어있지 않으면 pop을 해주고 비어있으면 push를 해준다. 맨 처음에 '}' 이 나오면 '{'으로 바꿔주는 것이 핵심이다. 3. 코드 package 문자열; import java.util.Scanner; import java.util.Stack; public class bac..

→2020.10.09

알고리즘/백준

[백준 - 16938] 골드4 캠프 준비 (조합)

www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 1. 유형 조합 2. 풀이 조합 베이스 코드에다가 기저조건을 요구사항대로 만들면 된다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class back_16938캠프준비 { static int N,L,R,X,inp[], sel[], answer=0; public static void main(String[] args) t..

→2020.10.04

알고리즘/백준

[백준 - 1946] 실버1 신입 사원 (그리디)

www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 1. 유형 그리디 2. 풀이 문제를 이해하는데 오래 걸렸다. 서류 순으로 오름차순 정렬한다. 그 다음 면접 성적 순으로 우선순위 큐에 넣는다. 그러면 서류 성적은 더 낮지만 면접 성적은 더 높은 사람이 들어올 수 있다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

→2020.10.03

알고리즘/백준

[백준 - 2531] 실버1 회전 초밥 (투포인터)

www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 1. 유형 투 포인터 2. 풀이 이중 for문을 쓰면 시간 초과가 나기 때문에, 슬라이딩 윈도우를 써야한다 3. 코드 import java.util.Scanner; public class back_2531회전초밥 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc..

→2020.10.03

알고리즘/백준

[백준 - 3274] 실버4 두 수의합 (투포인터)

www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1. 유형 두 포인터 2. 풀이법 단순히 이중for문을 사용하면 시간 초과가 난다 그렇기 때문에 정렬후, 이분탐색을 사용해야한다 3. 코드 import java.util.Arrays; import java.util.Scanner; public class back_3273두수의합 { public static void main(String[] args) { S..

→2020.10.03

알고리즘/백준

[백준 - 17135] 골드4 캐슬디팬스 (구현)

www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 유형 조합, bfs, 시뮬레이션 2. 풀이 조합을 이용해서 궁수의 위치를 정해준다. 궁수의 위치마다 bfs를 돌려준다. 적을 찾았으면 동시에 적을 죽여야한다. 3. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class back_17135캐슬디펜스 { static int M,N,map[][], D, an..

→2020.10.02

알고리즘/백준

[백준 - 11497] 실버2 통나무 건너뛰기

www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 1. 유형 그리디 2. 풀이 입력값을 정렬한 후에 아래 그림처럼 나올 수 있도록 +2만큼 건너 뛰면서 탐색한다. 3. 코드 import java.util.Arrays; import java.util.Scanner; public class back_11497통나무건너뛰기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in);..

→2020.09.30

알고리즘/백준

[백준 - 19539] 실버1 사과나무 (그리디)

www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 1. 유형 그리디 2. 풀이법 사과나무 크기의 합이 3의 배수이다 홀수의 갯수가 전체합/3보다 작아야한다. 예를 들어 {1 2 1 2}는 가능하다. 하지만 {3 1 1 1}는 불가능하다. 한 턴에 물뿌리게를 다 써야하니깐.... 그래서 두번째 조건이 들어가야 한다 3. 코드 import java.util.Scanner; public class back_19539사과나무 { public static void main(String[] args) { Scann..

→2020.09.30

티스토리툴바