모항이코딩한다

풀이방법 사용된 것: ArrayList 2022.04.30 ArrayList는 새로운 요소를 특정 인덱스에 추가하였을 때 그 인덱스보다 뒤에 있는 요소들을 자동으로 한 자리씩 뒤로 이동시켜준다. 따라서 이 문제는 ArrayList를 사용하면 쉽게 풀리는 문제이다. 학생이 뽑은 번호가 주어질 때마다 맨 뒷자리의 인덱스, 즉 이번 학생이 0을 뽑았을 경우 서야 하는 자리의 인덱스에서 학생이 뽑은 번호만큼을 빼서 그 인덱스에 학생을 add하면 된다. 코드 Java(2022.04.30) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import..

풀이방법 사용된 것: Stack 2022.04.29 #9012 : 괄호 풀이방법 사용된 것: 스택 2022.03.02 boolean 형 변수 v를 사용한다. 해당 문자열이 올바른 괄호 문자열이면 v 를 true로, 그렇지 않으면 false로 설정할 것이다. v의 초기값은 true이다. 반복문 내에서, 주 blowupmomo.tistory.com 백준 9012번 괄호 문제와 매우 비슷한 문제이다.​ 각 문자열마다 아래의 과정을 수행하면 된다. boolean 형 변수 v를 true로 초기화해준 뒤, 문자열이 균형잡히지 않았다는 것이 발견되면 false로 바꾸어줄 것이다. 마지막에 v의 값이 true인 상태로 남아있다면 해당 문자열은 균형잡힌 것이다. 주어진 문자열을 처음부터 한 글자씩 살핀다. 이번 문자가 ..

풀이방법 사용된 것: 그리디 알고리즘 정렬 2022.04.28 물이 새는 곳을 편하게 '구멍'이라 부르겠다. 가장 왼쪽 구멍부터 살피면 되므로 그리디 알고리즘이다. 가장 왼쪽 구멍부터 살피려면 구멍 위치 배열을 오름차순 정렬해야 하므로 정렬이 사용된다. 먼저 구멍들의 위치를 싹 읽어와 int[]형 배열에 저장한 뒤, 이 배열을 오름차순 정렬한다. 2개의 정수형 변수가 사용된다. 정수형 변수 cnt는 현재까지 사용된 테이프의 개수를 저장한다. 즉, 다 풀고 나면 이 문제의 정답이 cnt에 저장되게 된다. 다 쓰지 않았더라도 지금 사용하는 중인 테이프까지 세어야 하므로 초기값을 0이 아닌 1로 선언한 뒤, 새 테이프를 꺼낼 때마다 1씩 증가시킬 것이다. 정수형 변수 left는 지금 사용하는 중인 테이프의 왼..

풀이방법 사용된 것: HashMap TreeSet 2022.04.28 평균, 중앙값, 범위는 매우 쉽게 구할 수 있으나 최빈값을 구하기가 성가신 문제였다. 최빈값을 구하는 데에만 해시맵과 트리셋을 다 사용했다... 더 간단하게 구하는 방법이 있을 것 같은데 뭔가 찝찝하다. 평균은 총합을 구한 뒤 이를 n으로 나누면 된다. 그리고 입력된 수들을 모두 저장한 int[]형 배열을 오름차순으로 정렬한다.(Arrays.sort() 사용) 정렬된 배열에서 인덱스가 n/2인 수가 중앙값이다. 정렬된 배열의 마지막 수에서 첫 번째 수를 뺀 것이 범위이다. 최빈값을 구한 방법은 다음과 같다. 먼저 해시맵을 사용해 모든 수의 등장 횟수를 구한다. 를 저장하는 형 해시맵을 사용하면 된다. 그 다음 위의 해시맵을 처음부터 돌..

