본문 바로가기
728x90

코딩테스트

[백준] 2467 용액 / 자바(Java) 문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 해설 정렬되어 있는 수들 중 2개의 값의 합이 가장 0에 가까운 수의 조합을 찾는 문제이다. 모든 수의 조합을 확인하려면 100,000 * 99,999가 되어 너무 많은 조합을 확인해야하므로 배열에서 2개의 포인터를 사용해 원하는 조건에 맞춰 확인하는 방식을 사용한다. 입력값은 오름차순으로 정렬되어 있으므로 입력을 배열로 변경한다면 왼쪽에는 가장 작은 수, 오른쪽에는 가장 큰 수가 있을.. 더보기
[백준] 1759 암호 만들기 / 자바(Java) 문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해설 모든 가지수를 정렬된 순으로 확인해야하는 문제이므로 브루트포스를 조합을 사용해 해결한다. 조건들이 간단한 조합문제보다 더 다양함으로 이에 주의한다. 조건 최소 하나의 모음과 두개의 자음으로 구성 알파벳들은 정렬되어있음 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im.. 더보기
[백준] 2170 선 긋기 / 자바(Java) 문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 해설 입력값의 범위가 넓어 정렬이 필요하지만 양이 너무 많아 우선순위큐를 통해 문제를 해결한다. 우선순위큐에 넣을 때 NlogN번, 하나씩 빼면서 답을 계산할때 N번으로 총 O(NlonN)만큼의 시간복잡도로 해결이 가능하다. 주의점 입력 값의 범위가 너무커 Long타입을 사용한다. 코드 import java.io.BufferedReader; import jav.. 더보기
[백준] 1074 Z / 자바(Java) 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 해설 Z형태가 반복되는 형상에 재귀 및 분할정복이 필요하다 생각들었습니다. findz 함수를 통해 각 단계별로 r,c가 어느 사분면에 존재하는지를 구하고 그 단계의 사각형의 크기를 통해 그 사분면의 첫 숫자의 크기만큼 더해주어 마지막으로 사각형의 크기가 1인 경우에는 해당 사각형의 탐색 순서를 구할 수 있도록 하였습니다. 주의점 각 사분면단위로 계산하기 때문에 범위를 잘 판단해야한다.. 더보기
[백준] 1309 동물원 / 자바(Java) 문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 해설 dfs와 같은 탐색으로 해결하기에는 N의 길이가 너무 길다(답을 9901로 나눈 나머지를 출력하라는 부분도 값이 크게 되리라는 예상이 된다) 따라서 DP를 사용해 이전의 경우의 수에서 가능한 가능성을 구하는 점화식의 형태로 문제를 해결한다. arr[i][j]에서 i 는 사자우리의 세로번째의 수, j는 0~2까지 각각 사자가 들어가지 않는 경우, 왼쪽칸에 들어간경우, 오른쪽 칸에 들어간 경우를 나타내어 arr[i][j]는 i번째에 각 가능성이 될 경우의 수가 들어가게 된다. 사자우리는 바로 이전 번째에서만 영향을 받아 a.. 더보기
[백준] 1013 Contact / 자바(Java) 문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 해설 문제에서부터 정규표현식을 사용해줌으로써 자바의 String 내부에 있는 정규표현식을 사용해 쉽게 해결할 수 있었습니다. 유사한 문제에 대한 접근법으로 정규표현식을 사용할 수 있음을 알아 학습하는 계기가 되었습니다. 주의점 정규 표현식을 써보자 코드 import java.io.BufferedReader; import java.io.IOException; import java.i.. 더보기
[백준] 17298 오큰수 / 자바(Java) 문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 해설 오큰수는 수열에서 특정 숫자보다 오른쪽에 있는 수 중 큰 가장 가까운 수이다. 들어오는 값의 순서를 유지하고 오큰수가 정해진 수에 관여하지 않기 위해 stack을 사용한다. 앞에 있는 값부터 순서대로 stack에 넣으면 stack에는 값이 역순으로 들어가게 됩니다. 그러다 오큰수에 해당하는 stack의 peek값보다 큰 수가 들어온다면 stack에서 그 값을 pop해주고 오큰수로 배열에 저장해 주.. 더보기
[프로그래머스] 주차 요금 계산 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 차량별 주차요금을 차량번호가 작은 순으로 출력하는 문제입니다. 문제의 조건을 잘 보고 사용가능한 자료구조와 분기를 파악하여 구현하면 해결가능합니다. 1. 데이터 정리 문제의 조건을 읽어보면 차량을 총 주차시간을 기준으로 요금을 측정하기 때문에 입력 데이터를 가공하기 쉽도록 String값을 Int배열로 바꾸고 차량번호순 오름차순으로 정렬, 같다면 시간 순으로 정렬하여 값을 변경했습니다. .. 더보기
728x90

티스토리툴바