모항이코딩한다

풀이방법 및 문제점 2022.11.09 어이 없는 이유로 계속 실패하다가 오늘 해결에 성공한 문제이다. 이 문제를 풀 수 있는 완벽한 로직은 9달 전부터 알고 있었다. 그러나 그 때에는 Comparator를 아직 알지 못해, 매우 비효율적인 방식으로 값들을 정렬하였다. 그래서 시간초과를 받았다. 그리고 오늘 다시 도전하였다. 오늘은 Comparator를 아는 상태이기 때문에 시간초과는 받지 않았다. 그러나 for문에 break를 넣어서 틀렸다. 넣을 이유가 없는데 왜 넣었는지 모르겠다. 정말 멍청한 실수였다! break를 지우니 정답 처리가 되었다. 정답 게시글 바로가기 코드 Java(2022.01.22) 시간초과를 받은 코드 import java.util.Scanner; import java.util...

풀이방법 사용된 것: 정렬 그리디 Comparator 2022.11.09 오답노트 #7983 : 내일 할거야 풀이방법 및 문제점 2022.11.09 어이 없는 이유로 계속 실패하다가 오늘 해결에 성공한 문제이다. 이 문제를 풀 수 있는 완벽한 로직은 9달 전부터 알고 있었다. 그러나 그 때에는 Comparator를 아직 알 blowupmomo.tistory.com 과제들을 마감일자가 가장 늦은 순으로 정렬한다. (가장 마감이 늦은 과제가 가장 앞에 오도록) 정답 값을 저장할 int 형 변수 ans를 선언하고, Integer.MAX_VALUE로 초기화한다. 그 후, 정렬되어있는 과제들을 앞에서부터 방문하며 아래를 반복한다. 이번 과제의 마감일자가 ans 값보다 큰 경우: ans = ans - (이번 과제를..

풀이방법 사용된 것: TreeSet 정렬 그리디 2022.11.09 이 문제의 경우, 모든 경우의 수에 대하여 1원당 열량을 구하는 것이 매우 쉽다. 그 이유는 다음과 같다. 토핑의 종류가 최대 100가지밖에 안 된다. 동일한 토핑을 여러 번 올리는 경우가 없다. 토핑의 가격이 모두 같으므로, 열량이 더 높은 토핑을 올리지 않은 채 열량이 더 낮은 토핑을 올린다면 무조건! 손해이다. 그러므로 가장 열량이 높은 토핑부터 골라잡는 게 무조건 이득이다. 따라서 모든 경우의 수에 대한 1원당 열량 값을 싹 다 구하고, 그 중 가장 큰 것을 출력하면 된다. 방법은 다음과 같다. 먼저 토핑의 값을 모두 읽어온 뒤 오름차순 또는 내림차순으로 정렬해놓는다. 아무 토핑도 올리지 않았을 경우의 1원당 열량을 계산하여 그 ..

풀이방법 2022.08.24 테스트케이스 개수가 최대 100개밖에 되지 않아서 그냥 단순하고 무식한 방법으로 해결하였다. 입력값에서 HH와 MM을 얻어오는 데에는 substring을 사용했다. 00시 00분으로부터 몇 분이 지났는지를 시각 값으로 이용함으로써 오전과 오후의 구분을 없애고 요금 계산을 쉽게 하였다. 오전 7시의 시각 값은 7*60 = 420, 오후 7시의 시각 값은 19*60 = 1140이다. 통화 시작 시점의 시각 값을 구해놓고 종료 시점에 이를 때까지 1분씩 더해가면서 요금을 구한다. 현재의 시각 값이 420(7*60) 이상 1140(19*60) 미만이라면 10원을 더하고 그렇지 않다면 5원을 더하는 방식이다. 전화하던 중 날짜가 바뀌었으면 현재의 시각 값을 0으로 만들어주고 계속한다...

