본문 바로가기

알고리즘 풀이

 (84)
[백준] 10986번: 나머지 합 - JAVA 🔗 문제 링크 BOJ 10986번: 나머지 합 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 📝 풀이 과정 연속된 구간의 합이기 때문에 누적합 방법으로 문제를 풀이해야 한다. 배열의 연속 구간의 합은 $sum[j] - sum[i]$로 구할 수 있는데, 이 합의 M으로 나눈 나머지가 0인 순서쌍을 구해야 한다. $(sum[j] - sum[i]) \% M = 0$이 되고, 모듈러 연산은 분배가 가능하기 때문에 $sum[j]\%M - sum[i]\%M = 0$ 따라서..
[백준] 1072번: 게임 - JAVA 🔗 문제 링크 BOJ 1072번: 게임 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1️⃣ 이분 탐색 📝 풀이 과정 새로운 게임을 하게 되면 계산되는 확률은 $((y+횟수) \times 100) / (x + 횟수)$ 따라서 해당되는 횟수가 최소로 증가할 때 확률의 값이 변하는 경우를 찾으면 된다. 주어진 게임의 2배만큼 진행했는데도 확률이 변하지 않았다면 더이상 변하지 않기 때문에, 0부터 최고 1,000,000,000번 진행했을 때까지 이분탐색을 통해 값을 찾을 수 있다. 💡 부동소수점 오차 변수..
[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 가사 검색 programmers.co.kr 1️⃣ Trie 📝 풀이 과정 words의 길이는 100,000개, queries의 길이는 100,000개로 단순 탐색시 시간 초과가 발생한다. 다음으로 생각한 풀이는 Trie를 사용하는 방법이었다. words를 모두 Trie에 insert한 다음 queries를 통해 문자열을 검색할 때, 삽입된 문자열의 길이를 모른다면 탐색하기 어렵다. 때문에, Trie의 노드마다 lenMap을 생성하였다. key는 삽입된 문자열의 길이고, value는 해당 길이의 문자열의 개수를 가지고 있다. 따라서 Trie의 node 위치에 도달했을 때, 해당 노드까지 도달..
[프로그래머스] 자물쇠와 열쇠 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 자물쇠와 열쇠 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 📝 풀이 과정 열쇠를 자물쇠에 맞게 움직이며 비교하면서 답을 찾는 문제이다. 열쇠는 자물쇠를 벗어나게 대볼 수 있기 때문에 자물쇠를 기준으로 -M ~ +N까지의 범위로 비교해볼 수 있다. 만약 자물쇠가 모두 1(돌기)인경우까지 생각해 열쇠를 아예 벗어나게 대보는 경우도 고려했다. 함수에 y, x를 전달하고 해당 범위만큼 열쇠를 자물쇠에 대보는 연산을 수행한다. 예를 들어 (-2, -1)만큼 벗어나게 대본다고 가정..
[프로그래머스] 괄호 변환 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 괄호 변환 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 📝 풀이 과정 문제만 이해하면 그대로 구현하면 되는 문제이다. () => 균형잡힌 괄호 문자열(O), 올바른 괄호 문자열(O) )( => 균형잡힌 괄호 문자열(O), 올바른 괄호 문자열(X) )(( => 균형잡힌 괄호 문자열(X), 올바른 괄호 문자열(X) 균형잡힌 괄호로 나눠주기 위해 '('는 +1, ')'는 -1로 계산하며 값이 0이 되면 균형잡힌 괄호로 판단하고 ..
[프로그래머스] 문자열 압축 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 문자열 압축 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 📝 풀이 과정 길이 순으로 실제 압축을 구현해 가장 작은 길이를 반환하는 문제이다. 길이는 1부터 문자열 길이의 절반까지 가능한데, 어차피 문자열의 길이의 절반 이상으로 압축을 시도해도 같은 문자열을 반복할 수 없기 때문이다. 이후, 반복문을 돌며 앞의 문자열과 같은 문자열이라면 cnt를 증가시켜주고 아니라면 반복문을 탈출해 실제 문자열이 아닌 길이만 알면 ..
[프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 📝 풀이 과정 단순 시뮬레이션으로 구현할 수도 있지만 그렇게 하면 효율성을 통과하지 못하기 때문에 아이디어가 필요하다. 5, 2, 10 => 2, 5, 10 2, 5, 10 => 0, 3, 8 => 0, 0, 5 음식의 시간순으로 오름차순 정렬을 하고, 남은 시간을 크기 순으로 한 번에 제거하면 그만큼 시간을 줄일 수 있게 된다. while (idx k) break; k ..
[프로그래머스] 매칭점수 / 2019 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 매칭점수 / 2019 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀 programmers.co.kr 📝 풀이 과정 다소 복잡하지만 문제에 주어진 그대로만 구현하면 되는 문제다. 자바에서 정규식 처리를 쉽게 할 수 있도록 만든 Pattern과 Matcher를 사용하여 구현하였다. (참고: [Java] Pattern, Matcher Class 사용법과 메소드 정리) Pattern urlPattern = Pattern.compile("[\\s\\S]*]*content=\"(..

티스토리툴바