오늘도 디벅잉

🤖 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 정렬을 사용하면 메모리 초과가 됩니다. 주어지는 수의 개수가 최대 1천만개로 이를 모두 저장해서 정렬한다면, 4바이트 * 1천만 = 40MB에 달하여 상당한 메모리를 차지한다고 볼 수 있습니다. 다만, 주어지는 수의 범위는 최대 1만까지이기 때문에 각각의 수를 인덱스로 하는 배열을 만들고 개수를 기록한 후 앞에서부터 하나씩 뽑아서 출력합니다. (아래의 코드로 PyPy3에서는 메모리 초과, Python3..

🤖 문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 이진 탐색으로 풀이를 진행했습니다. 아래와 같이 처음으로 제출한 코드를 정돈할 수 있을 것 같아 정리해보았습니다. 1. 첫 코드에서 11번째 줄 answer변수에 굳이 결과를 담지 않고, 아래의 코드 26번째 줄과 같이 바로바로 출력했습니다. 2. 첫 코드 13번째 줄 for문 안에서 인덱스를 사용할 일이 없습니다. 아래의 코드 11번째 줄과 같이 배열..

🤖 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 문제를 너무 쉽게 판단하고 '틀렸습니다.'라는 결과를 맞이하게 되었습니다. 카드 묶음을 오름차순으로 정렬한 후 앞에서부터 순서대로 더하면 답이 나올 것이라고 생각했습니다. 아래 코드의 11~13번째줄과 같이 첫번째, 두번째 숫자는 N-1번 더하고, 마지막 숫자는 1번만 더할 것이라는 개념을 바탕으로 풀이를 작성하였습니다. 이 풀이의 문제는 아래의 예시를 해결할 수 없다..

🤖 문제 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 시간초과로 구글링을 하였고, 입력값을 받는 방법을 변경하여 해결했습니다. input() 대신 속도가 더 빠르다고 하는 sys.stdin.readline()을 사용했습니다. 속도 차이가 나는 이유는 버퍼의 크기가 다르기 때문으로 보입니다. sys.stdin.readline() 버퍼의 크기가 커서 한번에 많은 처리를 하는 것입니다. 또한 출력내용을 한번에 모아서 출력하..

🤖 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 삭제할 노드를 부모로 가지는 노드를 모두 삭제하고, 이어서 삭제된 노드들을 부모로 가지는 노드들을 삭제하는 과정을 반복하는 방식으로 풀어나갔습니다. 이러한 문제의 접근 방법은 깊이우선탐색(DFS)으로 볼 수 있을 것입니다. 하지만 결과로 '틀렸습니다'가 계속 나오는 바람에 꽤나 헤맸습니다. 조건식을 잘못 작성한 것이 원인이었습니다. 루트만 남는 경우 루트를 리프 노드로 카운트 ..

🤖 문제 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt"; const INPUT_ARR = require("fs").readFileSync(filePath).toString().trim().split("\n"); const Q_ARR = INPUT_ARR[1].split(" ").map(Number); let countPrime = 0; function isPrime(n..

🤖 문제 https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt"; const INPUT_ARR = require("fs").readFileSync(filePath).toString().trim().split(" "); console.log( INPUT_ARR.reduce((pre, cur) => BigInt(pre) + BigInt(cur)).toString() ); 1. (line 5) 주어진 숫자 2개를 BigIn..

🤖 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt"; const INPUT_N = +require("fs").readFileSync(filePath).toString().trim(); let box5kg; let box3kg; function calcBoxNum(totalKg) { box5kg = Math...

🤖 문제 https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 풀이 const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt"; const INPUT_ARR = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const CASE_NUM = +INPUT_ARR[0]; const CASE_ARR = INPUT_ARR.slice(1); ..

🤖 문제 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이 const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt"; const INPUT_ARR = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const INPUT_COUNT = +INPUT_ARR[0]; let ..