//프로그래머스 level2 문제풀이 기능 개발 publicstaticvoidmain(String[] args) { int[] progresses = {93, 30, 55}; int[] speeds = {1, 30, 5}; Queue<Integer> q = new LinkedList<>(); ArrayList<Integer> answer = new ArrayList<>(); int r_date; for(int i = 0; i < progresses.length; i++) { r_date = (int)Math.ceil((100-progresses[i])/(double)speeds[i]); q.add(r_date); } r_date = q.peek(); int cnt = 0; while(!q.isEmpty()) { if(r_date >= q.peek()) { cnt++; q.remove(); } else { answer.add(cnt); cnt = 1; r_date = q.poll(); } } answer.add(cnt); } }
일단 각 기능이 언제 개발이 완료하는지 계산해야한다. 이 때, 배포는 하루의 끝에 완료된다는 가정이 있기 때문에 올림으로 처리해야한다. 정수간의 나눗셈은 정수만 반환하므로, 실수로 캐스팅하는 걸 잊어선 안된다. 그리고 큐에 완성일을 추가한다.
이 문제는 쉽게 큐에서 오름차순을 찾아내는 문제이다. 배포일 r_date를 큐의 첫번째 원소로 초기화한다. 그리고 배포되는 기능의 개수를 저장하는 cnt를 같이 선언한다. 큐에서 원소들을 보면서 r_date보다 빠른 것들은 같이 배포해야하는 것들이므로 cnt를 늘린다. 만약 r_date보다 늦게 배포하는 것은 배포일을 따로 하는 것이므로, 그 때 cnt를 어레이리스트에 저장하고 cnt를 1로 초기화한다. 비교할 r_date는 해당 원소로 업데이트한다.
이 문제의 시간복잡도는 큐에 들어갔다 나오는 최대 반복을 생각하면 된다. progresses의 길이를 n이라 했을 때, 총 삽입과 삭제의 수는 2n이다. 따라서 시간복잡도는 \(O(n)\)이 된다.
테스트
이 문제같은 경우 시간을 너무 많이 소요했다. 두번째 조건을 생각하기 힘들었는데, 질문하기에서 누군가가 올려준 테스트케이스 덕분에 통과할 수 있었다.
자신의 주가가 언제 적자가 나는지 계산하는 문제이다. 예를 들면 문제에서 가격이 4일 때 주식을 사면 4초동안 주가가 떨어지지 않으므로 4이다. 필자는 처음에 문제를 잘못 이해하여 하나 빼고 다 틀렸다. 질문하기를 보니 다른 사람도 똑같이 그런 것 같았다. 지문의 개선이 필요해보인다.
스택과 큐를 활용하라는 문제라고 나와있긴 하지만, 필자는 활용하진 않았다. 최대 길이가 만개이기 때문에 \(n^2\)의 시간복잡도도 충분히 돌아갈거라 생각했기 때문이다. 코드는 간단하다. 각 주식 가격에서 처음으로 주가가 떨어지는 포인트를 발견하면, 그 두 값의 차를 기록하는 것이다. 만약 if문을 거치치 않았다면 끝까지 주가가 떨어지지 않는다는 것이므로 전체에서 인덱스+1을 빼준다.
이 문제의 시간복잡도는 \(O(n^2)\)이다.
테스트
이걸 스택 큐로 분류해 놓은 이유를 잘 모르겠다. 스택/큐를 이용하면 더 빠른 시간안에 풀 수 있는것일까?
처음에 필자는 저 순서대로를 못 읽고, 정렬을 했다가 주구장창 틀렸다. 역시 문제는 꼼꼼히 읽자. 필자는 각 트럭별로 들어오는 시간을 계산하여, 가장 마지막 시작시간에 다리의 길이를 더해주는걸로 정답을 내었다. 변수 설명을 하자면, item은 각 트럭의 id인덱스 번호이다(지금 생각해보니 truck_id가 더 나았을 것 같다.). w는 현재 다리가 버티고 있는 무게이고, out은 현재 다리를 빠져나간 트럭의 인덱스를 나타낸다. in_time은 트럭이 다리로 진입할 때의 시간이다. 이제 트럭을 큐에 넣었다 빼며, 맨 마지막으로 들어오는 트럭의 진입시간(in_time)을 계산하면 된다. 일단 while문을 넘기고 24-28번째 줄을 들여다보자. 큐에 진입하는 시간을 넣고, 다음 트럭이 오는 in_time을 계산하기 위해 item과 in_time을 1씩 증가하였다. 기본적으로 weight가 무한대라면 저것만 쓰면 될 테지만, 다리가 버틸 수 있는 무게가 있기에 while문이 필요한 것이다. while문의 첫번째 조건은 이해가 간다. 들어올 트럭의 무게를 현재 무게에 합했을 때 한계치를 넘을 경우, 앞에 있는 트럭이 빠져나가고 넣어야 한다. 뒤에 있는 조건문이 어려울 수도 있는데 이를 설명하기 위해 코드에서 쓴 테스트 케이스를 그림으로 설명하겠다.
트럭의 무게들과 첫번째 조건만을 활용했을 경우 나타나는 오류를 나타낸 그림이다. 아래가 각 시간마다 다리에 있는 트럭의 위치를 나타낸 것이니 참고하면 되겠다. while문의 두번째 조건을 무시하고 첫번째 조건만을 신경쓴 채로 큐에 원소를 넣고 빼고 하다보면 idx = 6일 때 이상한 모습을 볼 수 있다. 6이 진입할 때 무게는 3이어야 하는데 5가 된 것이다. 3번 트럭이 빠지지 않은 것이 문제인데, 첫번째 조건만 가지고는 이것을 걸러낼 수 없다. 큐에서 원소를 뺄 때, 무게만 고려하는 것이 아니라 현재 in_time시간에 빠져나간 트럭들을 제거해주는 것도 같이 해야한다. 그래서 두번째 조건이 나온 것이다. 큐가 만약에 비어있다면 false를 반환하고, 아니라면 in_time에 나가야하는 트럭이 있는지 유무를 확인한 뒤, 그 원소가 큐에 남아있다면 큐에서 그 원소를 삭제한다. 모든 원소의 진입 시간이 계산되었으니, 정답을 계산한다. 마지막 반복문을 돌 때, in_time이 1 증가되었으니 이를 1줄여주고, 다리 길이를 더하면 정답이다.
이 문제의 시간복잡도를 구하기 힘들어할 수도 있는데, 어렵지 않다. 큐에 들어갔다 나오는 최대 반복을 생각하면 된다. truck_weights의 길이를 n이라 했을 때, 다 들어왔다가 다 나간다해도 2n이다. 따라서 시간복잡도는 \(O(n)\)이 된다.
테스트
이 문제같은 경우 시간을 너무 많이 소요했다. 두번째 조건을 생각하기 힘들었는데, 질문하기에서 누군가가 올려준 테스트케이스 덕분에 통과할 수 있었다.
//프로그래머스 문제풀이 level2 멀쩡한 사각형 publicstaticvoidmain(String[] args) { int w = 8; int h = 12;
long answer = 0; double a = h*(-1)/(double)w; int b = h; for(int i = 1; i < h; i++) { double x = (i-b)/a; answer += (long)x; } answer *= 2;
System.out.print(answer); } }
코드의 길이는 짧은 편이다. 일단 필자는 사각형을 2차원 좌표로 나타냈을 때, (0,h) 와 (w,0)을 지나는 직선으로 생각했다. 그러면 기울기 a와 y절편 b를 구할 수 있다. 그리고 y좌표가 1부터 h-1까지(왜냐하면 y좌표가 h이면 어차피 멀쩡한 사각형이 없다.) 각각의 x좌표를 구한다. 그렇다면 그 x좌표가 해당 높이의 대각선이 존재하는 위치이다. 그렇다면 계산한 x가 만약 6.12xxxxx 라면 멀쩡한 사각형은 해당 위치에서 12(6*2)개가 있을 수 있다. 필자는 직각삼각형에 존재하는 사각형을 모두 구한 뒤 이를 2배 했다. 필자와 비슷한 생각을 했다면 아마 프로그래머스에서 테스트 케이스 6번을 틀렸을 수도 있는데, 이는 부동소수점 오차가 영향을 줬기 때문이다. 필자도 x값을 구하는 과정에서 (i/a) - (b/a)를 썼는데 틀렸었다. 그래서 나누기를 최소화하는 방향으로 둘을 합치니 통과가 되었다. 실수형 연산을 할 땐 조심 또 조심하자.
최종적인 시간복잡도는 \(O(h)\)이다.
테스트
최대공약수를 통해서 이 문제를 푼 사람도 있었다. 도대체 그런 규칙은 어떻게 알아내는 지 신기하다. 패턴이 존재하는 것 같은 느낌은 받았지만, 필자는 그 규칙까지 찾아내지 못했다. 덕분에 유클리드 호제법도 익힐 수 있었다.
publicstaticvoidmain(String[] args) { String skill = "CBD"; String[] skill_trees = {"BACDE", "CBADF", "AECB", "BDA"}; int answer = 0; boolean isAdd = true; HashMap<Character, Integer> map = new HashMap<>(); char[] skill_arr = skill.toCharArray(); int v = 0; for(char c : skill_arr) { map.put(c, v); v++; } for(String s : skill_trees) { int pre_v = -1; char[] skill_tree_arr = s.toCharArray(); for(char c : skill_tree_arr) { int value = map.getOrDefault(c, -1); if(value != -1 && value - pre_v != 1) { isAdd = false; break; } elseif(value != -1) pre_v = value; } if(isAdd) answer++; isAdd = true; } System.out.print(answer); } }
필자는 해시를 이용하여 문제를 풀었다. 자세한 사항은 부분부분 보면서 따라가자.
1 2 3 4 5 6 7 8 9
boolean isAdd = true; HashMap<Character, Integer> map = new HashMap<>(); char[] skill_arr = skill.toCharArray(); int v = 0; for(char c : skill_arr) { map.put(c, v); v++; }
isAdd는 문자열이 조건을 만족하는지 여부를 저장하는 변수이다. 해쉬를 쓰기 위해 해시 맵을 선언했다. skill의 문자 하나하나를 hash에 매핑 시킨다. 예를 들어 "CBD"가 주어진다면, [C:0, B:1, D:2]와 같이 매핑된다. 이렇게 매핑해두면 각 키의 값을 비교하여 1씩 증가하는 지 확인하면 된다. 매핑하지 않은 키는 -1을 반환하도록 하여 이 연산에서 빠지도록 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
for(String s : skill_trees) { int pre_v = -1; char[] skill_tree_arr = s.toCharArray(); for(char c : skill_tree_arr) { int value = map.getOrDefault(c, -1); if(value != -1 && value - pre_v != 1) { isAdd = false; break; } elseif(value != -1) pre_v = value; } if(isAdd) answer++; isAdd = true;
위에서 설명한 부분의 코드이다. pre_v의 초기값으로 -1을 넣어준 뒤, 주어진 스킬트리에서 문자를 하나씩 꺼내본다. 만약 맵에 있는데 초기값과 1차이가 나지 않는다면, 조건을 만족하지 않으므로 isAdd를 false하고 반복문을 탈출한다. 맵에 있는 값이면 pre_v를 업데이트 해주는 것을 잊지 않도록 하자. 다음엔 isAdd를 통해 정답을 세나간다. 최종적인 시간복잡도를 계산해보면 skill_trees의 길이를 n이라하고 skill_trees에 있는 문자열의 길이를 m이라하면, \(O(n*m)\)이다.
테스트
정규식을 통해 문제를 푼 사람도 있어서 신기했다. skill_trees의 각 원소에서 skill이 아닌 문자들을 지운뒤, indexOf를 활용하여 순서를 유지하는지 확인하였다. 이럴 경우 코드 수가 많이 줄어들어 가독성이 좋았다. 나도 정규식을 좀 더 공부해 봐야겠다.
publicstaticvoidmain(String[] args) { int n = 6; StringBuilder buff = new StringBuilder(); while(n > 0) { int r = n % 3; n/=3; buff.append(String.valueOf(r)); } char[] arr = buff.reverse().toString().toCharArray(); for(int i = arr.length-1; i >= 0; i--) { if(arr[i] == '0') { int p = i; for(int j = i; j >=0; j--) { if(arr[j] != '0') { p = j; break; } } if(p != i) { for(int k = p; k < i; k++) { int pre_num = Integer.parseInt(String.valueOf(arr[k])); char pre_char = Character.forDigit(pre_num-1, 10); arr[k] = pre_char; int aft_num = Integer.parseInt(String.valueOf(arr[k+1])); char aft_char = Character.forDigit(aft_num+3, 10); arr[k+1] = aft_char; } } } } int start_idx = 0; for(int i = 0; i < arr.length; i++) { if(arr[i] != '0') { start_idx = i; break; } } for(int i = start_idx; i < arr.length; i++) { if(arr[i] == '3') arr[i] = '4'; } String answer = new String(arr); answer = answer.substring(start_idx, arr.length);
System.out.println(answer); } }
부분부분 따라가보자.
1 2 3 4 5 6 7
while(n > 0) { int r = n % 3; n/=3; buff.append(String.valueOf(r)); } char[] arr = buff.reverse().toString().toCharArray();
일단 정상적인 3진법으로 만든다. 기본적으로 이 문제는 3진법의 응용문제이다. 왜냐하면 사용하는 숫자가 총 3개이기 때문이다. 이를 대응관계로 보면 3진법의 수는 {0, 1, 2}인데, 이 문제의 경우 {4, 1, 2}로 대응된다. 그러면 3진법으로 바꿔서 4,1,2로만 바꾸면 되지 않느냐 할 수 있는데 그럴 수 없다. 3의 배수가 아닌 수는 앞서 말했던 방법이 통한다. 하지만 6을 예시로 들어보자 6의 경우 3진법으로 바꾸면 20이다. 이를 대응 관계에 비춰 바꿔보면 24이지만, 정답은 14이다. 0이 존재하지 않기 때문에 이를 처리하기 위한 방법이 필요하다. 실은 이 부분에서 꽤 고생을했는데 필자가 생각한 방법은 이렇다. 1. 3진수로 바꾼 배열을 뒤에서부터 보면서 0이 있는지 확인한다. 2. 0이 있으면 앞에서부터 빌려올 수 있는 수가 있는지 확인한다. 3. 빌려올 수 있는 수가 있다면 빌려온다. 이 때 내려받는 수는 10진법에선 10이지만, 지금은 3진법이므로 3이 되겠다. 4. 3을 빌려준 수는 1 깎인다. 5. 0을 다 없애고 나면 3인 수를 4로 바꿔준다.
이해를 돕기 위해 그림을 첨부한다.
초등학생 때 했던 10진수 빼기를 생각하면 된다.
이 부분에서 시간복잡도는 3으로 나눴을 때의 자릿수만큼이므로 \(O(log3(n))\)이다.
for(int i = arr.length-1; i >= 0; i--) { if(arr[i] == '0') { int p = i; for(int j = i; j >=0; j--) { if(arr[j] != '0') { p = j; break; } } if(p != i) { for(int k = p; k < i; k++) { int pre_num = Integer.parseInt(String.valueOf(arr[k])); char pre_char = Character.forDigit(pre_num-1, 10); arr[k] = pre_char; int aft_num = Integer.parseInt(String.valueOf(arr[k+1])); char aft_char = Character.forDigit(aft_num+3, 10); arr[k+1] = aft_char; } } } }
3진수로 바꾼 수에서 뒤에서부터 보면서 0이 있는지 확인한다. 만약 0이 있다면, 자신의 앞에 있는 수에서 3을 빌릴 수 있는지 확인한다. 3을 빌릴 수 있는 숫자가 발견되면, 그 인덱스를 기억해 놨다가. 빌리고 빼는 것을 반복한다. 위 코드에서 보이는 k를 iterator로 쓰는 for문이 바로 그 부분이다(3,4번과정). 이 분의 시간 복잡도는 \(O(log3(n))\)인데, 해봤자 \(2log3(n)\)이기 때문이다. 앞쪽에서 빌리면 해당수와 앞쪽 사이에는 0이 절대로 존재할 수 없기 때문인데, 혹시 더 이해가 안간다면 이메일을 통해 언제든지 질문하기를 바란다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
for(int i = 0; i < arr.length; i++) { if(arr[i] != '0') { start_idx = i; break; } } for(int i = start_idx; i < arr.length; i++) { if(arr[i] == '3') arr[i] = '4'; }
거의 다왔다. 4,5과정을 거쳐도 코드적으로 해결해야하는 것이 있는데 자릿수가 있다. 아까 그림을 보면 알 수 있듯이 원래 9의 자릿수는 3자리였지만 변환 후의 자릿수는 2자릿수로 문자열을 편집해줄 필요가 있다. 앞에서 부터 0이 안나오는 인덱스를 저장해두어 나중에 substring으로 잘라준다. 그리고 3을 4로 치환한다(5번과정). 이 부분도 시간복잡도는 \(O(log3(n))\)이다.
따라서 최종 시간복잡도는 \(O(log3(n))\) 이다.
테스트
60줄을 넘었는데 다른 풀이는 고작 10줄안에 끝나서 절망했다. 하지만 할 수 있는건 계속 문제를 풀어나가는 수 밖에 없다. n에 나머지 연산을 해주고 나눌 때 3의 배수이면 -1을 해줬는데, 자릿수를 올리지 않기 위해서 그랬다고 하지만, 경험적으로 풀어봐야 이해할듯 말듯하고, 원리에 대해 명쾌하게 설명해주는 블로그가 없어서 아쉬웠다. 이 부분은 좀 더 고민해보고 이 포스트에 보충해서 쓰도록 하겠다.
다트게임을 해서 총 몇점을 득점했는지 계산하는 문제이다. 점수는 0~10점이며 옵션에 따라 점수가 바뀔 수 있다. S는 해당 점수의 1제곱, D는 제곱, T는 세제곱을 하는 것이며, 은 이전 점수와 해당 점수의 2배(만약에 이전 점수가 없으면 해당 점수만 2배 한다.)이다. #은 해당 점수를 빼는 것이다. 과 #은 중첩될 수 있다.
//프로그래머스 문제풀이 level1 다트 게임 publicstaticvoidmain(String[] args) { String dartResult = "1S2D*3T"; int answer = 0; char[] arr = dartResult.toCharArray(); Stack<Integer> s = new Stack<Integer>(); for(int i = 0; i < arr.length; i++) { if(Character.isDigit(arr[i])) { int n = Integer.parseInt(String.valueOf(arr[i])); if(Character.isDigit(arr[i+1])) { n = 10; i++; } if(arr[i+1] == 'S') s.push(Integer.parseInt(String.valueOf(n))); elseif(arr[i+1] == 'D') s.push((int)Math.pow(n, 2)); else s.push((int)Math.pow(n, 3)); } elseif(arr[i] == '*') { if(s.size() == 1) { int n = Integer.parseInt(String.valueOf(s.peek())); s.pop(); s.push(n*2); } else { int n1 = Integer.parseInt(String.valueOf(s.peek())); s.pop(); int n2 = Integer.parseInt(String.valueOf(s.peek())); s.pop(); s.push(n2*2); s.push(n1*2); } } elseif(arr[i] == '#') { int n = Integer.parseInt(String.valueOf(s.peek())); s.pop(); s.push(n*(-1)); } } while(!s.empty()) { answer += s.peek(); s.pop(); } System.out.print(answer); } }
부분부분 살펴보자. 일단 스트링을 문자배열로 쪼갠다음 이 문자를 하나씩 보면서 계산할 것이다. *옵션을 계산하기 위해 스택도 함께 선언하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
if(Character.isDigit(arr[i])) { int n = Integer.parseInt(String.valueOf(arr[i])); if(Character.isDigit(arr[i+1])) { n = 10; i++; } if(arr[i+1] == 'S') s.push(Integer.parseInt(String.valueOf(n))); elseif(arr[i+1] == 'D') s.push((int)Math.pow(n, 2)); else s.push((int)Math.pow(n, 3)); }
에 대해서 처리해주는 부분이다. 일단 들어온 문자가 숫자인지 확인한다. 이때 10에 대한 처리를 따로 한다. 똑같은 1이 들어와도 1일 수도 있고, 10일 수도 있기 때문이다. 이를 알기 위해 다음 문자도 숫자인지 확인하고 숫자라면 n에 10을 대입한다. 그리고 S,D,T에 따른 제곱처리를 하고 스택에 쌓는다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
elseif(arr[i] == '*') { if(s.size() == 1) { int n = Integer.parseInt(String.valueOf(s.peek())); s.pop(); s.push(n*2); } else { int n1 = Integer.parseInt(String.valueOf(s.peek())); s.pop(); int n2 = Integer.parseInt(String.valueOf(s.peek())); s.pop(); s.push(n2*2); s.push(n1*2); } }
숫자와 S,D,T에 대한 처리를 모두 했으니, 다음은 에 대해서 처리하자. 은 이전 점수와 현재 점수를 2배 처리하는 것이다. 이전 점수가 없을 수도 있으니 스택의 사이즈에 따라 달리한다.
1 2 3 4 5 6
elseif(arr[i] == '#') { int n = Integer.parseInt(String.valueOf(s.peek())); s.pop(); s.push(n*(-1)); }
#인경우 스택의 top원소를 빼내어 -1을 곱한 뒤, 다시 집어넣는다. 이 과정을 dartResult가 끝날 때 까지 하므로 여기서의 시간복잡도는 dartResult의 길이를 n이라 할 때, \(O(n)\)이다.
실패율을 계산하는 부분이다. i번째 스테이지에 도달한 사람은 clear[i-1]이다. 3레벨에 도달하는 사람이 2레벨을 통과한 사람인 것처럼(아직 3단계를 통과한 사람들은 아니다!). 지금은 성공률이 아닌 실패율을 계산하는 것이므로 이 사람들 중 통과한 사람의수가 분자에 들어가야한다. 따라서 clear[i-1]-clear[i]가 분자에 올라간다. 스테이지를 통과한 사람이 없을 경우엔 실패율을 0으로 한다. 이 부분에서 시간복잡도는 \(O(N)\)이다.
정렬방식이 특이하게 주어진 경우에는 비교자를 직접 정의하는 것이 좋다. 대신 자바에서는 Integer, Double과 같은 Wrapper 클래스만 비교자 정의를 허용한다. 따라서 int라면 Integer로 꼭 바꿔주자. 자세한 비교 코드는 위 코드를 참고하자. 이 부분에서 시간복잡도는 \(O(NlogN)\)이다.
살짝 복잡할 수 있는데 천천히 읽어보면 이해할 수 있다. 일단 map1에 들어있는 스트링은 한뭉텅이니 char 배열로 쪼개준다. 배열로 쪼개고 나서 이 2진수의 길이가 n이라고 단정할 수 없기 때문에, for문의 범위가 위와 같다. 만약 n=5인데 만들어진 2진수는 010이면 이는 code의 2부터 집어넣어야한다. code1에는 n-code_char.length부터 넣지만 char 배열에선 0부터 값을 꺼내오는 것이므로 k라는 인덱스르 따로 선언해준다. map2에 대해서도 똑같이 해준다. 이 때 손쉬운 비교를 위해 char를 int형식으로 고쳤다.