풀이방법 2022.08.24 매우 간단한 문제이다. 주어진 문자열의 모든 글자에 대하여 if문을 사용해 공백, 소문자, 대문자, 숫자의 개수를 세면 된다. EDOC MT 팀대항전에서 푼 문제이다. 코드 Java(2022.08.24) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(..

풀이방법 사용된 것: HashSet 2022.08.24 중복체크를 해야 하므로 HashSet를 사용하여 풀었다. 참가자들이 3번의 게임에서 낸 숫자들을 일단 모두 읽어온다. 먼저, 각 회차마다 0점처리해야 하는 숫자를 해시셋에 넣어두는 작업을 한다. 회차가 3개이므로 해시셋 3개의 배열을 만든다. 이것을 dup라고 하겠다. 각 회차마다 참가자들이 낸 숫자들을 모두 훑으면서 중복되는 수를 그 회차를 담당하는 해시셋에 넣어둔다. 이제 점수를 계산한다. dup에 들어있는 숫자라면 0점을, 그렇지 않다면 낸 숫자만큼을 점수에 추가해주면 된다. EDOC MT 팀대항전에서 푼 문제이다. 코드 Java(2022.08.24) import java.io.BufferedReader; import java.io.IOExce..

풀이방법 사용된 것: 정렬 다익스트라 2022.08.17 고속도로 위에서 0미터 지점부터 D미터 지점까지 1미터씩 전진하며, 현재 자신이 위치한 지점으로부터 시작하는 지름길이 있는지 확인하는 방법을 사용했다. 불필요한 연산을 줄이기 위해 다음과 같이 지름길 정보를 걸러서 저장했다. 주어진 지름길들 중 지름길의 도착지점이 고속도로의 끝지점을 초과하지 않고 이용했을 때 이득이 되는 것들만 List list에 저장해둔다. 그리고 우리는 고속도로의 0미터 지점부터 차근차근 오름차순으로 진행해나갈 것이므로 지름길들을 시작지점을 기준으로 오름차순 정렬(시작지점이 같다면 끝지점을 기준으로 오름차순 정렬)한다. 다음으로는 다익스트라에 필요한 필드들을 준비한다. 1차원 정수 배열 dist를 선언한다. 이 배열은 각 지점..

풀이방법 사용된 것: 정렬 2022.08.12 재료가 N가지 있고 각 재료의 번호는 서로 겹치지 않는다. 재료 두 개를 골라 두 재료의 번호의 합이 M이 되는 경우의 수를 구하는 문제이다. 여러 가지 방법으로 풀 수 있는데 나는 아래와 같이 풀었다. 재료번호들을 오름차순 정렬한 뒤, (내림차순으로 정렬해도 됨) 0번 인덱스에 위치한 수를 좌항으로 잡고, 좌항보다 뒤의 인덱스에 위치한 수들을 우항 후보로 간주한다. 우항 후보들을 하나하나 검사해보며 좌항과의 합이 M이 되는 수가 존재하는지 판별한다. 그러한 수가 존재한다면, 정답의 값을 1 증가시킨 뒤, 현재의 좌항의 다음 수를 새로운 좌항으로 설정한 뒤 위의 과정을 반복한다. 코드 Java(2022.08.12) import java.io.BufferedR..

풀이방법 사용된 것: 조합 2022.05.08 몇 달 전에 푼 문제인데 정리글을 쓰지 않아 적는다. 동쪽에 있는 사이트들 중, 서쪽의 사이트 개수만큼을 고른다. 그럼 이제 다리를 놓을 수 있는 방법은 단 한 가지로 정해진다. 북쪽에서부터 차례대로 딱딱 연결하지 않으면 다리가 서로 겹치기 때문이다. 그러므로 이 문제의 답은 M개 중 순서 상관없이 N개를 뽑는 경우의 수이다. 중/고등학교 때 배운 조합 공식으로 풀면 된다. 코드 Java(2022.05.08) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class M..

풀이방법 사용된 것: Deque 2022.08.02 덱을 만들고, 원형인 것처럼 작동하게 하면 된다. 덱을 만들어서 1부터 N까지의 정수를 넣어두면 준비 끝이다. 이제 문제의 상황을 시뮬레이션하면 된다. 백준이가 숫자만 외치고 그냥 다음 사람으로 넘어가는 것은, 덱의 첫 요소를 꺼내서 가장 뒷 순서로 보내는 것과 같다. deque.add(deque.poll()); 이렇게 하면 된다. 그러므로 for(int t=1; t