기록방

👉 문제링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열이 있다. 두 수를 묶어서 곱셈 연산을 할 수 있고, 나머지는 합연산으로 계산한다. 계산 결과의 최대값을 출력한다. 🔸 문제 풀이 🔸 곱셈 연산으로 최대값을 만들어야 하므로 그리디 알고리즘으로 풀이한다. 수열을 정렬 후, 1보다 큰 수 중에서 크기가 큰 수를 우선으로 짝을 지어 곱셈 연산을 진행한다. 수가 1 미만인 수들은 음수끼리 만나 양수가 되거나, 0과 합쳐져 음수가 지워지므로 짝을 짓는다. 🔸 코드..

👉 문제링크 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열을 버블 소트로 정렬했을 때, swap이 총 몇 번 발생하는지 출력한다. 🔸 문제 풀이 🔸 N이 50만까지 가므로 O(nlogn)의 알고리즘을 사용해야 한다. 여기서는 병합 정렬(Merge Sort)을 사용한다. 버블 소트는 1칸씩 이동할 수 있으므로, 정렬 후 바뀐 인덱스의 크기를 모두 더하면 된다. 병합 정렬에서 기존 인덱스보다 앞 인덱스로 옮길 때, 그 크기를 누적해서 출력한다...

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 새로운 데이터가 입력될 때 마다 내림차순 정렬했을 때, k 번째 수를 출력한다. 배열의 정렬은 시간 복잡도가 커지므로 java 우선순위 큐의 최대 힙을 사용해 정렬한다. 🔸 코드 🔸 import java.util.PriorityQueue; class Solution { public int[] solution(int k, int[] score) { int[] answer = new int[score.length]; PriorityQueue que = new PriorityQueue..

👉 문제링크 7507번: 올림픽 게임 각 테스트 케이스마다 "Scenario #i:"를 출력한다. 여기서 i는 테스트 케이스 번호이며 1부터 시작한다. 그 다음 줄에는 상근이가 참석할 수 있는 경기의 최대 개수를 출력한다. 문제에서도 설명했지 www.acmicpc.net 🔸 문제 분석 🔸 문제 한 경기가 끝나야 다음 경기를 볼 수 있다. 종료와 시작 시간이 완전히 같아도 볼 수 있다. 테스트 케이스 별, 한 사람이 볼 수 있는 최대 경기 수를 출력한다. 풀이 (Greedy) 경기 정보를 날짜와 종료 시간으로 오름차순 정렬 한다. 다음 경기를 볼 수 있으면 카운트 + 1을 한다. 다음 경기가 다음 날짜이면, 무조건 볼 수 있으므로 다음 경기로 이동한다. 다음 경기의 시작이 현재 경기의 종료 시간보다 같거나..

👉 문제링크 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 🔸 문제 분석 🔸 입력받은 n개의 수에서 전체 입력 중에 더 작은 값의 개수를 출력한다. 2차원 배열 arr[n][3]을 선언한다. 1번째는 입력 값, 2번째는 입력 순서, 3번째는 압축 값을 저장한다. 1번째 값 기준으로 오름차순 정렬한다. 3번째 값을 채운다 배열 앞에서 부터 더 작은 값은 0, 1, 2...로 커져간다. 같은 값이 연속되서 나오면 값을 키우지 않고 그대로 저장한다. 2번째 값 기준..