풀이방법 사용된 것: 수학 2022.04.23 주어진 벌집은 다음과 같이 여러 개의 겹으로 인식할 수 있다. 안쪽으로부터 몇 번째 겹에 있느냐에 따라, 그 칸에 도착하기까지 거치는 칸의 수가 정해진다. 17은 3번째 겹에 위치하므로, 17이 입력값으로 주어졌을 때 올바른 출력값은 3이다. 따라서, 주어진 수가 몇 번째 겹에 위치하는지를 알아내는 알고리즘을 작성하면 된다. 1번째 겹에 속하는 수는 1개이다. 2번째 겹에 속하는 수는 6개이다. 3번째 겹에 속하는 수는 12개이다. 4번째 겹에 속하는 수는 18개이다. ... n번째 겹에 속하는 수는 6$\times$(n-1)개이다. 이러한 규칙을 이용하여, 각 겹에서 가장 큰 수를 저장하는 정수 배열을 생성할 수 있다. N의 최댓값이 1,000,000,00..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.04.21 가능한 수를 모두 구하고 그 중 최솟값을 출력하면 된다. 처음엔 브루트포스로 풀면 시간초과가 날까봐 다른 방법을 생각해내려 애썼다. 그런데 전혀 생각이 나지 않았다... 그래서 문제의 카테고리를 펼쳐보니, 이럴 수가 브루트포스 문제였다. 그냥 다 구하면 된다. 알고리즘은 다음과 같다. 칸의 색이 흰색 혹은 검은색으로 두 가지이므로 boolean값을 이용해 색을 구분하였다. 검은색은 true로, 흰색은 false로 하였다. 하나의 8$\times$8 크기 구획 내에서 고쳐야 하는 칸의 최소 개수를 구하는 함수를 정의한다. 그리고, 이 함수를 해당 체스판에서 만들어질 수 있는 모든 8$\times$8 크기 구획에 대하여 수행하면 된다. 그 중 최솟..

풀이방법 사용된 것: Queue 2022.04.21 큐를 이용하여 풀었다. 먼저 큐에 1부터 N까지의 수를 순서대로 넣는다. 가장 앞 사람을 poll()하여 맨 뒤에 add()하는 작업을 K-1번 반복한다. 그럼 제거해야하는 사람이 가장 앞에 오게 된다. 한 명을 poll()하여 정답 배열에 추가한다. 이 과정을 N번 반복하면 된다. 코드 Java(2022.04.21) import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = ne..

풀이방법 사용된 것: 해시맵(HashMap) 이분탐색법 해시맵을 사용하는 방법, 이분탐색법을 이용하는 방법이 있다. 시간은 해시맵이 덜 걸리고 메모리는 이분탐색법이 덜 사용한다. 2022.04.19 먼저 해시맵을 사용하는 방법이다. 의 데이터 쌍을 저장하는 해시맵을 하나 선언한다. Key에는 카드의 번호, Value에는 카드의 개수를 저장할 것이다. 상근이가 가지고 있는 카드들의 번호를 차례차례 읽어오면서 개수를 세어준다. 처음 세는 카드라면 해시맵에 (해당 카드의 번호, 1)의 요소를 새롭게 추가한다. 이미 센 적 있는 카드라면 해시맵에 (해당 카드의 번호, 현재까지 센 개수에 1을 더한 값)의 요소를 추가한다. 해시맵은 키가 동일한 다수의 요소를 저장하지 않으므로 자동으로 이전의 요소는 지워진다. 이..

풀이방법 사용된 것: 수학 2022.04.19 이항계수의 수학적 정의대로 계산해주면 된다. 코드 Java(2022.04.19) 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 a = sc.nextInt(); int b = sc.nextInt(); int ans = 1; for(int i = 0; i

풀이방법 사용된 것: Deque 2022.04.17 주어진 수를 한 글자씩 덱에 넣는다. boolean타입 변수 v를 선언하고 true로 초기화한다. 덱의 양쪽 끝에서 글자를 하나씩 poll() 해와서 두 글자를 비교하는 과정을 덱이 텅 비거나 덱에 글자가 하나 남을 때까지 반복한다. 꺼내온 두 글자가 동일하면 continue한다. 한 번이라도 두 글자가 서로 다르면 v의 값을 false로 바꾸고 즉시 반복문을 끝낸다(break). 두 글자가 다른 적이 한 번도 없다면 v의 값이 바뀌지 않는다. 따라서 v가 true로 남은 채 반복문이 끝난다. 따라서 주어진 수가 팰린드롬수라면 v는 true로 남고, 그렇지 않으면 v는 false가 된다. 코드 Java(2022.04.17) import java.io.B..