728x90 전체 글250 [백준] 12015번 : 가장 긴 증가하는 부분 수열2(JAVA) https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 처음수로 0을 주어지고 count로 위치를 1로 지정합니다. count - 1보다 수가 클경우 count위치에 값을 넣고 증가시킵니다. 아닐 경우 value의 위치를 구하고 그 위치에 값으 value로 변경해줍니다. 소스코드 ArrayList + 이분 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.In.. 2021. 9. 9. [백준] 14925번 : 목장 건설하기(JAVA) https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 풀이 1이나 2가 아닌 0이 있을 때 농장을 지을 수 있습니다. 정사각형을 지을 수 있으면 그자리에 +1해서 사이즈를 추가해줍니다(dp) -1,0부분, 0,-1부분, -1,-1부분 중 가장 작은 수를 구한후 +1을 시켜 가장 큰 정사각형을 구할 수 있습니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.. 2021. 9. 8. [백준] 4396번 : 지뢰 찾기(JAVA) https://www.acmicpc.net/problem/4396 4396번: 지뢰 찾기 첫 번째 줄에는 10보다 작거나 같은 양의 정수 n이 입력된다. 다음 n개의 줄은 지뢰의 위치를 나타낸다. 각각의 줄은 n개의 문자를 사용하여 한 행을 나타낸다. 온점(.)은 지뢰가 없는 지점이며 별 www.acmicpc.net 풀이 두번째로 입력받은 배열에 0이 들어가 있으면 그 위치 주위에 폭탄이 있을시 그 갯수를 추가하여 만들면 된다. ※ 0인 위치에 폭탄이 있을 경우 게임에 실패한걸로 간주되어 *의 위치 전부에 *를 추가하면된다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; pub.. 2021. 9. 5. [백준] 22999번 : K-Goodness String(JAVA) https://www.acmicpc.net/problem/22999 22999번: K-Goodness String For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of operations required to transform the given string S into a string with goodness score equal to K. www.acmicpc.net 풀이 입력받은 문자를 앞뒤 1글자씩 비교하면서 다를경우 ++한 후 주어진 k랑 비교하였을때의 차이를 출력하면 됩니다. ※ 주의 : 절대값을 출력.. 2021. 9. 1. [백준] 1662번 : 압축(JAVA) https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 풀이 일단 String을 계속 선언하면서 하면 최종적으로 메모리초과가 뜹니다. 문제는 최종 문자열을 출력하는게 아닌 문자열의 길이를 출력하는거니 길이체크만 해주면 되서 long으로 해주면됩니다. stack을 활용하여 )가 나올 시 (까지 count를 세줍니다. 여기서 *(count를 세준 후 나온 값을 *과함께 넣어줌)이 나올 경우 그값을 그대로 더해줍니다. 아닌경우 +1 소스코드 impor.. 2021. 8. 30. [백준] 12904번 : A와 B(JAVA) https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 문자 2번을 1번이 되도록 하면서 풀면 됩니다. 1번문자에서 2번문자가 될려면 A나 B를 1개 무조건 추가하는 식이므로, 반대로 2번에서 1번이 될려면 A나 B를 빼줍니다. 대신 B를 뺄려면 문자를 뒤집어줘야한다. 1번문자와 2번문자의 길이가 같을 때, 문자가 서로 같으면 1, 아니면 0을 리턴하는 함수를 작성합니다. 소스코드 import java.io... 2021. 8. 27. [백준] 1701번 : Cubeditor(JAVA) https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 풀이 기존 kmp알고리즘을 이용하여 이중 for문으로 substring으로 할 시 HashSet을 써도 메모리초과가 납니다. kmp알고리즘에서 사용되는 함수 중 getpi만을 이용하여 하시면 됩니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream.. 2021. 8. 26. [백준] 1786번 : 찾기(JAVA) https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 풀이 기존 KMP알고리즘에서 달라진 부분은 같은 부분이 나올때 count를 세주고 위치를 저장해서 마지막에 출력해주는 부분입니다. ArrayList를 통하여 위치를 저장해주고 count를 선언하여 ++해줍니다(전역) 여기서 StringBuilder를 써주냐 안써주냐의 차이로 시간이 2500ms 가량이 차이납니다(확실 x) 소스코드 import java.io.BufferedReader; imp.. 2021. 8. 26. [백준] 16916번 : 부분 문자열(JAVA) https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 풀이 KMP와 문자열문제입니다.(KMP를 안다면 바로 풀 수 있는 문제) 먼저 getpi()함수를 통하여 맞추고자 하는 글자의 중복위치를 체크해줍니다. KMP()함수를 통하여 처음 문자열과 두번째 문자열을 1글자씩 비교합니다. 비교하면서 같을 경우 위치(j)를 증가시켜주고 j가 0보다 크고 서로 다를경우 맞는 위치까지 내려가기 위해 while문으로 j를 줄여줍니다. for문이 끝날때까지 없다면 0, j가 두번째 문자열의 길.. 2021. 8. 26. 이전 1 ··· 18 19 20 21 22 23 24 ··· 28 다음 728x90