정렬55 백준 16496 자바 - 큰 수 만들기 (boj 16496 java) 문제 : boj16496 당연한거지만 앞에 올수록 더 전체값이 커질만한 순서대로 정렬한 후, 출력해주면 되는 문제이다. 그 정렬 규칙만 잘 정하면 된다. 케이스1 - 예를들어 9와 89999999가 있다. 직관적으로 자리수와 정렬 규칙은 관계가 없음을 알 수 있다. 둘 중 작은 길이의 숫자까지 비교해서 그 중 다른 숫자가 있다면 쉽게 규칙을 정할 수 있다. 이 경우 9를 먼저 놓는것이 당연히 이득이다. 케이스2 - 그럼 98와 98999이 있다면 어떨까? 직관적으로 98999를 먼저 두는 것이 이득임을 알 수 있다. 이 경우는 '케이스1'로는 판단할 수 없는 경우이다. 그렇다면 자리수가 다르면서, 둘 중 작은 자리수까지 비교해도 비교가 안되는 경우를 어떻게 판단할지가 관건임을 알 수 있다. 내 경우 규칙.. 2022. 3. 30. 백준 13537 자바 - 수열과 쿼리 1 (BOJ 13537 JAVA) 문제 : boj13537 기본적으로 알고 있어야 하는 알고리즘 기법들이 좀 있어야 이해할 수 있는 풀이 입니다. 모르는 알고리즘이 있다면 별도로 공부하셔야 이해하실 수 있습니다. 결국 통과된 풀이에 쓰인 오프라인 쿼리는 사실 어차피 값이 변경되지 않으므로, 순서를 바꿔서 쿼리를 진행하더라도 원래 위치만 안다면 순서를 바꿔서 답을 구한 후, 원래 위치에 맞게 답만 출력해주면 된다고만 이해하시면 됩니다. 제곱근 분할법은 여기를 참고하시면 될 것 같습니다. 몰라도 사실 유-명한 세그먼트 트리를 사용하면 더 효율적으로 풀 수 있습니다. (제곱근 분할법인 sqrt(N), 세그먼트 트리는 logN) 1. 시간초과 난 풀이방법 '1'은 오답노트 느낌으로 시간초과 난 풀이방법을 적은 것이니, 통과한 풀이를 보고 싶으시.. 2022. 3. 25. 백준 23394 자바 - Haja Ordenação (BOJ 23394 JAVA) 문제 : boj23394 Brute force로 생각하기 쉽지만, 사실 이 경우 10^5C2 만큼 판단해야 할 것이므로 시간내에 통과할 수 없다. 아이디어만 잘 떠올린다면 아주 간단하게 풀 수 있다. 사실 동일한 색상 2개를 고르고 교환하는 부분을 직접 할 필요가 없다. 중요한건 최종적으로 정렬된 순서로 만들 수 있냐이므로, 처음 입력으로 들어왔던 색상의 순서와 시퀀스만 가지고 정렬한 순서의 색상이 동일하다면 실제 색상 2개를 고르고 서로 교환하는 부분은 어떻게든 가능할테니 대충 퉁칠 수 있는 부분이 된다. 예를들어 예제 입력1과 2는 다음과 같다. 처음 입력으로 들어온 색상과, 시퀀스를 기준으로 정렬된 색상의 순서가 서로 다르다면 N, 동일하다면 Y를 출력해주면 된다. 코드 : github import.. 2022. 3. 1. 백준 14729 자바 - 칠무해 (BOJ 14729 JAVA) 문제 : boj14729 문제 자체는 단순히 모두 입력받은 후 오름차순으로 정렬해서 처음 7개만 출력하면 되는 아주 간단한 문제이다. 다만 생각할 부분이 좀 있는데, 애초에 스페셜 저지 문제가 아니므로(별도의 채점 로직 없이 단순히 입력을 주고 출력 나온걸 정답과 비교하는 형태) 무조건 입력받은 형태 그대로 출력해야 한다. 그렇다면 사실 String 그대로 받고 비교하는게 맞긴하다. 왜냐하면 무조건 소수점 3자리까지 입력으로 들어온다고 조건을 주지 않았기 때문이다. 하지만 이 경우 자바로는 String으로 N개를 입력받는 것 자체가 메모리 초과가 나게 된다. 결론적으로 정석대로(String 그대로 받기) 자바로 풀기 위해서는 모두 입력받고 정렬하면 안되고, 별도로 가장 낮은 값 7개를 찾는 로직을 세워야.. 2022. 2. 26. 백준 10817 파이썬 - 세 수 (BOJ 10817 Python) 문제 : boj10817 변수가 3개밖에 안되므로, 조건문만 여러개 사용해도 쉽게 풀 수 있다. 하지만 왠지 한줄로 처리하고 싶었다. input()을 split해서 list로 변환 후, 정렬하고 2번째 인덱스의 값을 출력했다. 그럼 2번째로 큰 수가 출력된다. 코드 : github print(sorted(list(map(int, input().split())))[1]) 2022. 2. 23. 백준 16678 자바 - 모독 (BOJ 16678 JAVA) 문제 : boj16678 1. 문제 이해 결국 단 1번의 Defile로 모두 박탈시키려면 모든 의원의 명예를 1부터 차츰차츰 상승하는 계단형식으로 만들면 된다. 즉, 모든 의원의 명예가 낮은 명예부터 봤을 때 2이상 차이가 나지 않게 하면 된고, 이렇게 만들 때 최소한만 감소시켜서 진행해야 한다. 2. 문제 풀이 1부터 n까지 확인하면서 해당 값을 한명씩 무조건 가지도록 명예를 깎는다면 모든 명예값이 2이상 차이나지 않을 수 있다. 단순히 생각해도 더 낮은 숫자를 만들기 위해서는 애초에 명예가 낮은 의원의 명예를 깎는것이 더 최소한의 횟수로 만들 수 있을 것이다. 따라서 우선 입력으로 들어온 값을 오름차순으로 정렬해보자. 그리고 1부터 1개씩 증가시키며 해당 값에 한명 이상 매칭시켜보자. 예를들어 '예제.. 2022. 2. 21. 백준 20291 자바 - 파일 정리 (BOJ 20291 JAVA) 문제 : boj20291 1. A.B 의 형태로 입력이 주어질 때, 결국 A는 아예 필요없고 B만 보면 된다. 따라서 문자열 파싱을 통해 '.' 뒤의 문자만 빼낼 수 있어야 한다. 2. 확장자에 대한 카운팅이 필요하다. 해시를 사용하는것이 효율적이다. 해시맵을 사용해 key를 확장자로 두고, value를 카운팅으로 하면 된다. 3. 결과를 확장자 이름순으로 출력해야 한다. 해시맵에서 keySet을 빼내서 정렬해도 되겠지만, 애초에 메모리를 좀 더 써서 따로 key값만 가지고 있다면 더 효율적으로 정렬할 수 있다. 내 경우엔 리스트에 새로운 key가 나올 경우 담아두었다. 그리고 리스트를 정렬한 후, 오름차순으로 정렬되어있는 key가 담긴 리스트를 순회하며 key와 value를 얻어 출력해줬다. 코드 : .. 2022. 2. 17. 백준 20126 자바 - 교수님의 기말고사 (BOJ 20126 JAVA) 문제 : boj20126 각 시험이 서로 겹치지 않는다는 점 때문에 상당히 쉽게 풀 수 있다. 결국 모든 시험이 겹치지 않으므로, 각 시험의 비어있는 구간이 M 이상인지만 확인하면 된다. 즉, i번째 시험을 arr[i] 라고 한다면, arr[i].x - (arr[i-1].x + arr[i-1].y) 의 값이 M보다 크다면 문제의 조건을 만족하는 시간이 된다. 예를들어 다음의 입력을 봐보자. 3 4 20 3 1 7 5 13 3 위의 그림 중 첫번째 이미지처럼 다른 시험들이 진행될 것이다. 이 때 우리가 확인해야 할 부분은 두번째 이미지의 파란 부분이다. 정렬 후 위에서 제시한 공식대로 진행한다면 어렵지 않게 찾을 수 있다. 답은 16이 될 것이다. 그리고, 그림에서도 나오듯이 주의점은 0-3 구간과 16-.. 2022. 2. 1. 백준 11609 자바 - Class Time (BOJ 11609 JAVA) 문제 : boj11609 order by last asc, first asc의 형태로 정렬하면 된다. 문자열을 입력 받아 띄어쓰기를 기준으로 나눌 줄 알고, 정렬하는 방법을 안다면 쉽게 풀 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Name implements Comparable { String first, last; public Name(String name) { StringTokenizer st = new StringTokenizer(name); first = st.nextToken.. 2022. 1. 29. 백준 10373 자바 - Buffcraft (BOJ 10373 JAVA) 문제 : boj10373 1. 문제 정의 상당히 문제가 불친절하다. 예제라도 의미 있을 예제를 들어주면 좋을텐데 ㅡㅡ; 상당히 별로인 문제이다. 1.1 'The following line must contain n different numbers', 'The last line of the output must contain m different numbers' 에 따라 출력을 해줘야 하는데, 그럼 following line이 0이라 출력할 게 없으면 줄을 띄워야 되나 말아야 하나라는 문제점이 있다(second, third line이라고 하던지.. 저렇게 하면 사실 following line이 last line이 되기도 하므로 애매하다.). 원래 문제대로라면 줄을 띄워야 맞지만(해당 대회 문제 채점 데이터.. 2022. 1. 17. 이전 1 2 3 4 5 6 다음
