[백준] 9202: Boggle [Java]
알고리즘 분류: 트라이, 백트래킹문제 링크: https://www.acmicpc.net/problem/9202 【 문제 】 4*4 격자판에 알파벳들이 주어지면, 각 문자에서 8방 탐색을 해 문자열을 구성하고, 그 문자열이 찾고자 하는 문자열 리스트에 들어있는지 여부에 따라 총 점수, 가장 긴 문자열, 찾은 문자 개수를 갱신하는 문제이다.주의해야할 점은 같은 위치의 문자를 두 번 이상 사용할 수 없다(다시 방문할 수 없다)는 것, 이미 찾은 문자열에 대해서는 점수를 올리거나 문자 개수를 올리지 않는다는 점이다. 【 풀이 】찾아야 할 단어 목록을 트라이로 구성.이때 트라이 노드에 단어의 끝을 나타내는 문자인 `*` 을 넣어줬다격자판에서 인접한 문자를 고르면서 문자열을 조합해내야 하기 때문에 DFS로..
[백준] 28422: XOR 카드 게임
알고리즘: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/28422 28422번: XOR 카드 게임 XOR 카드 게임이란 $N$장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다. 한 www.acmicpc.net 【 문제 】 주어진 카드 n장 중 2장 혹은 3장을 카드가 0장이 될 때까지 뽑는다. 뽑은 카드에 적힌 숫자들을 XOR 연산한 뒤, 2진수 값으로 변환시켜 1의 개수를 구하고 점수로 더한다. 마지막에 1장의 카드가 남을 경우 최종 점수가 0점이 된다. 이때 점수의 최댓값을 구하는 문제. 【 풀이 】 1비트의 개수를 구하는 함수를 정의한다...
[프로그래머스] 연속 부분 수열 합의 개수 [Java]
알고리즘 분류: 해시맵, 누적합, 완전 탐색 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 【 문제 】 정수로 이루어진 배열이 주어졌을 때 이를 원형 리스트로 간주한다. 이때, 서로 다른 연속 부분 수열의 합의 개수를 구한다. 【 풀이】 첫 for 루프에서 연속 부분 수열의 요소 개수를 정한다. 두 번째 for 루프에서 부분 수열의 첫 요소를 제거하고, 다음 요소를 추가하면서 누적 합을 계산한다. 이때 그 누적합을 map에 저장..
[LeetCode] 205. Isomorphic Strings [Java]
알고리즘 분류: 해시맵 문제 링크: https://leetcode.com/problems/isomorphic-strings/description/ 【 문제 】 두 문자열 s와 t가 주어졌을 때, 두 문자열의 형태가 같은 지 판단하는 문제이다. 【 풀이】 s의 각 문자 위치에 해당되는 t의 문자를 map에 저장한다. 이미 저장된 문자가 다른 문자와 매핑되어 있다면 false를 반환한다. t의 문자가 이미 다른 문자에 매핑되어 있다면 false를 반환한다. 시간 복잡도: O(n) 공간 복잡도: O(n) 【 코드】 public class LeetCode_205 { public boolean isIsomorphic(String s, String t) { Map map = new HashMap(); for (in..
[프로그래머스] 야근 지수 [Java]
알고리즘 분류: 우선순위 큐, 구현, 시뮬레이션 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 【 문제 】 야근 피로도는 works 배열 각 요소들의 제곱의 합이다. 주어진 n을 통해 works 에서 주어진 각 일들의 작업량을 1씩 줄일 수 있다. 이때, 야근 피로도를 최소로 줄였을 때의 그 야근 피로도를 반환하는 문제이다. 【 풀이 】 가장 작업량이 많은 일을 먼저 처리하는 것이 이득이다. 따라서 works 배열을 내림차순으로 ..
[LeetCode] 125. Valid Palindrome [Java]
알고리즘 분류: 문자열, 파싱 문제 링크: https://leetcode.com/problems/valid-palindrome/description/ 【 문제 】 주어진 문자열이 팰린드롬(가운데를 기준으로 양쪽이 동일한 문자열)인지 확인하는 문제이다. 대소문자를 구분하지 않으며(모두 소문자로), 영문자와 숫자만을 대상으로 한다. 【 풀이 】 문자열을 순회하며 영문자와 숫자만을 StringBuilder에 추가한다. (Character 인터페이스의 isLetterOrDigit 메소드 사용) StringBuilder의 처음과 끝부터 비교하며 팰린드롬 여부를 확인한다. 시간 복잡도: O(n) 공간 복잡도: O(n) 【 코드 】 public class LeetCode_125 { public boolean isPa..
