본문 바로가기

구현10

[백준] 2002 추월 (Java) [2002 추월] 난이도: 실버1 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 문제 입력 출력 [아이디어] 추월했다는 건 들어갈 때의 위치보다 나갈 때 위치가 빠르다는 것이다. 따라서 위치를 확인해주면 된다. [JAVA 코드] import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static Str.. 2022. 6. 23.
[백준] 14503 로봇 청소기 (Java) [14503 로봇 청소기] 난이도: 골드5 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 입력 출력 [아이디어] 문제에 써있는 설명대로 코드를 작성해주면 되는 시뮬레이션 문제이다. 조심해야되는 부분은 후진할 때는 청소를 한 장소여도 후진할 수 있다. 그리고 후진한 후 청소를 다시 해주면 안된다는 것이다. 청소하지 않은 장소인 경우에만 청소해주자. [JAVA 코드] package bj.g5; import java.io.*; import java.util.*; public class BJ_G5_14503_.. 2022. 6. 6.
[백준] 17779 게리맨더링2 (Java) [17779 게리맨더링2] 난이도: 골드4 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제 입력 출력 [아이디어] 가능한 모든 경우들을 완탐으로 풀었다. 1, 2, 3, 4번 선거구역을 나눠주고 해당되지 않는 구역을 5번 구역으로 판단해서 값을 구해줬다. 여기서 선거구역을 나눌 때 경계선의 꼭지점들을 기준으로 판단해주었다. 예를 들면, x = 4, y = 3, d1 = 1, d2 = 1 의 경우 1번 선거구역을 찾기 위해 (x, y) => (4, 3) 을 기준으로 위에 있는 칸들을 먼저 찾아주고 r이 3이하인 .. 2022. 6. 3.
[백준] 18405 경쟁적 전염 (Java) [18405 경쟁적 전염] 난이도: 골드5 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 입력 출력 [아이디어] 사방으로 바이러스가 퍼져나가므로 BFS를 활용하면 된다. 이 때, 매 초다마 번호가 낮은 종류의 바이러스부터 증식하므로 단순 Queue를 사용하면 구현이 조금 복잡해질 수 있다. 따라서 나는 우선순위 큐를 사용해주었다. Point 클래스를 생성하여 바이러스의 위치, 종류, 걸린시간을 관리해주었고, 시간과 바이러스 종류로 우선순위를 정해주었다. 그 후는 일반 BFS.. 2022. 5. 5.
[백준] 5430 AC (Java) [5430 AC] 난이도: 골드5 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 입력 출력 [아이디어] 이 문제는 두가지 방법으로 풀어볼 수 있다. R이 나올 때마다 정말 배열을 뒤집으면 시간초과가 난다. 하나는 덱을 사용하는 방법이고, 다른 하나는 투포인터를 사용하는 방법이다. 덱을 사용하는 것은 단순하게 앞에서 삭제할지 뒤에서 삭제할지를 저장하는 변수를 통해 덱의 내장함수인 removeFirst(), removeLast(), pollFirst(), pollLast() 를 사용해주었다. 투포인터를 사용할 때는 st와 end 위치를 저장하는 변수와 삭제 위치.. 2022. 5. 2.
[백준] 14890 경사로 (Java) [14890 경사로] 난이도: 골드3 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 입력 출력 [아이디어] 단순한 구현 문제이다. 문제 설명대로 코드를 짜주면 되는데 경사로가 겹치게 놓이면 안된다는 것이 가장 까다롭다. 따라서 나는 경사로가 이미 놔져있는가를 체크하는 배열을 따로 써줬다. 그리고 열방향 탐색의 함수를 따로 만들지 않고, 열을 행으로 변환하여 하나의 함수를 재활용 하였다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import jav.. 2022. 4. 26.
[백준] 2636 치즈 (Java) [2636 치즈] 난이도: 골드4 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 입력 출력 [아이디어] 이 문제는 BFS를 사용하면 된다고 바로 감이 올 것이다. 하지만 어려운 부분은 어떻게 외부 공기가 닿는 부분만 체크를 하는가이다. 문제를 해결하는 방법은 거꾸로 생각하기이다. 보통 치즈를 너비 우선 탐색하는 방법을 사용하지만, 이 문제는 바깥의 공기를 너비 우선 탐색하여 체크해주는 것이 포인트이다. 먼저 바깥의 공기를 너비 우선 탐색해서 어느 부분이 공기인지 체크해준다. 그 후 전체를 탐색하면서 치즈인 경우.. 2022. 4. 17.
[백준] 14891 톱니바퀴 (Java) [14891 톱니바퀴] 난이도: 골드5 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 입력 출력 [아이디어] 톱니바퀴를 돌릴 때 재귀를 활용하였다. 왼쪽 톱니바퀴가 회전하는지를 판단할 때는 아래와 같이 코드를 작성하였다. // 왼쪽 톱니바퀴 회전 여부 판단 if(gear > 1 && !visited[gear - 1] && gears[gear][6] != gears[gear - 1][2]) { // 맞닿은 톱니의 극이 다르다면 rotate(gear - 1, dir * -1); // 왼쪽 톱니바퀴를 d.. 2022. 4. 17.
[백준] 2239 스도쿠 (Java) [2239 스도쿠] 난이도: 골드4 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 입력 출력 [아이디어] 백트래킹을 사용하여 가지치기를 하였다. 처음에는 빈칸에 하나의 수를 결정할 때마다 for문을 통하여 가능한지의 여부를 찾았다. 시간초과가 뜨지 않았지만 다른 사람들이 시간을 훨씬 덜 쓰길래 찾아보았더니 for문을 사용하여 가능하지를 따지지 않고 따로 배열을 생성하여 체크하는 방법을 알게되었다. i행에 쓰인 숫자를 체크하는 배열 -> row[][] i열에 쓰인 숫자를 체크하는 배열 -> col[.. 2022. 4. 6.
[백준] 14500 테트로미노 (Java) [14500 테트로미노] 난이도: 골드5 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 입력 출력 [아이디어] 'ㅜ' 모양을 제외하면 크기가 4인 DFS 모양이 된다. 'ㅜ' 모양은 모든 모양을 생각해준다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static Buff.. 2022. 3. 30.

티스토리툴바