기록의 흔적, 기억의 발자취

문제https://www.acmicpc.net/problem/24262시간 복잡도(Time Complexity) 개념을 이해하는 데 초점을 둔 문제입니다. 주어진 문제에서 함수 f(n)은 입력값 n에 관계없이 항상 한 번만 실행됩니다. 따라서 이 함수의 시간 복잡도는 상수 시간 복잡도인 O(1)입니다. 접근 방법상수 시간 복잡도: 함수 f(n)은 입력값 n과 상관없이 단 한 번 실행되므로, 항상 시간 복잡도는 O(1)입니다. 풀이 과정첫 번째 줄에는 1 (실행 횟수)두 번째 줄에는 0 (시간 복잡도 O(1)을 의미) 코드import java.io.IOException;public class Main { public static void main(String[] args) throws IOExcept..

문제https://www.acmicpc.net/problem/3003입력으로 주어진 말의 개수를 기준으로, 체스 세트를 완성하기 위해 몇 개의 말이 더 필요하거나 초과하는지를 구하는 것이 목표이다. 접근 방법주어진 입력을 읽고, 각 말의 개수가 체스 세트에 필요한 기본 개수와 얼마나 차이가 나는지 계산해야 합니다.이를 위해, 각 말의 기본 개수를 저장한 배열과 입력으로 받은 현재 말의 개수를 저장한 배열을 이용하여 차이를 구합니다. 풀이 과정기본 개수 배열을 정의합니다: int[] requiredPieces = {1, 1, 2, 2, 2, 8}.입력된 말의 개수를 저장합니다.기본 개수와 입력된 개수의 차이를 계산하여 출력합니다. 코드import java.io.BufferedReader;import jav..

문제https://www.acmicpc.net/problem/1316주어진 단어가 '그룹 단어'인지 확인하는 문제로,  그룹 단어란 각 문자가 연속해서 나타나는 단어를 말합니다. 예를 들어, "happy", "new", "year"는 그룹 단어지만, "aba", "abcabc"는 그룹 단어가 아닙니다. 접근 방법각 단어를 순회하면서 그룹 단어인지 확인, 그룹 단어인지 확인하기 위해서는 이전에 등장했던 문자가 다시 나오지 않는지 체크하면 된다. 풀이 과정각 단어를 순회하면서 문자가 연속적으로 등장하는지 확인합니다.이전 문자를 기록하고, 현재 문자가 이전 문자와 다를 때, 이전에도 등장했던 문자라면 그룹 단어가 아닙니다.문자의 등장 여부를 기록하기 위해 boolean 배열을 사용합니다. 이 배열은 각 문자의..

문제https://www.acmicpc.net/problem/10988주어진 문자열이 팰린드롬인지 확인하는 문제로,  팰린드롬(Palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열을 의미한다. 접근 방법팰린드롬은 첫 번째 문자와 마지막 문자가 같고, 두 번째 문자와 끝에서 두 번째 문자가 같은 식으로 쌍을 이루어야 합니다. 이를 반복하여 문자열의 길이의 절반만큼 비교하면 된다. 풀이 과정입력 받기: 문자열을 입력받습니다.팰린드롬 확인: 문자열의 앞쪽 문자와 뒤쪽 문자를 순서대로 비교합니다.반복문 사용: 반복문을 통해 문자열의 길이의 절반만큼 비교하면서 문자가 다르면 팰린드롬이 아님을 확정할 수 있습니다.결과 출력: 모든 쌍이 일치하면 팰린드롬으로 판단하고 1을 출력, 하나라도 다르면..

문제https://www.acmicpc.net/problem/2346N개의 풍선이 일렬로 나열되어 있고, 각 풍선에는 숫자가 적혀 있습니다. 첫 번째 풍선부터 시작하여 풍선을 터뜨리고, 그 풍선에 적힌 숫자만큼 왼쪽이나 오른쪽으로 이동해 다음 풍선을 터뜨립니다. 모든 풍선을 터뜨릴 때까지 이 과정을 반복합니다.접근 방법Deque를 사용하여 양쪽 끝에서 삽입과 삭제가 가능하기 때문에 풍선을 터뜨린 후 이동하는 작업을 효율적으로 처리할 수 있다. 풀이 과정첫 번째 풍선을 터뜨리고, 그 풍선의 값을 기록합니다.그 값을 기준으로 오른쪽(양수) 또는 왼쪽(음수)으로 이동합니다.이동한 후에 다음 풍선을 터뜨리고, 그 값을 다시 기록합니다.이 과정을 모든 풍선이 터질 때까지 반복합니다. 코드import java.io..

