전체 글 137
[JAVA] Next_Permutation 알고리즘

코테를 공부하다가 다음순열을 구하는 문제가 꽤 보이길래 정리를 해보기로 하였다. Next_Permutation 현재 순열의 상태에서 크기순으로(사전순) 다음에 올 수 있는 순열을 생성해주는 알고리즘이다. How? 1. 맨 뒤에서부터 탐색을 하다가 더이상 오름차순이 아닐 때 index를 찾는다. (교환할 대상) 2. 맨 뒤에서부터 탐색을 하다가 교환할 대상(index)보다 큰 값을 찾는다. 3. 그 둘의 위치를 바꾼다. 4. 위치를 바꾼후 index뒤를 전부 오름차순으로 정렬한다. 말로만 하면 이해를 못하니 예시를 통해 확인해보자. 예를 들어 1,4,5,6 이라는 수가 있다고 가정을 하자. 1. 맨뒤에서 탐색을 하다가 더 이상 오름차순이 아닐 때의 index를 찾는다. 6 -> 5 (오름차순이 아니다.) ..
코딩테스트 2022.05.10

[JAVA] String.matches() vs String.contains()

알고리즘 문제를 풀다가 정규표현식 문제를 만났다. String.matches()를 사용해서 푸는 문제였는데 contains()와 무엇이 다를까? 둘다 공통점은 반환값이 특정 값이 문자열에 포함되어있으면 true 아니면 false를 반환한다는 점이다. String.matches() matches()는 인자로 정규표현식을 받는다. 만약에 인자로 정규표현식이 아닌 문자열이 온다면 '포함'이 아니라 '정확히' 일치해야 한다. public class MatchesTest{ public static void main(String[] args){ String str = "my java test"; //정규표현식 사용 안할때 정확히 일치해야 한다 System.out.println( str.matches("java") ..
개발/JAVA 2022.05.02

[BOJ2468/JAVA] 안전 영역

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 풀이 해당문제는 BFS로 풀었던 완전탐색문제이다. 물에 잠기지 않는 안전한 영역의 최대 개수를 구해야한다. BFS로 탐색하면서 일정높이보다 높은 영역의 개수를 count를 세야한다. 이때 높이를 다 설정해가면서 최댓값을 계속해서 업데이트를 해주어야한다. 1. 입력값을 다 받으면서 영역의 가장 높은 길이를 구해준다. (1~100까지 다 최댓값을 구하는 것보다는 입력값의 가장 높은 길이를 구해서 그만큼..
코딩테스트 2022.04.26

[BOJ10972/JAVA] 다음 순열

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 처음에는 순열 문제여서 dfs로 순열을 만든다음에 배열에 저장하고 그 배열의 다음 인덱스를 출력하려고 했으나 풀이방법이 단단히 잘못되었다. 다른사람의 코드를 참고하니 애초에 값을 받은 다음에 받은 값에서 다음 순열이 무엇인지 배열의 원소를 바꾸면서 정렬해주는 식이다. 만약에 7 2 3 6 5 4 1 이라는 순열이 있다고 치자, 1. 맨 오른쪽 인덱스부터 시작해서 수열의 오름차순이 끝나는 지점을 찾는다. 이 말은 1부터 시작해서 하나씩 줄여나가면서..
코딩테스트 2022.04.23
1 2 3 4 ··· 14
더보기

티스토리툴바