https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 스택을 사용하고, 입력받는 숫자를 총 3가지 경우로 나누어 처리한다. 1) 현재 top에 있는 숫자가 입력받은 숫자보다 작으면 그 숫자까지 push하고, 한 번만 pop한다. ex) 4 1 push, 2 push, 3 push, 4 push, 4 pop 2) 현재 top에 있는 숫자가 입력받은 숫자와 같으면 한..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 나의 풀이 : ArrayList 사용 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)); StringTo..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 대표적인 스택 문제다. '(' 왼쪽 괄호를 만나면 스택에 push하고, ')' 오른쪽 괄호를 만나면 스택을 pop한다. 이 때 ')' 오른쪽 괄호를 만나면 스택을 pop했는데 pop한 문자열이 ( 가 아니라면 올바른 괄호 문자열이 될 수 없다. 로직 1. n을 입력받는다. 2. n번 동안 괄호 문자열을 입력받고 blankStr(str)을 호출하여 올바른 괄호 문..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산해야 한다. 비가 내려서 잠기는 높이의 경우의 수마다 BFS를 수행해서 안전한 영역의 최대 개수를 구한다. 로직 1. n을 입력받는다. 2. nxn 크기의 int형 배열 arr을 선언한다. 3. 지역의 높이 정보를 입력받고 arr에 저장한다. 이 때 가장 높은 지점의 높이를 max값에 저장한다. 4. 아무 지점도 잠기지 않으면 안전 영역의 개..

https://www.acmicpc.net/problem/5212 풀이 r x c 크기의 지도를 입력받고, 인접한 4방향 중 3방향 이상이 바다라면 그 위치는 바다로 바꿔야 한다. 그 후 지도의 크기를 모든 섬을 포함하는 가장 작은 직사각형이 되도록 해야 한다. 일단 지도의 정보를 담는 배열과 50년 후 지도의 정보를 담는 배열을 따로 생성하여 50년 후 지도의 정보를 구하고, 그 후 변경된 지도의 크기를 구해야 한다. 로직 1. r과 c를 입력받는다. 2. String[] sea = new String[r]; 지도의 정보를 입력받는다. 3. char[][] ans = new char[r][c]; ans는 50년 후 지도의 정보를 담는다. 4. ra, rb, ca, cb는 각각 새로운 지도의 행 번호(첫..

https://www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net 풀이 일단 입력한 알파벳 글자가 한글 자음 부분인지 모음 부분인지 구분해야 하고, 각 알파벳마다 위치 정보를 저장해야 한다. 각 글자마다의 위치 정보를 찾는 것을 용이하게 하기 위해 Map을 사용해서 키로 알파벳 글자를 저장하고, 값으로 해당하는 알파벳 글자의 위치 정보를 저장한다. 위치 정보를 저장하는 클래스 Position을 생성하고, Position 클래스는 int x, y, bo..

https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 풀이 처음에 문제를 보았을 때는 map을 사용해서 (번호, 추천수) 와 같은 형태로 저장하려고 했다. 하지만 문제의 3번에서 "비어있는 사진틀이 없는 경우, 추천수가 가장 적고 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다."고 나와 있다. 즉, 정렬 기준이 추천 수, 최신에 게시되었는가 2가지가 되기 때문에,..

https://www.acmicpc.net/problem/22858 22858번: 원상 복구 (small) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 위 방식을 그대로 K번 섞은 카드의 정보와 D의 정보를 알고 있다고 할 때, 원래 카드는 어떤 배치를 이루고 있었는지 구해보자. 입력 첫번째 줄에는 카드의 개수 N과 카드를 섞은 횟수인 K가 공백으로 구분되어 주어진다. 두번째 줄에는 K번 카드를 섞은 후 카드의 배치를 의미하는 Si가 공백으로 구분되어 ..

https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 풀이 태그 밖에 있는 단어는 공백을 기준으로 구분하며 뒤집어야 한다. 태그 안에 있는 단어는 뒤집으면 안되고, 공백이 있어도 무시해야 한다. 로직 1. 단어를 뒤집기 위해 사용할 StringBuilder 타입 변수 sb를 선언하고 초기화한다. 2. 태그 안인지 밖인 지 구분할 boolean 타입 변수 flag를 선언하고 true로 초기화한다. 3. for문을 사용하..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 구해야 하므로, BFS를 사용한다. 숫자의 중복 여부를 체크하기 위해 Map을 사용하고, 각 숫자마다 명령어 나열을 저장해야 하므로 Map에 (숫자, 명령어 나열)을 저장한다. 큐에는 숫자를 저장한다. 로직 (시간초과) 1. BFS를 수행할 dslr함수에서 int형 숫자를 저장하는 큐, (숫자, 명령어 나열)을 저장하는 H..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 처음에는 DFS를 사용하여 S층에서 G층으로 갈 수 있는 모든 경우를 구하고, 그 경우에서 최솟값을 구하려고 하였다. 하지만 시간초과가 떴다. 그래서 구글링을 한 결과 BFS와 방문배열를 사용하여 문제를 풀었다. 층의 방문 여부를 저장하는 방문 배열을 사용하지 않는다면 메모리 초과가 뜬다. 로직 1. BFS를 사용하여 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 구한다. 이 때 한 번 ..

https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 풀이 처음에는 Integer 메서드를 사용하여 8진수 문자열 -> int -> 2진수 문자열 순서로 변환하여 문제를 풀 생각이었다. 하지만 입력으로 주어지는 수의 길이는 333,334 이기 때문에 숫자의 범위가 int형을 넘어서는 문제가 발생한다. long으로 타입을 바꿔줘도 런타임 에러(NumberFormat)가 발생한다. 이를 해결하기 위해 처음 String으로 입력받고 for문을 사용해 글자마다 글자 -> int -> 2진수 문자열로 바꾸는 로직을 작성한다. 8진수를 2진수로 변환하는 방법 -> 8..