모항이코딩한다

풀이방법 사용된 것: 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

풀이방법 사용된 것: Stack 2022.07.19 후위 표기식은 무조건 앞에서부터 계산하면 올바른 답이 나오도록 되어있다. 그러니 그냥 식을 앞에서부터 탐색하며, 식이 끝날 때까지 아래와 같은 과정을 반복하면 된다. 피연산자가 등장하는 동안에는 피연산자들을 스택에 차곡차곡 쌓다가, 연산자가 등장하면 즉시 그 연산자의 바로 직전에 있는 두 개의 피연산자 즉 스택의 top과 top 바로 아래에 있는 피연산자 두 개를 꺼내온 뒤, 그 두 개를 가지고 연산을 한 값을 다시 스택에 쌓아주면 된다. 등장한 연산자가 곱셈/나눗셈인지, 덧셈/뺄셈인지는 신경 쓸 필요 없다. 그들 사이의 우선순위까지 모두 고려하여 그냥 앞에서부터 계산하면 되도록 정렬해놓은 것이 바로 후위 표기식이기 때문이다. 코드 Java(2022.0..

풀이방법 사용된 것: 수학 2022.07.13 간단한 문제이지만 기억해야 할 것이 한 가지 있어서 적는다. 정답을 구하기 위하여 나눗셈과 곱셈을 한 번씩 해야 하는 문제이다. 이때 주의할 점은 정답을 출력할 때 소숫점 아래를 모두 버린다고 해도, 출력연산 대상인 세 수를 정수 형태로 읽어오면 안 된다는 것이다. 먼저 double 등의 소수 타입으로 받아온 다음, 연산을 모두 마치고, 정답이 도출된 뒤에 그 정답을 정수로 만들어 출력해야 한다. 그러지 않으면 오차가 발생한다. 예를 들어, 1 / 3 * 4 라는 연산을 하는데, 세 수를 모두 정수로 읽어왔다고 치자. 1 / 3 의 값은 0.33333.....이지만, 1과 3 두 수 모두 정수형이라면 프로그램은 소숫점 아래를 버리고 0이라는 정수형의 결과를 ..

풀이방법 사용된 것: Comparator Overriding 2022.07.11 일단 문제에서 말한 기준대로 나라를 내림차순으로 쫙 정렬한다. 이렇게 정렬된 배열 상에서, K나라의 위치(인덱스)를 찾는다. 그 인덱스 값을 정수형 변수 answer에 저장해둔다. 만약 K나라와 동점인 나라가 하나도 없다면 answer+1이 답이다. 동점인 나라가 존재한다면 동점인 나라의 개수만큼을 answer에서 빼준 뒤에 1을 더하면 그것이 답이다. 따라서 아래의 과정을 통해 동점인 나라의 개수를 센다. 먼저 동점인 나라의 개수를 저장할 정수형 변수 cnt를 선언하고 0으로 초기화한다. 인덱스가 answer-1인 나라부터, 즉 K나라의 바로 직전 순서로 정렬되어있는 나라부터 시작하여 1등 나라(인덱스 0)까지 탐색한다. ..

풀이방법 2022.06.23 간단한 문제이지만 기억해야 할 내용이 하나 있어서 적는다. 다음과 같이 Scanner를 사용한 코드를 제출하면 런타임 에러(NoSuchElementException)가 발생한다. import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); for(int i=0; i=0; j--) System.out.print(arr[j]); System.out.print(System.lineSe..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.06.19 브루트포스로 풀면 매우 쉽다. 굳이 이분 탐색을 써보려고 하다가 계속 실수를 해서 그냥 브루트포스로 풀었다. 각 버스 노선마다, 영식이의 터미널 도착 이후에 출발하는 배차들 중 가장 이른 것 하나만 다룬다. 이 조건을 만족하는 버스 출발 시간은 각 노선마다 1개 혹은 0개 있다. 이렇게 찾아낸 출발 시간들 중 최솟값을 취하면 된다. 영식이의 터미널 도착 이후에 출발하는 배차가 하나도 없을 때, 즉 영식이가 탈 수 있는 버스가 없을 때는 화면에 -1을 출력한다. 코드 Java(2022.06.19) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea..