6-6화이탱

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 1. 들어오는 순서대로 스택에 값이 있다면 높이를 비교한다. 2. 스택에서 peek한 높이가 더 높을 경우에는 해당 값이 수신하는 건물이 된다. 3. 더 낮을 경우에는 이 건물의 영향을 받지 않을 것이기 때문에 pop한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 다른 N과 M 시리즈의 문제 푼 방법에다가 만족하는 수열을 담을 LinkedHashSet을 추가하면 된다! LinkedHashSet은 순서가 보장되고 중복은 허용하지 않는다. LinkedHashSet에 만족하는 수열을 넣고, 마지막에 이들을 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 현재까지는 N과 M 시리즈를 1~8까지 풀었는데, 다 비슷한 문제들이기에 1이랑 8을 기록해본다! 이 문제도 dfs로 해결하였다. n까지 포문을 돌면서 입력받은 값의 i번째 값을 첫번째로 선택한 값으로 한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net dfs를 사용하여 문제를 풀 수 있었다. 방문 여부를 확인하여 숫자를 뽑아서 배열에 넣고, m개를 뽑았을 경우에는 StringBuilder에 append한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net DFS를 사용하여 해결할 수 있었다. 1->3->1 , 5->5 와 같이 2번째 값과 1번째 값이 이어지는 것들을 찾으면 된다. 1. 배열에 2번째 줄 입력 값을 넣는다. 2. 이어지는 것들을 넣을 arryList, 방문 확인할 배열을 선언한다. 3. 첫번째부터 포문을 돌려서 방문을 표시하고, 해당 인덱스(첫번째 줄 값)을 2번째 줄 값으로 갖고 있는 애들을 확인한다. import j..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 최단 시간을 구하는 문제로 최단 거리를 구하는 bfs를 이용하여 문제를 풀었다. 큐에 지훈이 정보, 불의 정보를 넣었다. Node 객체를 생성하여 좌표와 카운트, 지훈인지 불인지 구분하는 name을 필드로 가지게 했다. 1. 불 이동 -> 지훈 이동 2. 방문했던 위치인지 확인 3. 동서남북으로 포문 돌려서 벽과 불이 아닐 경우에는 세가지의 작업을 한다. 1)해당 좌표의 값을 바꾸..

https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net ArrayList에 넣어서 비교하면 되는 문제였다. 포문에서 char배열로 변환한 후 비교했었는데 이러면 메모리 초과가 발생되었다 .. charAt으로 해당 인덱스로 잘라서 비교함으로써 해결~~~ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Ma..

https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net a의 갯수를 세어서 그 갯수만큼의 범위를 돌면서 b의 최솟값을 찾으면 된다! aaaabbbbba 인 경우에는, a가 5개 이므로 시작 지점을 0~9(문자열 길이 10) 범위는 5 1) aaaab -> 1개 2) aaabb -> 2개 3) aabbb -> 3개 4) abbbb -> 4개 5) bbbbb -> 5개 6) bbbba -> 4개 7) bbbaa -> 3개 8) bbaaa -> 2개 9) ba..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net DFS를 사용해서 맨 첫 여행지부터 시작해서 방문가능한 곳들에 대한 확인을 한다! 여행계획대로 포문을 돌려서 방문 가능한지 본다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokeni..

https://www.acmicpc.net/problem/24337 24337번: 가희와 탑 일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다. www.acmicpc.net 구현 문제로, 풀이법을 생각해내기 꽤 어려운 문제였다... 1. 건물의 최고 높이는 a와 b중 큰 값이다. 2. 디큐를 생성하여 a-1만큼의 오름 차순 + 최고 높이 건물 + b-1만큼의 내림차순으로 먼저 add 한다! 3. 다 add 한 후에 디큐 사이즈가 n보다 크다면, 건물 정보가 나올 수 없는 것이기에 -1을 출력한다!! 4. 여기까지 진행하면 아래와 같은 경우가 발생된다. 입력 9 1 5 -..