Java/Algorithms

문제 접근 방식 이 문제는 입력을 왜 이렇게 불편하게 주는지는 모르겠다... 입력 받은 수들을 모두 뒤집은 후에 오름차순으로 정렬해야 하는데 입력 자체를 스트링으로 받기 때문에 스트링 빌더의 리버스 메서드를 사용하여 돌려준 후에 long 타입으로 변환해줬다. 그 후에 정렬은 직접 구현해서 하거나 sort 메서드를 사용하면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer ..

문제 접근 방식 정렬한 후에 반복문으로 카드 수를 일일이 체크하는 것이 더 빠르지만 Comparator 사용에 익숙해질 겸 한 번의 정렬만으로 해결해 봤다. 맵을 사용 해서 카드의 수를 키로 하고 값을 해당 카드가 등장할 때마다 1씩 증가시켜 줬다. 맵은 배열처럼 하나의 객체와 타입으로만 이루어진 것이 아니기 때문에 맵을 정렬하기 위해선 entrySet 메서드를 사용하여 셋이나 리스트로 바꿔줘야 한다. List entries = new ArrayList(cards.entrySet()); entries.sort( (o1, o2) -> { int ov = o1.getValue(); int tv = o2.getValue(); long ok = o1.getKey(); long tk = o2.getKey(); i..

문제 접근 방식 정렬 문제 해결을 위한 Comparator / Comparable 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또 da9dac.tistory.com 세 가지의 정렬 기준대로 시리얼 번호를 정렬해야 하는데 자바에서는 Comparator를 사용하여 정렬 메서드의 정렬 기준을 커스텀할 수 있다. (블로그에 Comparator와 Comparable에 대해 정리해 둔 글이 있으니 참고하길 바란다.) 우선 첫 번째 정렬 기준은 문자열의 길이라 짧은 것이 가장 최우선이고 길이가 같다면 시리얼 번호의 각 자릿수의 합이 낮은 것 합도 같은 경우에는 ..

1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 위의 문제의 경우에는 세 가지의 정렬 기준으로 주어진 입력을 정렬해야 하는데 반복문을 돌면서 총 3번의 정렬을 수행할 수도 있겠지만 Comparator와 Comparable을 이용해 커스텀 정렬 기준으로 정렬을 할 수도 있다. 자바에서 제공하는 두 인터페이스들은 객체를 비교할 수 있는 상태로 만들기 위해 사용하는데 숫자나 문자 같은 경우는 기본적으로 손쉽게 비교가 가능했지만 객체는 서로 다른 특성을 가지고 있기 때문에 어떤 것으로 비교해야 할지 정해진 기준..

문제 접근 방식 숨바꼭질 + 나이트의 이동 문제가 합쳐진 느낌의 문제인데 기존에는 가로세로, 가로세로상하 이렇게 이동했다면 이번에는 가로세로 + 나이트의 이동 방식 8가지가 합쳐진 BFS를 해야 한다. 총 12가지 방향으로 매번 탐색을 수행해 주면서 0,0에서 배열의 끝까지 갈 수 있는 최단 경로를 찾아주면 되는데 주의해야 할 점은 나이트의 이동 방식은 정해진 횟수만큼만 사용 가능하다. 예제 테스트케이스가 통과되는 코드를 작성하는 것은 쉬웠지만 막상 제출을 하니 계속해서 실패하였는데 처음에는 가로세로 이동과 나이트의 이동 모두 방문을 기록하는 배열을 공유해 봤고 두 번째에는 각각의 배열을 나눠서 사용해 봤는데 둘 다 공통적으로 발생하는 문제점이 있었다. 같은 배열을 쓰던 안 쓰던 나이트의 이동으로 앞서간..

문제 접근 방식 뒤로 이동은 x - 1, 앞으로 이동은 x + 1, 순간이동은 x * 2를 해주면서 동생의 좌표까지 가주면 되는 간단한 문제인데 함정이 몇 개 숨어있다. 뒤와 앞으로 이동하는 경우에는 이동시간이 1씩 증가하지만 순간이동의 경우에는 이동하는데 시간이 걸리지 않는다. 그래서 순간이동은 아무리 써도 시간이 걸리지 않기 때문에 순간이동을 우선적으로 사용해 주고 앞뒤로 이동해주어야 한다. 이동 순서가 바뀌게 되면 결과가 달라지는 문제라 이 부분을 신경 써줘야 한다. BFS를 사용해서 풀 때 한 가지 더 조심해야 할 부분이 있는데 큐는 들어온 순서대로 실행되기 때문에 최단경로가 텔레포트를 3 연속으로 사용하는 경우라도 텔레포트 > 텔레포트 > 텔레포트 순서대로 실행되는 것이 아니라 (텔레포트 > 앞..

문제 접근 방식 1이 끊어지지 않고 최대로 이어진 곳들을 하나의 대륙이라고 볼 수 있고 각 대륙들을 서로 잇는 다리의 길이들을 구해야 한다. 일단 각 대륙들을 구분하면서 각 대륙의 외곽 지역을 큐들에 집어넣었는데 대륙의 외곽 지역은 바다와 맞닿아 있는 땅이라고 볼 수 있다. 외곽 지역을 모두 찾은 후에는 외곽을 순회하면서 바다만 찾아서 탐색을 하면서 다른 대륙을 마주친 경우 현재까지 이동한 거리를 이전의 다리 길이와 비교하여 더 작은 경우에는 값을 바꿔주었다. 풀이 자체는 쉽게 떠올렸는데 코드로 구현하고 보니 엄청 길어진... 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br..

문제 접근 방식 빙산을 매년 녹이면서 현재 빙산의 연결들이 끊어지지 않았는지 확인을 해주면 되는 간단한 문제다. 문제의 풀이 자체는 간단하게 떠올릴 수 있는데 PS는 항상 코드 작성이 문제다... 일단 입력을 받으면서 바다(0)가 아닌 1 ~ 10의 빙산들을 모두 큐에 넣어주었는데 이 때 시간을 같이 기록해줘야한다. 시간을 기록하는 이유는 만약 10개의 빙산 중 첫 번째 빙산이 녹았을 때 그 다음 빙산은 녹아버린 첫 번째 빙산을 바다로 취급하지 않아야 되는데 코드 상으로는 빙산이 하나씩 순서대로 녹아내리지만 실제로는 동시간대에 존재하는 모든 빙산이 한 번에 녹아야하기 때문이다. 즉, 같은 시간대의 빙산끼리는 서로에게 영향을 줄 수 없어야 하고 이를 위해서 큐에 넣을 객체는 빙산의 좌표와 시간대를 포함하게..