코딩테스트 연습 - 튜플
"{{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
- 분석 및 해결
집합의 원소들을 가지고 순서를 알아맞혀야 하며, 이때 주의할 점은 집합은 원소의 순서가 바뀔 수 있다는 점이다. 따라서 나는 집합을 원소의 개수별로 Map에 저장하였고, 집합의 원소가 1개인 것부터 n개인 것까지 차례로 돌아가며 순서를 유추했다.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class PG_튜플 {
// 원소의 개수별로 집합을 관리 key:원소 개수, value: 집합
private static Map<Integer, List<Integer>> map = new HashMap<>();
public int[] solution(String s) {
int[] answer = {};
parsing(s);
answer = getAnswer(answer);
return answer;
}
// 집합 나누기
private static void parsing(String s) {
int strLen = s.length();
List<Integer> list = new ArrayList<>();
String partStr = "";
for(int index = 1; index < strLen - 1; index++) {
char ch = s.charAt(index);
if(ch == '{') {
continue;
}
else if(Character.isDigit(ch)) {
partStr += ch;
}
else if(ch == ',') {
// 집합 내 원소를 구분하는 ','인 경우
if(s.charAt(index - 1) != '}') {
partStr += ch;
}
}
else if(ch == '}') {
String[] split = partStr.split(",");
for(String tmp: split) {
list.add(Integer.parseInt(tmp));
}
map.put(list.size(), list);
list = new ArrayList<>();
partStr = "";
}
}
}
private static int[] getAnswer(int[] answer) {
int n = map.size(); // tuple num
answer = new int[n];
Iterator<Integer> iter = map.keySet().iterator();
while(iter.hasNext()) {
int key = iter.next();
int num = map.get(key).get(0); // 집합에 존재하는 유일한 원소
// 현재 num을 모든 집합에서 삭제함.
// {2}, {1, 2}가 있다면, 2를 삭제함으로써 다음 집합에서 튜플의 다음 원소 순서를 파악할 수 있다.
for(int index = key; index <= n; index++) {
map.get(index).remove((Integer)num);
}
answer[key - 1] = num;
}
return answer;
}
}
'Algorithm > Programmers' 카테고리의 다른 글
[찾아라 프로그래밍 마에스터 - 포켓몬] (0) | 2021.07.25 |
---|---|
[2018 KAKAO BLIND RECRUITMENT] 파일명 정렬 (0) | 2021.04.03 |
[2021 KAKAO BLIND RECRUITMENT] 순위 검색 (0) | 2021.03.31 |
[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (0) | 2021.03.30 |
[2020 카카오 인턴십] 키패드 누르기 (0) | 2021.03.17 |
댓글