publicclassNthGame{ //프로그래머스 문제풀이 level2 n진수 게임 publicstaticvoidmain(String[] args){ int n=2, t=4, m=2, p=1; String answer = ""; String answer = ""; int cnt = 0; int num = 0; int idx = 1; while(cnt < t) { Stack<Integer> stack = new Stack<>(); int t_num = num; do { stack.push(t_num%n); t_num /= n; }while(t_num > 0); while(!stack.empty()) { if(p == idx) { String add_num = String.valueOf(stack.peek()); if(add_num.equals("10")) add_num = "A"; elseif(add_num.equals("11")) add_num = "B"; elseif(add_num.equals("12")) add_num = "C"; elseif(add_num.equals("13")) add_num = "D"; elseif(add_num.equals("14")) add_num = "E"; elseif(add_num.equals("15")) add_num = "F"; answer += add_num; p += m; cnt++; if(cnt == t) break; } idx++; stack.pop(); } num++; } } }
cnt는 알려준 숫자이며 이것이 t가 될 때까지 숫자를 n진수로 바꿔볼 것이다. num은 0부터 시작한다. num은 1씩 계속 증가해야 하므로, 실제 연산을 할 땐 t_num에 복사한 값을 쓴다. 0도 진수로 바꾸어야 하기 때문에 do-while문을 사용하였다. n진수로 바꾼 숫자들은 스택에 쌓는다. idx는 현재 몇번째 숫자인지 알려주는 지표이다. 이 idx값이 p값과 일치한다면 그 값을 문자열에 추가하고 p에 m을 더해 다음 차례를 알려준다. idx는 pop을 할 때마다 1씩 증가하도록 한다.
테스트
카카오톡 인턴 시험을 봤는데, 역시 정말 어려웠다. 공부한지 얼마 되지도 않았는데 벌써 기죽지말고 차근차근 해나가자. 발전하고 있다.
코드가 긴데 핵심 아이디어는 간단하다. head별로 정리하여 사전을 만들어놓고 number별로 사전을 만들어놓고 들어온 순서대로 사전을 만들어 3개의 사전을 준비한다. 이제 두 대상을 비교할 때, head로 된 사전을 찾아보고 만약 두 값이 같으면 number사전을 찾아본다 number사전에서의 값도 같다면 순서를 기록해둔 사전을 참고하여 순서를 알아내면 된다. main은 이 세가지 사전을 만드는 과정이다.
22번째 줄에서 순서 사전을 만드는 것을 볼 수 있다 들어온 파일명대로 순서대로 i를 증가하며 저장한다. 이와 동시에 head사전과 number사전을 만들기 위한 준비를 한다. 정렬은 하지 않은 채 배열에 넣는다. 이때 head는 모두 소문자로 바꾸어 넣고 number는 모두 int로 변환하여 넣는다.
이제 head를 정렬한다. 정렬하고 이를 사전에 넣어야하는데, 만약 사전에 이미 있는 경우라면 값을 바꾸면 안되기 때문에 getOrDefault함수를 활용하였다. 사전에 없는 경우라면 사전의 크기를 값으로 지정한다. number또한 똑같은 원리로 한다. 이제 모든 사전이 완성되었다.
파일들을 정렬하기 위해 비교자를 새로 정의하였다. 비교자 선언은 어렵지 않다. 아까 말한 우선순위를 그대로 코드에 적었으니 찬찬히 보면 이해가 갈 것이다. ReturnHeadNumber에서 head와 number값을 받아올 수 있다.
ReturnHeadNumber를 보자. head_idx와 tail_idx가 있다. head_idx에는 head가 끝나는 인덱스를 너흘 것이고 tail_idx는 tail이 시작되는 지점을 넣을 것이다. isnum은 flag인데 코드를 살펴보면서 설명하겠다. 일단 문자열에서 문자를 하나씩 떼와서 처음으로 숫자가 나올 경우 이곳부터 number가 시작되므로 head_idx에 해당 인덱스 값을 넣고 isnum을 true로 해준다. isnum이 없다면 숫자가 여러자리 일 때도 head_idx가 계속 증가하기 때문이다.
isnum이 true로 바뀌면 이제 tail값을 찾아야한다. 처음으로 숫자가 아닌 구간이 나온다면 그곳부터는 tail이므로 tail_idx에 해당 idx를 넣고 반복문을 탈출한다. 이제 두 값으로 문자열을 잘라주면 우리가 원하는 head와 number를 가져올 수 있다.
최종 시간복잡도는 파일들의 개수를 n개라 할 때, \(O(nlogn)\)이다.
테스트
비교자를 새로하는 부분에서 테스트케이스가 많으면 간혹 논리가 맞아도 정렬이 꼬이는 경우가 있어서 불안했었는데, 무사히 통과해서 다행이다.
//프로그래머스 문제풀이 level2 압축 publicstaticvoidmain(String[] args){ String msg = "KAKAO"; ArrayList<Integer> answer = new ArrayList<>(); HashMap<String, Integer> map = new HashMap<>(); for(int i = 0; i < 26; i++) map.put(String.valueOf((char)('A'+i)), i+1); int w = 0; int c = 1; boolean flag = false; while(c <= msg.length()) { int value = map.getOrDefault(msg.substring(w,c), 0); while(value != 0) { c++; if(c > msg.length()) { flag = true; break; } value = map.getOrDefault(msg.substring(w,c), 0); } answer.add(map.get(msg.substring(w, c-1))); if(flag) c--; map.put(msg.substring(w, c), map.size()+1); w = c-1; if(flag) break; } } }
사전을 map으로 구현하였다. 일단 A부터 Z까지 기본 단어를 만들어 놓는다. 그리고 w에서 c까지의 문자열을 반복해서 본다. c의 값을 늘려가며 처음으로 map에 없는 단어가 나올 경우 맵에 해당 문자열을 저장하고 바로 직전 반복의 문자열은 색인 값을 반환한다. 그리고 w에 다음 위치인 c-1을 집어넣으면 되는 단순한 알고리즘이다. 하지만 이 반복은 c가 메시지의 길이에 달했을 때 배열범위에 문제가 생기므로 이에 대한 처리를 따로 해야한다. flag와 관련된 부분이 그 부분이다.
네오가 기억하는 계이름과 음악의 계이름 재생시간이 주어질 때, 네오가 들은 곡을 알아내는 문제이다. 음악의 길이보다 재생기간이 길면 반복하여 재생하는 것이고, 짧다면 중간에 끊어진 것이라고 봐야한다. 만약 네오가 기억하는 계이름을 가지고 있는 곡이 여러 개라면 재생 시간이 긴 것을 우선으로 하고, 재생 시간도 같은 경우 먼저 들어온 곡을 반환한다.
int repeat = duration/code_cnt; int song_end = duration%code_cnt; String song = ""; for(int i = 0; i < repeat; i++) { song += info_arr[3]; }
char[] song_arr = info_arr[3].toCharArray(); int song_idx = 0; for(int i = 0; i < song_arr.length; i++) { if(song_idx == song_end) break; StringBuilder buff = new StringBuilder(); buff.append(song_arr[i]); if((i < song_arr.length-1) && (song_arr[i+1] == '#')) buff.append(song_arr[++i]); song += buff.toString(); song_idx++; }
곡을 재생시간만큼 만들기 위해서 #에 대한 처리가 필요하다. 일단 #을 제외하면 전체 계이름 개수를 알 수 있다. #을 기준으로 문자열을 쪼갠 뒤, 전체 계이름 개수를 구한다. 그리고 repeat와 song_end를 구한다. repeat는 전체 노래가 몇 번 반복하는지 알려주는 변수이다. 나누기 연산을 통해 구할 수 있다. song_end는 중간에서 노래가 멈출 경우 몇번째 음에서 멈추는지 알려주는 변수이다. 이는 나머지 연산을 통해 구할 수 있다.
repeat수 만큼 전체 문자열을 song에 더해주고 두번째 for문은 song_idx가 song_end에 도달할 때까지 #을 고려하여 song에 계이름을 더해준다.
이제 만든 노래를 비교해보면 된다. 여태까지 제일 길었떤 재생 시간을 저장한 last_time이 duration보다 작고, 네오가 기억한 음이 포함되어 있다면 if문 안으로 들어간다. 이 때, 처리해주지 못하는 케이스가 있는데 맨 마지막에 #이 붙는 경우이다. 이 경우 indexOf로 찾은 값에 m의 길이를 더해 #이 있으면 불일치로 간주하면 된다. 네오의 음과 일치하는 구절이 여러 곳일 수 있기 때문에 idx는 루프를 돌 때 마다 업데이트한다.
코드가 긴 편인데 과정을 살펴보면 후보키가 될 수 있는 모든 조합을 만들어보고 검사하는 것이다. 원소의 개수가 k개인 부분집합을 검사해주는 함수를 만들어서 k를 1부터 행의 갯수만큼 돌려보면 모든 경우의 수를 다 볼 수 있다. 메인쪽은 간단하기 때문에 함수만 보도록하자.
publicstaticvoidReturnIndex(int size, int k, String idx, int start_idx) { if(size == k) { for(int i = 0; i < table.length; i++) { String[] arr = idx.split(""); StringBuilder buff = new StringBuilder(); for(String s : arr) { buff.append(table[i][Integer.parseInt(s)]); buff.append(" "); } if(map.getOrDefault(buff.toString(), 0) != 0) { map.clear(); return; } map.put(buff.toString(), 1); } for(String s : keys) { char[] key = s.toCharArray(); char[] idx_arr = idx.toCharArray(); int k_i = 0; for(int i = 0; i < idx_arr.length; i++) { if(key[k_i] == idx_arr[i]) { k_i++; } if(k_i == key.length) return; } } answer++; keys.add(idx); map.clear(); } else { for(int i = start_idx+1; i < table[0].length; i++) { ReturnIndex(size+1, k, idx+String.valueOf(i), i); } } }
매개변수에 대해 설명을 하자면 size는 현재 집합에 들어가있는 원소의 개수, k는 만들고자 하는 부분집합의 크기이다. idx는 부분집합에 들어가있는 원소를 나타낸다. 가령 1,2행으로 만들고자 한다면 idx에는 "12"가 들어가있다. start_idx는 이제부터 집어넣을 행을 나타낸다. 중복을 없애기 위해 strat_idx를 넣었다고 보면 된다.
종료조건을 먼저 생각해보자 size가 k가 되면 일단 튜플을 고유하게 분류할 수 있는지 봐야한다. 이를 위해 map을 활용하였다. idx에 있는 행번호를 가져와 map의 키를 생성한다. 이 예제에서 만약 idx가 "12"라면 "b 2", "b 2", "1 0", "7 5","3 0"으로 만들어질 것이다. 키를 만들 때 공백을 넣어주는데 이유가 있다. 수학11점과 과학1점, 과학11점과 수학1점은 다르기 때문이다. 숫자만 합하면 111이지만 다른 정보이기 때문에 다른 키 값으로 간주된다.
키를 만들 때마다 맵에서 똑같은 키 값이 존재하는 지 확인한다. 만약 똑같은 키값이 있다면 1이 반환되므로 이때는 맵을 클리어한 뒤 바로 함수를 종료한다.
맵에서 중복되지 않으면 고유성을 통과했으니 이제 유일성을 확인할 차례이다. 이 부분에서 꽤나 골머리를 앓았는데 contains를 쓰면 틀린다는 사실을 몰랐기 때문이다. "abcd"에서 "ad"는 부분집합이지만 contains로는 이를 판별할 수 없다. 그래서 이를 위한 처리를 해야한다. 두 문자열을 문자배열로 바꾼 뒤, 이미 있는 키들의 부분집합 관계인지 하나하나 확인하는 코드를 짰다. 만약 key가 idx의 부분집합이라면, k_i가 key의 크기가 될 것이고 이 때 바로 함수를 종료한다.
문제에서 원하는 것은 최종 단톡방의 관리창이기 때문에 중간에 몇 번을 바꾸었든 최종적으로 바꾼 닉네임만 가지고 있으면 된다. 필자는 map을 활용하여 문제를 풀고자 한다. map의 키는 uid이며, 값은 닉네임이다. 배열을 순회하며 Enter나 Change가 들어오면 맵에 값을 추가한다. 이미 있는 값이면 최근 값으로 업데이트한다.
이 과정을 끝내면 각 uid마다 최종 닉네임이 무엇인지 알 수 있다. 이제 이를 활용하여 문제에서 원하는 형식으로 답을 내면 된다. 들어오고 나간다는 문자에 따라 적절한 형식을 버퍼에 삽입하고 이를 어레이리스트에 삽입한다.
자바는 정말 놀라운 언어이다. 호출 빈도에 따라서 정렬해주는 맵이 이미 존재했다! LinkedHashMap에서 호출 빈도에 따른 정렬을 제공하는데, 평소에는 false로 되어있다. 이를 true로 바꿔주면 LRU를 구현하기 한 층 쉬워진다.
일단 캐시 사이즈가 0인 경우를 따로 처리한다. 0인 경우 맵의 크기가 0이 되어 예외가 발생하기 때문이다. 0인 경우에는 모든 도시에서 cache miss가 발생하므로 전체 크기에 5를 곱한 값을 반환한다. 그렇지 않은 경우 캐시를 활용한다. 만약 들어온 도시 이름이 맵에 없는 경우 두 가지 경우로 나뉜다.
캐시가 이미 다 차서 오래된 것을 제거해야 하는 경우
캐시에 아직 여유 공간이 있는 경우
1번의 경우 맵에서 호출된지 가장 오래된 원소를 지워야한다. 이는 map에서 첫번째 원소를 제거하면 되므로 iterator의 첫번째 키값을 받아 제거한다. 이 뒤에 원소를 추가한다. 이 과정을 거치고 정답에 5를 더해준다.
만약 캐시에 도시 이름이 있을 경우 반응시간을 1늘려주면 된다.
호출 시간에 따른 정렬은 시간복잡도가 정확히 나타나있지 않다. 다만 \(logn\)으로 추측이 간다(이진 탐색을 활용할 가능성이 높다). 따라서 최종시간복잡도는 \(O(nlogn)\)이다.
코드가 길지만 진정하고 차근차근 따라가보자 과정에 따라 나누면 코드는 다음과 같이 나눠진다. 1. 집합 A를 만든다. 2. 집합 B를 만든다. 3. 집합 A와 집합 B의 교집합을 구한다. 4. 집합 A와 집합 B의 합집합을 구한다. 5. 교집합과 합집합에 들어있는 원소의 개수로 답을 구한다.
필자는 hashmap을 사용해서 문제를 풀었다. 일단 arr1에 문자열을 쪼개어 문자 배열로 만든 다음 두글자씩 보면서 영어가 아닌 것이 있으면 map에 추가되지 않도록 continue를 사용했다. 만약 두 문자다 영어라면 버퍼에 문자들을 넣어주고 전부 소문자로 바꾸어주었다. 이유는 대문자 소문자를 구별하지 않는다고 문제에 나와있기 때문이다. 이후 맵에 문자를 key값으로 하고 값은 만약 이미 값이 있다면 기존값에 +1을 없다면 1을 삽입하도록 한다.
1,2번 과정이 끝났으니 이제 교집합을 구할 차례이다. 교집합은 두 집합 모두에게 존재해야 한다. 따라서 필자는 a의 key값을 b에 대입해 볼 것이다. 만약 b에 값이 존재한다면 a와 b에 있는 값 중 작은 값이 들어가도록 했다. 아래에 보면 union은 합집합인데 a를 일단 넣어두려고 반복문안에 넣었다.
이제 자카드 유사도를 구할 차례이다. inter_size와 union_size를 선언하고 value들을 전부 합한 값을 담는다. 이때 union_size를 0으로 초기화하지 않은 이유는 0으로 나눴을 때 예외가 발생하기 때문에 컴파일을 애초에 해주지 않기 떄문이다. 그래서 1로 선언하고 나중에 다시 1을 감소시킨다. 나눈 두 값으로 자카드 유사도를 구했다.
최종 시간복잡도는 공비가 \(1\over2\)인 등비수열의 합이므로, 2진법을 계산하는 과정이 있기 때문에 \(O(n*{1\over2}^n)\)이다.
//프로그래머스 문제풀이 Level2 예상 대진표 publicstaticvoidmain(String[] args){ int n = 8, a = 4, b = 7; boolean flag = false; int total_round = Integer.toBinaryString(n).length()-1; int l = Math.min(a,b); int r = Math.max(a,b); int answer = total_round; int size = 2; for(int i = 1; i <= total_round; i++) { for(int j = 1; j <= n; j+=size) { if(j <= l && r <= j+(size-1)) { answer = i; flag = true; break; } } if(flag) break; size *= 2; } System.out.println(answer); } }
원래 재귀로 풀었었는데, 런타임 에러가 자꾸 떠서 결국 방법을 바꾸었다. 비주얼 스튜디오 코드에서는 동작했던 걸 보아하니 채점 사이트에서 막은 건가 싶었다. 어쨌든 새로 한 두번째 방법은 2명씩 4명씩 8명씩.. 이런식으로 계속 묶어나가며 a,b가 동시에 속한 경우를 발견하면 그 라운드를 i에 받고 반복문을 마친다.
코드를 좀 더 자세히 설명하자면, total_round는 이진법으로 바꾼 문자열에서 -1하면 된다. 그리고 l은 두 선수 중 숫자가 작은 쪽, r은 숫자가 큰 쪽이다. 1라운드부터 최종라운드까지 선수들을 묶어가면서 범위에 두 선수가 속해있는지 확인한다. 이때 초기 size는 선수가 2명씩 묶이므로 2로하고 라운드를 진행할 수록 팀 당 선수는 2배씩 늘어나므로 size도 2를 곱해준다.
최종 시간복잡도는 공비가 \(1\)인 등비수열의 합이므로, 2진법을 계산하는 과정이 있기 때문에 \(O(n*{1}^n)\)이다.
테스트
비트 연산을 통해서 문제를 푼 것을 보고 감탄을 느꼈다. 2로 나누거나 곱하는 연산은 비트 연산을 통해 풀어볼 수 없는지 공부해 봐야겠다.
k칸 앞으로 점프하는 경우 k만큼 건전지를 사용하고 워프를 통해 현재위치의 두배에 해당하는 위치로 비용없이 간다고 할 때, 목표 지점 n으로 이동하는 최소 건전지 사용량을 구하는 문제이다.
문제풀이
전체 코드는 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
package level2;
publicclassJumpAndTele{
//프로그래머스 문제풀이 Level2 점프와 순간 이동
publicstaticvoidmain(String[] args){ int n = 5000; System.out.println(Integer.bitCount(n)); } }
코드가 너무 간단해서 황당할 수 있다. 자바에는 bitCount란 메소드가 있다. 수를 넘겨주고 이를 2진수로 바꿨을 때 1의 개수를 반환하는 프로그램이다. 이것이 왜 성립하는지 알아보자.
일단 워프를 최대한 많이 쓰는 것이 좋은 것은 자명하다. 그렇다면 이를 어떻게 쓰냐는 건데, 5를 예로 들어보자 5로 가는 가장 빠른 방법은 2에서 워프를 하고 1을 더하면 된다. 2에 도달하는 방법은 1에서 워프를 타면 된다. 그렇다면 0에서 1로는 1만 더하면 된다. 이 방법이 이진법에서 1의 개수를 세는 것과 같다.
최종 시간복잡도는 2진법을 계산하는 과정이 있기 때문에 \(O(log_{2}n)\)이다.
테스트
원래는 \(O(n)\)까지 복잡도를 줄여봐도 효율성이 개선이 안되었다. 10억이나 되기 때문이다. 남자친구랑 점심먹으면서 이 얘기를 하다가 남자친구의 힌트로 허무하게 문제를 풀었다. 역시 수학은 중요하다.