문제https://www.acmicpc.net/problem/18870주어진 좌표들을 압축하여 상대적인 순위를 매기는 문제,주어진 좌표들이 [-10, -5, 2, 3, -10, -5]라면,각 좌표의 상대적인 순위를 계산하여 [0, 1, 2, 3, 0, 1]로 변환하는 것으로데이터의 양이 많아질 때도 효율적으로 처리할 수 있도록 하는 것이 중요하다. 접근 방법원본 좌표를 배열에 저장: 입력된 좌표들을 그대로 배열에 저장합니다.좌표 정렬: 원본 배열의 복사본을 만들어 이를 정렬합니다.좌표 압축: 정렬된 배열을 순회하며, 각 좌표의 순위를 매겨 HashMap에 저장합니다.결과 출력: 원본 배열을 순회하면서, HashMap에서 해당 좌표의 압축된 값을 가져와 출력합니다. 코드import java.io.*;imp..

문제https://www.acmicpc.net/problem/1966여러 문서가 프린터에 들어오면, 중요도에 따라 높은 중요도를 가진 문서부터 출력됩니다. 주어진 문서 리스트에서 특정 문서가 몇 번째로 출력되는지 계산하는 문제입니다. 중요도가 높은 문서를 먼저 출력하며, 특정 문서가 언제 출력되는지 순서를 찾는 것이 목표이다. 접근 방법큐를 활용한 시뮬레이션: 문제에서 제시한 순서대로 문서를 처리하고, 인쇄 순서를 계산합니다. 큐를 이용해 앞에서부터 차례대로 문서를 꺼내고, 중요도가 더 높은 문서가 있으면 현재 문서를 다시 큐의 끝으로 이동시킵니다.목표 문서 찾기: 문서를 인쇄할 때마다 해당 문서가 우리가 찾는 문서인지 확인하고, 찾고자 하는 문서가 인쇄되면 그 순서를 출력합니다. 코드import jav..

문제https://www.acmicpc.net/problem/1021주어진 수열에서 숫자를 하나씩 뽑아내야 하는데, 이때 큐를 왼쪽 또는 오른쪽으로 회전시켜 원하는 숫자를 가장 앞에 놓는 작업을 최소화해야 합니다. 주어진 수열을 순서대로 뽑아내기 위해 큐를 회전하는 최소 횟수를 구하는 것입니다. 접근 방법덱(Deque) 자료구조 사용덱은 큐와 스택의 특성을 모두 갖춘 자료구조로, 양 끝에서 삽입과 삭제가 가능합니다. 이를 통해 큐의 좌우 회전을 쉽게 구현할 수 있습니다.최소 회전 횟수 계산현재 뽑아내려는 숫자의 위치에 따라 왼쪽으로 회전하는 것이 빠를지, 오른쪽으로 회전하는 것이 빠를지 판단합니다.왼쪽으로 회전할 때와 오른쪽으로 회전할 때의 횟수를 비교하여 더 적은 횟수만큼 회전합니다. 코드import ..

문제https://www.acmicpc.net/problem/2304여러 개의 기둥이 주어졌을 때, 이 기둥들을 사용해 만든 창고의 지붕 면적을 구하는 문제입니다. 각 기둥은 위치와 높이로 정의되며, 모든 기둥의 폭은 1입니다. 접근 방법기둥 배열 정렬: 기둥들을 위치에 따라 오름차순으로 정렬합니다.최고 높이의 기둥을 중심으로 면적 계산:왼쪽에서 최고 기둥까지: 왼쪽에서 오른쪽으로 진행하면서 높이가 증가할 때마다 면적을 계산합니다.오른쪽에서 최고 기둥까지: 오른쪽에서 왼쪽으로 진행하면서 높이가 증가할 때마다 면적을 계산합니다.최고 높이의 기둥 면적 추가: 마지막으로 최고 높이의 기둥 면적을 더해줍니다. 코드import java.io.BufferedReader;import java.io.IOExceptio..

문제https://www.acmicpc.net/problem/1417다솜이는 선거에 출마했는데, 자신을 제외한 다른 후보들도 있습니다. 각 후보의 득표 수가 주어졌을 때, 다솜이가 다른 후보들보다 많은 표를 얻기 위해 최소 몇 명의 유권자를 매수해야 하는지 구하는 문제입니다.다솜이가 매수할 때마다 다른 후보의 득표 수는 1씩 감소하고 다솜이의 득표 수는 1씩 증가합니다. 이 과정을 반복해 다솜이가 가장 많은 표를 얻게 하는 것이 목표입니다. 접근 방법우선순위 큐 사용: 다솜이를 제외한 다른 후보들의 득표 수를 관리하기 위해 우선순위 큐(최대 힙)를 사용합니다.매수 과정 반복: 가장 많은 표를 가진 후보를 찾아 매수를 진행합니다. 다솜이의 표가 그 후보보다 많아질 때까지 이 과정을 반복합니다.반복문 종료:..