www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 자신의 번호가 들어갈 수 있는 배열을 하나 만든다(0 초기화) 그리디 탐색으로 보고있는 자리가 비워져있다면 나보다 큰 사람이 들어갈 곳으로 판단해서 cnt를 1감소시킨다. cnt가 0이라 나보다 큰 애는 없어도 자리가 비워져있지 않다면 나보다 작은 친구가 들어간 곳이다. 다음 공간을 본다. cnt도 0이고 현재 공간이 0이면 내가 들어갈 자리이다. import java.util.Scanner; publi..
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제자체는 어렵지 않은데 시간초과가 있어서 최적화해줘야한다. --- 풀이 r길이는 2인데 속도가 1000이라면 엄청나게 왔다갔다해야된다. 같은 위치에 있을 경우의 규칙을 찾아야된다. 주의할 점은 같은 위치에 있더라도 방향이 반대인 것은 같은 경우가 아니다! 예를 들면 C=5이고 현재 열 번호 1에 있고 우로 움직이는 상어가 있다고 하자 열 번호 1 2 3 4 5 인 경우 S=1이면 오른쪽으로..
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 추가 설명에 비에 모두 잠기지 않을 가능성이 있다고 했다. (비가 안오는 경우가 있다. 높이 모두 1인 곳의 기준) 최대 지역의 높이 = 비의 최대 강수량으로 놓고 모든 비의 높이에 따라서 bfs를 돌려준다. 비의 높이보다 낮은 곳은 모두 0으로 만든 후 여전히 양수인 (물에 잠기지 않은 곳)의 영역을 구해준다. import java.util.LinkedList; import java.util.Queue; import..
www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net subset을 사용해서 처리해줬다. 길이가 1이상이라는 조건이 있다 import java.util.Scanner; public class Main { static int n,s; static int[] arr; static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in)..
프로그래머스에서 java를 쓰니 매우 어색하다 네이버 코테 대비로 연습 중 ㅠ javascript 쓸 것 같지만 문자열 처리 나오면 javascript로 해야지 -- 풀이 우선순위 큐에 모든 음식을 넣는다. 음식을 모두 섞는데 만약 가장 작은 수가 K 이상이면 조건을 만족하므로 break 아니면 섞는다. 만약 음식이 1개가 남으면 섞지 못하므로 break해주고 마지막 1개 음식이 K를 넘는지 확인한다. 아니면 최종까지 불가능한 것이므로 -1을 리턴해준다. import java.util.*; class Solution { public int solution(int[] s, int K) { int answer = 0; PriorityQueue pq=new PriorityQueue(); for(int i=0;..
www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 중간 중간에 조건들을 처리해줘야 할 것이 많다. 디버깅이 안되서 아예 다시 풀었다. 도착지, 출발지 정보를 다 저장하고 taxi클래스를 또 따로 만들어줬다. 한 사람의 도착지 = 다음 승객의 출발지이거나 초기 택시 출발지 = 이미 승객이 거기 서있음 의 경우로 택시 위치의 승객은 또 따로 처리해줘야 된다. 각 승객은 (출발지 != 도착지) 정보를 가졌지만 모든 승객이 같은..
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net subset으로 집합을 나눈다. vis[번호]=true => a집합, false면 b집합 만약 리스트 두 개를 만들어서 각각 집어넣는다. 리스트 하나라도 길이가 0이다 => 나머지 몰빵 => 집합 2개가 안됨 => return 리스트 두 개의 길이를 합쳤는데 n이 안됨 => 집합이 3개 이상이라는 뜻 => return 그 다음에는 한 집합 내에서 bfs로 인접리스트를 돌리며 한 집합의 모든 원소가 연결되는 지 확인한 후 두 집합 합..
www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 청소년 상어를 풀고나서 이 문제를 푸니 dfs가 익숙해서 dfs로 경우를 탐색하다가 메모리 초과가 났다. 가끔 bfs로만 되거나 dfs만 되는 문제들이 있어서 헷갈리는데 최단 시간 (같은 위치 구간에서 동시에 탐색할 때)는 bfs이고 모든 경우의 수를 다 돌아봐야하는 경우 (청소년 상어처럼 먹는 물고기 번호가 가장 큰것을 구하는 것)은 dfs인 것 같다. 물이 차오를 지역도 못간다는 것은 즉, 물이 찬 것과 같다라는 뜻이라..
www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 대각선 45도, -45도로 배열을 돌리는 문제. 주 대각선들 외에는 그대로 냅둔다. import java.util.Scanner; public class Main { static int n,t,d; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int tc = 1; tc
www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 물고기 이동은 구현에서 상어이동은 dfs로 완탐을 돌려줘야되는 문제여서 복잡했다 ㅠㅠ 지쳐.. 중간에 상어가 멈춰서 ?? 했는데 나는 상어이동을 bfs로 구현했고 물고기가 있는 칸으로만 이동하는 것으로 짰더니 빈 칸으로는 이동을 못해 오도가도 못한 상태로 끝나버렸다. 추후 빈 칸도 갈 수 있도록 했더니 통과되었다. 칸이 4x4로 정해져있기 때문에 무조건 3번 이동이 가능한지 for문으로 확인하..