Java/Algorithms

문제 접근 방식 두 수의 차이가 m 이상이면서 가장 작은 경우를 구해야 하는데 간단하게 이중 반복문으로도 풀 수는 있지만 입력의 크기를 생각하면 시간초과 때문에 다른 방법을 사용해야 한다. 골드 문제지만 투 포인터를 사용해서 풀면 간단하게 풀 수 있는 문제로 6개의 수가 주어졌을 때 차이가 3 이상인 수 중에서 가장 작은 경우를 찾아보겠다. 1 3 5 7 8 10 우선 위와 같이 주어진 수들이 정렬되어 있을 때 순서대로 비교할 기준을 처음인 1과 나머지 숫자들을 차이가 3 이상이 될 때까지 비교해보면 1 - 3 >> 2 1 - 5 >> 4 1 - 7 >> 6 1 - 8 >> 7 1 - 10 >> 9 5와 비교 했을 때 차이가 4로 처음으로 3보다 커지는데 이후의 비교는 차이가 점점 커지기 때문에 의미가 ..

문제 접근 방식 문제에 나오는 환형의 개념 중에서 대각선 이동이 살짝 햇갈렸던 문제인데 위의 사진들처럼 대각선 이동 중 인덱스를 벗어나는 상황을 살펴보면 인덱스가 음수가 되는 경우에는 가장 아래줄의 왼쪽이나 오른쪽으로 한칸 이동 양수가 되는 경우에는 가장 첫줄의 왼쪽이나 오른쪽으로 한칸 이동해주면 된다. 나머지 상하좌우 이동도 환형을 생각해주면서 백트래킹으로 단어를 조합만 해주고 이를 맵을 사용해서 각 단어별로 카운팅을 해줬다. 설명은 이해가 잘 안갔는데 막상 풀어보니 난이도 자체는 어렵지 않았던 문제다. 풀이 public class Main { private static int n; private static int m; private static int min = Integer.MAX_VALUE; p..

문제 접근 방식 처음 풀어보는 DP문제로 백트래킹으로도 풀 수 있지만 시간제한이 빡빡한 문제이기 때문에 DP로 효율적으로 풀어야 풀 수 있는 문제다. 2를 1로 만드는 경우 2 - 1 >> 1 2 / 2 >> 1 3을 1로 만드는 경우 3 / 3 >> 1 3 - 1 - 1 >> 2 4를 1로 만드는 경우 4 / 2 / 2 >> 2 4 / 2 - 1 >> 2 4 - 1 - 1 / 2 >> 3 4 - 1 - 1 - 1 >> 3 가장 작은 경우를 예로 들어 2 ~ 4가 1이 되는 경우를 살펴보면 위와 같은데 4 / 2 / 2 순서로 계산하여 1이 되는 경우에는 숫자의 변화는 4 > 2 > 1이 될 것이고 해당 숫자의 인덱스에 계산 횟수를 기록한다 치면 {0, 2, 1, 0, 0} 이 된다. 여기서 알 수 있는..

문제 접근 방식 바킹독님 시뮬레이션 강의를 들으면서 처음 풀어보는 빡구현 문제로 지문 길이 보고 풀기 싫어지지만 귀찮음을 이겨내고 풀어냈다... 무식하게 풀다 보니 코드가 엄청 길어지긴 했지만 백트래킹을 사용해서 쉽게 풀 수 있는 문제다. (지문의 길이게 겁먹지 말자...) 백트래킹 연습 문제로 풀었던 N과 M 시리즈를 CCTV에 적용하면 되는 문제로 1번 : 위, 오른쪽, 아래, 왼쪽 중 한 방향이벽을 만나기 전까지 감시 가능 2번 : 위/아래, 왼쪽/오른쪽 중 양쪽이 벽을 만나기 전까지 감시 가능 3번 : 위/오른쪽, 오른쪽/아래, 아래/왼쪽, 왼쪽/위처럼 직각인 두 방향이 벽을 만나기 전까지 감시 가능 4번 : 위/오른쪽/아래, 오른쪽/아래/왼쪽, 아래/왼쪽/위, 왼쪽/위/오른쪽처럼 세 방향이 벽을..

문제 접근 방식 세그먼트 트리를 사용해서 풀 수 있는 문제라는데 아직 배우지 않아서 세그먼트 트리에 대해서 간단하게 검색해 보니 재귀를 사용한 방식이라 스택으로도 풀 수 있는 문제라서 스택을 사용해서 풀어봤다. 눈으로는 이해가 쉽고 넓이가 바뀌는 구간을 찾아서 계산을 해주면 해결된다는 사실도 머리로는 쉽게 이해가 가능하지만 구현하려니 막상 머리가 안 돌아갔다... 우선, 간단하게만 생각해 보면 직사각형의 넓이는 다음 막대그래프의 높이가 낮아질수록 최대로 가능한 넓이가 작아질 것이고 다음 막대그래프의 높이가 같거나 높아야 최대로 가능한 넓이가 유지되거나 커진다. 정리하면 각각의 높이가 4 5 5인 막대그래프가 연속해서 존재하면 가능한 최대 높이는 가장 낮은 높이인 4와 연속된 그래프의 개수 3을 곱한 12..

문제 접근 방식 문제를 본 순간 떠올릴 수 있는 가장 쉬운 풀이는 배열을 하나하나 다 비교해 보는 것인데 두 배열의 최대 크기가 20000이기 때문에 최악의 시간 복잡도가 20000^2라 해당 문제를 풀 수가 없다. 투 포인터를 사용하여 효율적으로 풀 수 있지만 아직 배우지 않았기 때문에 정렬만 사용해서 풀어보기로 했다. 우선 두 배열을 모두 오름차순으로 기본 정렬한 후에 먹히는 배열을 순회하면서 먹는 배열을 매번 순회해 준다. 이때 먹히는 배열의 값이 먹는 배열의 값보다 작아지는 시점부터는 뒤에 오는 배열의 값들은 확인할 필요가 없기 때문에 남은 배열의 크기만큼 카운트를 추가해 주면 된다. 이렇게 풀면 시간은 오래 걸려도 통과는 되긴 하지만 나중에 이분탐색을 배운 후에 다시 풀이를 추가하도록 하겠다. ..

문제 접근 방식 숫자의 등장 횟수가 가장 많은 순서대로 정렬해야 하고 같은 경우에는 처음 입력된 순서대로 유지해야 한다. 입력 순서를 유지하기 위해 LinkedHashMap을 사용해서 풀었는데 생각해보니 입력의 범위가 모두 int형이라 배열을 사용해도 되는 문제다. 순서와 숫자의 카운트만 신경 써서 정렬해주면 되는 문제라 구현 자체는 어렵지 않았다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); Stri..

문제 접근 방식 입력받은 문자열들 중에서 중복을 제외하고 문자열의 길이가 같지 않다면 짧은 것을 우선 정렬하고 같다면 사전순으로 정렬해줘야 한다. 입력받은 배열을 위의 정렬 기준으로 정렬한 후에 중복이 아닌 경우만 출력해 주거나 Set을 이용해 애초에 중복을 허용하지 않고 저장하여 정렬한 후에 출력해 주는 방법이 있는데 Set을 사용해서 풀었다. HashSet을 이용해서 중복 없이 입력받은 후에 정렬을 해주거나 TreeSet을 이용해서 순서를 유지해 가며 입력을 받을 수 있다. 첫 번째 코드가 HashSet을 이용한 방법이고 두 번째 코드가 TreeSet을 이용한 방법이다. 풀이 public class Main { public static void main(String[] args) throws IOEx..