해시셋

[백준] 16940. BFS 스페셜 저지 (Java)

문제 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 알고리즘 그래프, 너비 우선 탐색(BFS), 해시셋 풀이 다음 그래프에 대해 (1 2 3 4 5 6 7 8 9 10 11 12) 라는 방문 순서가 있다면 다음과 같이 판별할 수 있다. 시작 노드인 1이 3개의 인접 노드를 가지고 있으므로 다음 3개의 수(2~4번째)는 1의 인접 노드이어야한다. 그 다음 노드인 2가 2개의 인접 노드를 가지고 있으므로 다음 2개의 수(5~6번째)는 2의 인접 노드이어야한다. ... 모든 노드가 위 조건을 만족하면 올바른 순서임을 알 수 있다. 표로 나타내면 다음과 같다. 빨간색 숫자가 검사할 숫자 파란색 숫자가 그의 인접한 노드가 위치해야하는..

[프로그래머스] 후보키 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 브루트포스, 해시셋 풀이 1개의 키부터 8개의 키를 사용하는 조합을 만들어 모든 경우의 수를 탐색한다. (2^8 = 255 가지) 하나의 조합을 만들었다면 유일성과 최소성을 둘 다 만족하는지 확인하여 만족한다면 answer를 1 증가시킨다. 유일성 확인 키로 사용할 속성들을 "-" 로 연결하여 해시셋에 저장하여 중복된 값이 있는지 확인한다. 예를 들어 예제 입력 1에서 학번, 이름을 키로 사용한다면 "100-ryan", "200-apeach", "300-tube", "400-con", "500-..

[프로그래머스] 숫자 카드 나누기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 해시셋 풀이 arrayA, arrayB 가 오름차순으로 정렬되어있다고 가정하고 문제를 풀었다. 1. arrayA의 제일 작은 원소(0번째 원소)의 약수를 구해 해시셋 cdA에 삽입한다. 2. arrayA의 원소들이 cdA로 나누어떨어지지 않는다면 제거한다. 3. arrayB의 원소들을 모두 나눌 수 없는 cdA의 원소 중 최댓값을 구한다. arrayB에 대해서도 마찬가지 작업을 하여 최댓값을 구하고, 두 값 중 최댓값을 반환한다. 약수 빠르게 구하기 약수를 구할 때 1부터 i 값까지 탐색하며 찾..

[프로그래머스] 택배상자 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 큐, 스택, 해시셋 풀이 택배를 옮기는 흐름은 다음과 같다. 1. 원하는 택배가 기존 컨테이너 벨트에 있다면 원하는 택배를 찾을 때까지 기존 컨테이너 벨트의 택배들을 보조 컨테이너에 담는다. 2. 원하는 택배가 보조 컨테이너 벨트에 있다면 (1) 보조 컨테이너 벨트의 맨 앞에 있다면 꺼낸다. (2) 보조 컨테이너 벨트의 맨 앞에 있지 않다면 더 이상 작업을 진행할 수 없다. 이를 구현하기 위해 1부터 순서대로 올려져있는 기존 컨테이너 벨트는 큐를 기존 컨테이너에서 옮긴 역순으로 올려져있는 보조 ..

[프로그래머스] 연속 부분 수열 합의 개수 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 해시셋 풀이 elements의 각 원소를 시작으로 elements의 원소 개수만큼 누적하며 그 값을 해시셋에 삽입한다. 해시셋은 중복을 허용하지 않기 때문에 탐색이 끝난 후 해시셋의 원소 개수가 답이 된다. * 인덱스를 elements의 원소 개수로 나머지 연산해 범위를 벗어나지 않게 한다. 코드 import java.util.*; class Solution { public int solution(int[] elements) { Set set = new HashSet(); for(int i=0; i

[프로그래머스] 등산코스 정하기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 다익스트라, 해시셋 풀이 어떤 산봉우리로 가는 코스가 최소 intensity를 갖는 코스라면 역방향으로 그대로 돌아오면 되고, 산봉우리 번호와 intensity만 반환하면 되므로 출입구로 다시 돌아오는 과정은 계산할 필요없이 최소 intensity를 갖는 산봉우리를 찾으면 되는 문제이다. 임의의 출입구로부터 다른 산봉우리까지 가는 최소 intensity는 다익스트라 알고리즘을 변형해 구할 수 있다. 하지만 정점이 최대 50,000개, 간선이 200,000개, 출입구가 최대 50,000개이므로 출..

[프로그래머스] 전화번호 목록 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 해시셋 풀이 1. 20개의 해시셋을 만들어 길이가 N인 전화번호를 N번째 해시셋에 추가한다. 2. phone_book을 탐색하며 1부터 (전화번호의 길이 - 1) 까지 전화번호의 앞 i 글자가 i 번째 해시셋에 이미 있다면 false를 반환한다. 문자열을 다 탐색했다면 한 번호가 다른 번호의 접두사인 경우가 없는 것이므로 true를 반환한다. 코드 import java.util.*; class Solution { public boolean solution(String[] phone_book) {..

[프로그래머스] 영어 끝말잇기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 해시셋 풀이 탈락하는 조건은 다음과 같이 두 가지이다. 1. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말하지 않았을 경우 2. 이전에 등장했던 단어를 다시 사용한 경우 따라서 앞사람이 말한 단어의 마지막 문자를 char 변수에 저장하고, 이전에 등장했던 단어를 HashSet 에 저장한다. words를 탐색하면서 1. 마지막 글자를 저장한 last와 현재 단어의 시작 글자인 words[i].charAt(0) 이 다를 경우 2. 또는 HashSet에 이미 words[i] 가 있을 경우 탈..

[프로그래머스] 신고 결과 받기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 해시맵, 해시셋 풀이 1. 유저와 해당 유저가 신고한 사람을 저장할 HashMap rMap과 유저와 해당 유저가 신고당한 횟수를 저장할 HashMap cMap 를 만들고, rMap과 cMap을 빈 set과 0으로 초기화한다. 2. report의 각 원소가 "신고자 피신고자" 형태이므로 공백 단위로 구분하여 신고자(key) - 피신고자(value) 조합이 없던 조합이라면 rMap의 value인 set에 추가하고, cMap의 value를 1 증가시킨다. 3. id_list를 탐색하며 id가 신고한 ..

[프로그래머스] 폰켓몬 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 해시셋 풀이 해시셋은 중복을 허용하지 않기 때문에, nums의 수를 해시셋에 삽입한 후, 해시셋에 크기가 폰켓몬의 종류가 된다. 따라서 해시셋의 크기가 N/2보다 크다면 N/2를 작다면 해시셋의 크기를 반환한다. 코드 import java.util.*; import java.math.*; class Solution { public int solution(int[] nums) { HashSet set = new HashSet(); for (int num : nums) set.add(num); re..