매일 조금씩

문제 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의 top을 체크하면서 현재 원소보다 작으면 pop을 해준다. (현재 원소 보다 큰 값이 나올때까지) 이후 Stack이 empty 상태라면 현재 원소보다 큰 수가 없는 것이므로 -1을 저장 Stack의 사이즈가 1이상이라면 Stack의 top이 현재 원소의 오큰수이므로 저장한다. 마지막으로 현재 원소를 Stack에 ..

문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 아래 문제랑 비슷한데, 해당 문제는 플로이드 와샬 알고리즘을 이용해 푸는게 가능하다. 2021.10.31 - [Problem Solving/Programmers] - [프로그래머스] 합승 택시 요금 (Java) [프로그래머스] 합승 택시 요금 (Java) 문제 https://programmers.co.kr/learn/courses/30/lessons/7..

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1,..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 PriorityQueue를 사용하면 된다. Comparator로 정렬 조건을 명시해주었다. 소스코드 package heap; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; impo..

문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 PriorityQueue로 풀면 된다. PriorityQueue는 정수형의 경우 기본정렬이 오름차순이므로 따로 Comparator를 만들어줄 필요는 없다. 소스코드 package heap; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; impo..

문제 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 예시 1) hat headgear sunglasses eyewear turban headgear headgear의 경우의 수: 3 (hat을 쓴다, turban을 쓴다, 안 쓴다) eyewear의 경우의 수: 2 (sunglasses를 쓴다, 안 쓴다) 3*2 = 6 모두 안쓸 경우 알몸이므로 ..

문제 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 풀이 큰 링의 반지름과 나머지 링 반지름의 최대 공약수를 각각 구하여 나눈다. 유클리드 호제법을 사용한다. 소스코드 package math; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokeni..

문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 풀이 ex) 24의 약수 2 3 4 6 8 12 2*12 = 3* 8 = 4*6 = 24 어떤 수의 모든 약수가 주어졌 때는 약수의 최소값과, 최대값을 곱하면 해당 수를 구할 수 있다. 소스코드 package math; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringToken..

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 Greedy알고리즘을 사용해 풀 수 있는 문제이다. 무조건 싼 기름을 채워넣으면 해결할 수있다. 1번 도시 -> 2번도시 1번 도시의 1리터 당 주유비용은 5원이며 1번과 2번도시 간 거리는 2이다. 1번 도시에서는 무조건 주유를 해야 한다. 총비용 = 5*2 = 10 2번 도시 -> 3번 도시 2번 도시에서 3번 도시로 가기 위해 기름을 주유해야 하는데 1번 도시에서 미..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 마이너스 기호가 한 번이라도 나온다면 그 뒤에 나오는 숫자는 모두 음수로 더해질 수 있다. 5+10-(20+30+50)-(20+30) 단 초항은 양수이므로, -가 처음 나오기 전까지의 숫자는 양수로 더해져야 함 5+10-(20+30+50)-(20+30) 5+10 은 양수로 더하고 나머지 숫자는 음수로 더하여 합계를 내면 된다. 만약 - 기호가 없다면 모두 양수이므로 모든 숫자를 더..