본문 바로가기

자료구조

 (19)
[백준] 15663번: N과 M (9) - JAVA 🔗 문제 링크 BOJ 15663번: N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📝 풀이 과정 permutation을 활용해 수열을 구하는 문제이다. 사전순으로 출력하기 위해 Arrays.sort를 활용해 입력이 들어온 숫자들을 오름차순 정렬해주었고, visit배열을 통해 같은 숫자가 수열에 포함되지 않도록 했다. input 3 1 4 4 2 -------- output 2 4 이전의 N과 M 문제들과 다른 점은 중복되는 수열이 출력되면 안된다는 점이다. 모든 수열을 구하게 되면 2,4,4..
[프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S programmers.co.kr 📝 풀이 과정 가장 최근 참조하지 않은 것을 교체하는 LRU 알고리즘을 구현해보는 문제이..
[프로그래머스] 뉴스 클러스터링 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 뉴스 클러스터링 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 📝 풀이 과정 집합을 만들어 교집합과 합집합을 조사해야 하는데, 같은 원소가 여러번 등장할 수 있고 자주 찾아 반환해주어야 하기 때문에 HashMap 자료구조를 사용하기로 했다. 집합에 대소문자 구분은 없으므로 String.toLowerCase()를 사용해 모든 문자열을 소문자로 변경해주었다. 첫번째 문자열을 모두 끊어 Map에 넣어..
[프로그래머스] 베스트앨범 - JAVA 🔗 문제 링크 [프로그래머스] 베스트앨범 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 📝 풀이 과정 genreTimes.put(genres[i], genreTimes.getOrDefault(genres[i], 0) + plays[i]); 먼저 장르마다 총 누적 플레이시간을 저장해야하기 때문에 Map.getOrDefault()를 통해 Map에 해당 장르가 존재한다면 기존 값을 얻어와 더해 다시 덮어쓰기 해주고 아니라면 0을 반환해 현재 값을 추가해 넣도록 하였다. List list = new ArrayLi..
[백준] 17219번: 비밀번호 찾기 - JAVA 🔗 문제 링크 BOJ 17219번: 비밀번호 찾기 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 📝 풀이 과정 사이트 주소를 통해 비밀번호를 얻으면 되는 문제이다. N과 M의 범위가 10만이기 때문에 단순 반복문으로는 시간초과가 발생할 수 있다. 사이트가 중복되지 않고, Map의 경우 get과 set의 연산 모두 $O(1)$이기 때문에 Map을 사용하기로 했다. Map을 통해 주소값을 key로 두고 비밀번호를 value로 저장하였고, 출력시 get(key)를 활용해 비밀번호를 출..
[백준] 11286번: 절댓값 힙 - JAVA 🔗 문제 링크 BOJ 11286번: 절댓값 힙 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 📝 풀이 과정 [백준] 11279번: 최대 힙과 정렬부분만 다른 문제이다. 우선 순위는 절대값이 작은 순 → 숫자가 작은 순으로 제거해야 하기 때문에 PriorityQueue를 사용해 Comparator의 compare를 오버라이딩하여 Queue에서 올바른 순서로 나올 수 있게 만들어 주었다. PriorityQueue que = new PriorityQueue((o1, o2) -> Math.abs..
[백준] 11279번: 최대 힙 - JAVA 🔗 문제 링크 BOJ 11279번: 최대 힙 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 📝 풀이 과정 힙을 직접 구현해도 좋겠지만, Java에 있는 PriorityQueue를 사용해 문제를 해결하기로 했다.(List로 문제를 풀 수도 있지만, n개의 숫자를 출력할 때마다 정렬하면 $O(n^2\log n)$으로 시간초과 발생) PriorityQueue는 add와 poll 모두 O(log n)으로 $O(n\log n)$만에 문제를 해결할 수 있다. PriorityQueue는 기본적으로 오름..
[백준] 9375번: 패션왕 신해빈 - JAVA 🔗 문제 링크 BOJ 9375번: 패션왕 신해빈 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 📝 풀이 과정 자료구조를 활용하여 경우의 수를 세는 문제이다. 만약 상의를 2개(상의1, 상의2), 바지를 1개(바지1) 가지고 있다면 (상의1) (상의2) (상의1, 바지1) (상의2, 바지1) (바지1) 총 5가지의 경우가 발생하게 된다. 이처럼, 상의를 입지 않거나 하나를 골라 입는 경우가 발생하게 된다. 때문에, 경..

티스토리툴바