반응형
문제링크 🚩 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 📕 문제 접근 📕 - init 트리를 만들 때 더하거나 빼거나 곱하는 것이 아닌 현재에서 선택 할 수 있는 최소값을 선택하는 로직만 선택한다면 기존 세그먼트 트리 그대로 활용하여 문제를 해결 할 수 있다. 아래 문제와 매우 유사하니 학습용으로 함께 풀어보면 좋을 것 같다. https://www.acmi..
문제링크 🚩 https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 📕 문제 접근 📕 - 굉장히 난처했던 문제 였다. - 문제 이해가 어려웠는데 정말 간단하게 설명하자면 ababab에서 최대 접미사 접두사의 반복 길이는 abab로 4이다 - 그치만 해당 문제가 요구하는것은 반복되는 문자열이 몇개의 반복으로 이루어져 있냐는 것이였다. - 예를 들면 ABCD의 경우 반복되는 것 없기에 ABCD의 1제곱이다. - 다음..
문제링크 🚩 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 📕 문제 접근 📕 - 해당 문제도 KMP 알고리즘을 사용한다(?). - 개인적인 생각으로는 KMP를 위한 table만 설계하면 끝난다고 생각하여 반쪽짜리 KMP 느낌이 든다. 포인트 1) 광고 문자열은 무한히 반복한다. 2) 무한히 반복하는 문자열 중 일부분만 확인하다. 3) 그광고가 될 수 있는 문자열(무한히 반복하는 문자열)이 가능한 경우 중 가장 짧은 문자열의 길이를 구한다. 문자열에서 접두사..
문제링크 🚩 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 📕 문제 접근 📕 - 가장 이상적인 KMP문제인 것 같다 - 접미사와 접두사가 같은 영역을 찾기 위한 table을 만들고 - 이를 KMP 알고리즘에 대입하여 해결하면 되는 문제다 - KMP 알고리즘은 해당 포스팅에 자세하게 정리해뒀으니 참고 바란다. https://security-gom.tistory.com/36 KMP -JAVA KMP Algorithm : 문자열 검색 알고..
문제링크 🚩 https://programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📕 문제 접근 📕 잘 못 된 접근 : // 모든 수를 낮게 만드는게 이득인가? // 7 -> 1 3 3 -> 18 // 2, 2, 3 -> 4 + 4 + 9 => 17 // 모든 수를 가장 낮게 만드는게 이득 // 배열을 순회하기에는 시간이 부족함 // 그럼 어떤 방법으러 해결해야하는가? // 전부다 더하고 n을 빼고 수를 나눈다면? => 문제 발생 그럼 2, 1, 2 에 n이 1 인경우 4가..
문제링크 🚩 https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📕 문제 접근 📕 110이 생기면 최대한 앞으로 뽑아내는 로직을 생각했다. 원래 문자에 110이 존재하지 않는다면 원본 그대로 저장하고 존재한다면 마지막 0뒤에 110을 찾은 수 만큼 넣는 로직을 생각하였다. 💻 Code 💻 **import java.util.Stack; class Solution { public String\[\] solution(String\[\] s) { St..