-
프로그래머스 Lv.2) 튜플알고리즘/프로그래머스 카카오 2020. 5. 19. 22:21반응형
튜플
코딩테스트 연습 - 튜플
"{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1]
programmers.co.kr
풀이
답의 규칙을 찾은 결과 가장 작은 크기의 부분 수열이 가진 원소의 순서대로 답의 순서가 정해진다는 것이었다.
"{{1,2,3},{2,1},{1,2,4,3},{2}}"
위의 예제로 설명하면,
가장 작은 크기의 부분수열 {2}로부터 2가 정답의 맨 첫번째임을 알 수 있고, 그다음 {2,1}을 통해 2->1, {1,2,3}을 통해 2->1->3, {1,2,4,3}을 통해 2->1->3->4가 되는 것이다.
우선순위 큐를 통해 가장 작은 크기의 부분수열부터 큰 부분수열을 찾아가며 답을 리턴해줬다.
또한, String 하나로 주어지기 때문에 이를 parsing하기 위해 replaceAll과 split 메소드를 이용했다.
HashSet은 중복 검사를 통해 원소가 딱 한번만 들어가게 하기위해 썼고, MyNum은 부분수열을 관리하기 위해 클래스를 만들었다.
코드
import java.util.HashSet; import java.util.PriorityQueue; public class Tuple_64065 { private static int[] solution(String s) { PriorityQueue<MyNum_64065> pq = new PriorityQueue<>(); HashSet<String> strSet = new HashSet<>(); String[] strArr = s.split("},"); int len = 0; for(String str : strArr) { MyNum_64065 tmp = new MyNum_64065(str.replaceAll("[{]", "").replaceAll("[}]","").split(",")); len = Math.max(len, tmp.numArr.length); pq.offer(tmp); } int[] answer = new int[len]; int idx=0; while(!pq.isEmpty()) { MyNum_64065 mynum = pq.poll(); String[] tmpArr = mynum.numArr; for(String str : tmpArr) { if(!strSet.contains(str)) { answer[idx++] = Integer.parseInt(str); strSet.add(str); } } } return answer; } public static void main(String[] args) { String s = "{{2},{2,1},{2,1,3},{2,1,3,4}}"; int[] result = solution(s); for(int num : result) { System.out.print(num + " "); } } } class MyNum_64065 implements Comparable<MyNum_64065> { String[] numArr; public MyNum_64065(String[] numArr) { this.numArr = numArr; } @Override public int compareTo(MyNum_64065 mynum) { return this.numArr.length > mynum.numArr.length ? 1 : -1; } }
반응형'알고리즘 > 프로그래머스 카카오' 카테고리의 다른 글
프로그래머스 Lv.2) [1차] 뉴스 클러링 (0) 2020.05.22 프로그래머스 Lv.2) 단체사진 찍기 (0) 2020.05.19 프로그래머스 Lv.2) 카카오프렌즈 컬러링북 (0) 2020.05.16 프로그래머스 Lv.4) 추석 트래픽 (2) 2020.05.15 알고리즘) 카카오 블라인드 채용 2020, 블록 이동하기 (0) 2020.05.09