java
-
[백준 1213번] 팰린드룸 만들기(Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 4. 14:27
백준알고리즘 1213번 : 팰린드룸 만들기 팰린드롬이란 회문, 즉 거꾸로 읽어도 같은 말이 되는 단어 혹은 문장을 말한다. 단어가 주어졌을 때 사전순으로 앞서는 팰린드롬을 만들고, 만들 수 없다고 판단되면 오류 메시지를 출력하는 문제이다. 단어가 홀수인 경우와 짝수인 경우로 나누어 풀었다. 풀이 과정 1. 사전순으로 출력되게 해야하므로, 배열을 받아 정렬한다. 2. 짝수인 경우에는 for문을 돌며 i번째와 i+1번째를 비교하여 StringBuilder로 append함과 동시에 Stack에 push를 하고 두 문자가 다른 경우에는 즉시 오류 처리하며 종료하도록 했다. 오류 처리가 되지 않은 경우에는 append한 String 값에 stack을 pop하여 단어를 추가 append하여 출력하도록하였다. 3. ..
-
[백준 2847번] 게임을 만든 동준이(Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 1. 00:44
백준알고리즘 2847번 : 게임을 만든 동준이 받아온 값들을 동일한 점수가 없는 오름차순으로 만드는 문제이다. Greedy Algorithm 응용 문제를 하면서 정렬을 수행하는 것에 익숙해졌는지 냅다 정렬을 하는 실수를 범했다. 순서대로 배열로 받아 가장 마지막부터 탐색하며 깎아야 하는 숫자를 count하여 풀 수 있었다. 풀이 과정 1. 점수들을 레벨의 수 N만큼 배열로 받는다. 2. 배열을 뒤에서부터 탐색한다. 하위 level의 점수가 상위 level의 점수보다 크면 해당 점수를 깎아서 기준 점수를 재정의한다. 3. 깎은 점수의 총 합을 출력한다. 소스 ▽ 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..
-
[백준 1202번] 보석 도둑(Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 28. 16:47
백준알고리즘 1202번 : 보석 도둑 시간 초과와 RunTime Error를 반복한 끝에 성공했다. 우선순위큐(Priority Queue)의 중요성을 배운 문제이다. 이중for문(혹은 for문과 while문)을 사용하게 된다면 최대 30만*30만의 시간복잡도가 발생하게된다. 따라서 가방의 최대 무게외 보석의 정보 배열을 정렬했다고 하더라도 시간 제한이 걸리는 testCase가 발생하기 때문에.. 이 방식은 한 번 해보고 빠르게 접었다. 우선순위큐의 장점은, 내가 add한 Queue 중 최대값(혹은 최소값)을 poll할 수 있다는 점이다. 이는 인자들을 꾸준히 더하거나 빼야하는 상황이나 (특정 가방이 들수 있는 보석들을 모두 담고, 하나의 보석만 빼고 남겨둬야한다.) 인자들의 최대, 최소값을 구해야하는 상..
-
[백준 1543번] 문서 검색(Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 23. 13:39
백준알고리즘 1543번 : 문서 검색 문서내에 특정 단어가 몇번이나 등장하는지 출력하는 문제이다. 처음에는 이중 for문을 사용하지 않고, 단일 for문을 이용하여 첫 글자부터 하나씩 check한 뒤에 한 글자라도 틀리면 다시 첫 글자부터 돌아가서 check하는 방식을 취했는데, 이러한 방식에는 문제가 있었다. 예를들어 단어의 길이가 길고, 뒷부분에서 틀린 글자가 발견되어 다시 첫글자부터 count를 하게되면, 문서내에 해당 단어의 패턴이 있었다고 하더라도 count를 못하게되어 찾지 못하는 불상사가 일어나게 된다. 예시로 abaabaa abaa 가 그렇다. 따라서 문서의 길이와 단어의 길이의 최댓값을 고려해도 이중 for문으로 풀어도 괜찮겠다 싶어 푸는 방식을 변경하였다. 풀이 과정 1. 이중 for문..
-
[백준 1449번] 수리공 항승 (Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 22. 16:39
백준알고리즘 1449번 : 수리공 항승 필요한 테이프의 갯수를 출력하는 문제이다. 어차피 구멍을 왼쪽부터 정렬하게되면, 무조건 왼쪽부터 커버해야하기 때문에 문제가 한결 쉬워질 것이라고 판단했다. 풀이 과정 1. 구멍의 위치를 오름차순으로 정렬한다. 2. 남아있는 테이프의 위치(왼쪽 끝, 오른쪽 끝)를 확인하고, 앞, 뒤를 다 커버가능한지 매번 체크하도록 한다 3. 커버가 불가능하다면 테이프 갯수를 하나 더 늘이고, 테이프가 커버할수 있는 위치를 초기화한다. 소스 ▽ 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.u..
-
[백준 1080번] 행렬 (Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 18. 16:44
백준알고리즘 1080번 : 행렬 예제에서 유추할 수 있듯 3x3크기의 부분행렬을 한번에 바꾸기 때문에 그보다 작은 행렬이 문제로 나온다면 다를 경우 -1, 같을 경우 0을 출력하는 것으로 판단할 수 있다. 문제는 3x3이상의 행렬인데, 이 경우에는 부분행렬중 좌측 최상단의 값만 이용하여 비교하는 식으로했다. 좌측 상단에서 우측 하단으로 탐색하면 언제나 좌측 최상단의 값은 해당 탐색 이후로는 변경할 수 없는 값이된다. 이를 바탕으로 행렬 A와 행렬 B의 좌측 최상단의 값만 비교하고, 같으면 다음 탐색으로 pass, 다르면 최상단을 포함한 3x3크기의 부분행렬을 모두 바꾸어주는 방식으로 전개한다. 메소드를 더 다양하게 사용했더라면 코드 길이는 훨씬 줄었을 문제이다. 그래도 소요시간 자체는 오래걸리지 않았다...
-
[백준 1744번] 수 묶기 (Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 18. 14:44
백준알고리즘 1744번 : 수 묶기 문제에 대한 대략적인 설명 곱하거나 더함으로써 정수 집합의 최댓값을 만들어 내는 문제이다. 처음에는 집합을 하나의 배열로 만들어 정렬한다음에 양의 정수와 그렇지 않은 정수로 구분하여 계산해주려고 했다. 그러나 그렇게 되면 배열을 어디서부터 끊어야할지 계산하는 것이 너무 복잡하여(집합의 길이가 짝수냐, 양수의 갯수가 짝수냐 등등..) 고민끝에 ArrayList로 양의 정수와 0이하의 정수를 구분하여 받아 정렬해주었다. 이렇게 되면 편한점은, 각 ArrayList들끼리만 정렬을 한뒤에 최댓값을 셈해주고, 남은 것들을 계산해주면 된다. 음의 정수는 작은 숫자들끼리 곱할수록 더 큰 정수를 만들수 있고(-11)*(-10) > (-5)*(-4), 양의 정수는 말할것도 없기 때문이..
-
[백준 1049번] 기타줄 (Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 15. 20:54
백준알고리즘 1049번 : 기타줄 필요한 기타줄을 사기위해 얼마의 돈을 필요로 하냐 묻는 문제이다. 약간의 특이사항이 있다면, 가격이 최소가 되는 선에서 구매한다는 가정하에, 필요한 기타줄의 갯수 이상으로 기타줄을 구매해도 된다는 점이다. 패키지 가격과 낱개의 가격을 브랜드별로 나눌 필요는 없다. 둘 사이의 연관관계가 전혀 없기 때문이다. 따라서 패키지 가격의 최솟값과 낱개 가격의 최솟값만 구해준 뒤, 적절한 조건문을 사용하여 계산하도록 해주었다. 풀이 과정 1. 패키지 가격과 낱개의 가격을 받아 각 가격의 최솟값을 산출 2. 패키지 가격이 낱개 가격에 6을 곱한것 보다 저렴한가? 등등의 조건문을 통해 정답을 산출 소스 ▽ 더보기 import java.io.BufferedReader; import jav..