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..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 DFS를 사용하여 스도쿠의 빈 칸에 모든 수를 집어넣고 각 경우마다 스도쿠가 될 수 있는지 체크한다. 로직 1. 스도쿠의 빈 칸 좌표를 ArrayList points에 넣는다. 2. sudoku(idx:0)을 호출한다. 이 때 idx는 points의 인덱스다. 3. points에서 좌표를 꺼내고, for문으로 1~9까지 해당 좌표에 들어갈 수 있는지 check() 함수를 통해 체크한다. 들어..

https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 풀이 map을 사용하여 (확장자 이름, 파일 개수)를 저장한다. 또한 확장자는 사전순을 출력해야 하므로 확장자를 정렬하기 위해, 확장자 이름은 따로 ArrayList에 저장한 다음 이후 정답을 출력할 때 사용한다. 로직 1. HashMap map과 ArrayList list를 선언한다. 2. 파일을 입력받고 파일의 확장자 이름을 뽑아낸다. 3. 확장자 이름이 map의 키로 존재한다면, 해당 엔트리의 값을..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 말이 지날 수 있는 최대의 칸 수를 구하기 위해, DFS를 사용해서 모든 경우를 탐색해야 한다. 이 때 같은 알파벳이 적힌 칸을 두 번 지날 수 없으므로, 중복되는 알파벳이 있는지 체크하기 위해 map을 사용한다. 칸을 이동할 때마다 그 칸의 알파벳을 map의 key로 저장하고, 다음 칸으로 이동하기 전 map.containsKey() 메서드를 호출하여 다음 칸의 알파벳이 map에 있..

https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 풀이 처음 예제 출력을 보면, 1은 별 하나가 찍혀있고, 2는 1의 출력에서 위아래 1줄을 띄고 감싸는 것 같은 모양이다. 별이 찍히는 규칙을 살펴보자면, 일단 가운데 줄을 기준으로 위아래가 대칭이다. 홀수 번째 줄의 경우, 맨 윗줄은 모두 별로 채워져 있고, 그 다음 홀수 번째줄부터 계속 양쪽 사이드에서 별이 1개씩 줄어들고 있다. 짝수 번째 줄의 경우, 처음 줄(위에서 2번째)은 양 끝에 별이 1개씩 있고, 그 다음 짝수 번째줄부터 계속 양쪽 사이드에서 별이 1개씩 추가되고 있다. 위와 같은 규칙을 코드로 구현하면 아래와 ..