Java 코딩테스트 연습 10일차 (프로그래머스 스쿨 Lv.0, 1130점)

오늘과 내일, 모레는 lv.0 문제를 정답률 낮은 순으로 3문제씩 풀고, 글피부터 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편에 나오는 문제를 풀기 시작할 예정이다. 원래 오늘과 내일 5문제씩 풀 예정이었지만 예상보다도 시간이 너무 오래 걸려서 하루 연장했다. 마지막 문제는 정답률이 29%라 어차피 못 풀 것 같기에, 마지막에 시도해 보고 실패하면 나중에 다시 풀어 보기로 했다. 마음 같아서는 lv.0 문제를 다 풀어보고 싶지만 Java 공부를 메인으로 하며 병행하다 보니 너무 오래 걸릴 것 같다. 앞으로 풀 것은 어려운 문제들이라 하루에 푸는 문제 수는 더 적어지겠지만, 얻는 것은 더 많을 것이다.

 

4월 5일부터 프로그래머스 스쿨에서 진행하는 코딩테스트 실력 UP 패키지 수업을 등록했는데, 수업을 따라가려면 lv.2 문제 정도는 스스로 풀 수 있어야 된다고 한다. 원래 이번 달에 듣고 싶었으나 실력이 안 돼서 듣지 못했다. 따라서 교재를 통해 이론 공부와 함께 어려운 문제 풀이를 해야 할 필요성이 있다. 개강 전까지 lv.2 문제를 해결할 실력을 쌓는 게 가능할지 모르겠지만 최선을 다해 볼 생각이다.

 

 

 

---

 

 

문자열 밀기

 

 

 

 

목록을 보니 정답률 낮은 순의 10문제 중 두 문제(3일차 분수의 덧셈, 4일차 최빈값 구하기)는 이미 풀었다. 따라서 12번째 문제부터 풀게 되었다.

 

정답률 낮은 순으로 정렬하니 그동안 풀어 왔던 문제들과 달리 다소 어려운 문제가 나온다. A의 문자열을 그대로 오른쪽으로 옮겼을 때 B와 같은 문자열이 되는지 묻는 문제다. 문자열을 복사해서 연장할 수 있으면 좋을 것 같은데, 방법을 모르기 때문에 A의 마지막 문자는 B의 첫 번째 문자와 비교하는 식으로 풀 수밖에 없을 것 같다.

 

 

 

 

A와 B가 같으면 바로 return하고, C의 다음 자리에 A의 문자가 대입되도록 했다. A에는 변경된 C의 값을 대입한다. 이렇게 변경된 A의 값을 가지고 A와 B가 같아질 때까지 같은 과정으로 for문을 돌린다. while문이 소득 없이 한 바퀴 돌아서 count가 A 문자열의 길이만큼 쌓이면 A와 B가 다르다는 뜻이므로 -1을 return한다. A와 B가 같아서 while문을 빠져나온다면 누적된 count만큼의 answer 값을 return한다.

 

그런데 값이 -1밖에 나오지 않는 것 같다. 뭔가 문제가 있다.

 

 

 

 

A의 마지막 문자를 더해 주는 식을 for 반복문 안에 넣었었다. 이러면 C는 이 문자를 계속해서 누적하게 된다. 이 부분은 수정했지만 문제는 아직도 해결되지 않았다.

 

 

 

 

A = C도 for 반복문 안에 넣었었다. 이러면 A는 계속 C를 대입해 C의 A 대입식에도 역으로 영향을 끼치게 된다. 이걸 수정했더니 실행 시간이 10초를 초과해 버린다. 시간 복잡도는 한참 남았다고 생각했는데 어떻게 최대 10억 번이 넘을 수 있는지 이해가 되지 않는다.

 

 

 

 

count 식도 for 반복문 안에 넣었었다. for 반복문이 최대 98번 돌아갈 동안 count도 그만큼 연산을 하고 있었던 것이다. 그걸 while문이 다시 최대 99번 돌린다. 그래도 어디서 10억 번이 되었는지 모르겠다. 게다가 반복문 안에서 하는 덧셈 수행은 산술 연산이라 시간 복잡도에 큰 영향을 끼치지 않을 것으로 생각했다. 어쨌든 이런 사소한 실수를 자꾸 하면 앞으로의 공부가 더 어려워진다. 항상 꼼꼼히 확인해서 실수하지 않는 습관을 길러야 한다.

 

 

다른 풀이 1

 

repeat라는 이름만 보고도 어떤 method인지 예상이 가능하다. 역시 이런 기능이 없을 리 없다. 찾을 때는 indexOf 메소드를 이용해 몇 번째 위치에 있는지 찾아서 바로 return하는 방식이다. 확실히 좋아요를 많이 받을 만한 좋은 풀이다. 복잡한 내 풀이와 비교된다ㅠㅠ

 

 

다른 풀이 2

 

 

문자열 변수끼리 더할 수 있는지 몰랐다. 앞의 풀이보다도 간단하게 한 줄로 끝난다. 이런 간결한 풀이를 지향해야 내 풀이과정처럼 실수를 하는 일이 줄어들 것이다.

 

 

저주의 숫자 3

 

 

 

 

원래의 n에 3의 배수나 3이 포함된 숫자를 더하는 문제다. 어떻게 할지 구상하는 데 생각보다 오래 걸렸다.

 

 

 

 

한 번에 답이 나오는 경우가 흔치 않은데 바로 나왔다.

 

i와 n이 같이 더해지면서 정확히 n번 동안 반복문을 수행하는 방식이다. i는 1부터 점점 커지면서 3의 배수 또는 3이 포함된 숫자가 될 때마다 1씩 더하고, 반복문의 길이를 유지하기 위해 n도 같이 더한다.

 

3이 포함된 숫자를 구하는 i % 10 == 3 조건문이 3의 배수 조건문 앞 뒤로 두 번 중복으로 쓰였는데, i와 n을 더하지 않고 그냥 지나가는 경우를 방지하기 위함이다. 예를 들어 3이 포함된 23에 1을 더해 3의 배수인 24로 만들었다면, 조건문이 끝나기 전에 3의 배수 조건문을 수행해야 누락되지 않는다. 반대로 3의 배수인 42에 1을 더해 3이 포함된 43이 되는 경우도 마찬가지다. 더 효율적인 방법도 있을 테지만 일단 생각나는 방법은 이 방법이었다.

 

30이나 130이 되었을 때는 10을 더해 주는데, 30은 조건문 앞에 있고 130은 조건문 뒤에 있다. 이는 30의 경우 3의 배수가 아닌 29에서 더해지므로 3의 배수 식에 들어가기 전에 조건문 앞에서 40으로 미리 만들어 주는 것이고, 130의 경우 129는 3의 배수이므로 129에서 3의 배수 식으로 1을 더해 준 뒤 조건문이 끝나기 전에 140을 만들어 주기 위함이다. 그렇지 않으면 누락되어 버린다.

 

 

다른 풀이

 

 

contains 메소드를 이용해 푼 solution이다. contains 메소드는 생각하지 못했다. 내 풀이보다 훨씬 간결한 데다가, 내 풀이는 n의 범위가 넓어지게 될 경우 230, 430 등의 위치와 300, 3000 등에 관한 조건식도 추가로 고려해야 한다. 따라서 이 풀이가 훨씬 좋은 풀이다.

 

 

다항식 더하기

 

 

 

 

다항식을 정리하는 문제인데, 보기에는 간단해 보였으나 푸는 데 시간이 엄청 오래 걸렸다.

 

 

 

 

처음에는 삼항 연산자를 이용해 봤는데, 오류도 떴지만 식이 알아보기 정말 힘들다. 역시 삼항 연산자는 한계가 있는 것 같다. 그래서 if-else 문으로 수정했다.

 

 

 

 

반복문 두 개와 indexOf 메소드를 이용해 원하는 값을 찾은 뒤, 변수의 계수를 더하는 coefficient 변수와 상수를 더하는 contant 변수로 나눠서 계산했다. 아래쪽은 answer를 case 별로 나눠서 출력하는 식이다.

 

그런데 뭔가 풀이가 꼬였는지 답이 이상하게 나온다. 계수도 상수도 엄청나게 중복되어 계산되고 있는 모양이다.

 

 

 

 

9번째 줄의 j가 문자열 안에 포함되어 있었다는 것을 알게 되었다. 이러면 j에 대입된 숫자가 아니라 문자열 "jx"를 찾게 된다. 수정했지만 여전히 숫자가 이상하게 나온다.

 

 

 

 

i의 범위를 50이 아니라 polynomial 변수의 길이까지로 바꿨다. 값이 달라졌지만 여전히 이상하게 나온다.

 

 

 

 

i와 j 반복문 안에 i나 j와 관련 없는 식들이 들어 가 있는 것이 원인임을 알게 되었다. 반복문 변수에 의존적이지 않은 식들은 조건만 맞으면 반복문이 진행되는 동안 항상 작업을 수행한다. 앞으로 반복문 변수와 관련 없는 식은 계속적인 반복이 필요치 않은 경우 무조건 밖으로 빼는 습관을 들여야겠다.

 

어느 정도 값이 가까워졌지만 아직도 같아지지는 않는다. 여러 번 수정해서 결국 테스트 1은 통과했지만, 테스트 2는 끝까지 2x로 나왔다.

 

한참 고생한 끝에야 알게 되었는데, 이 구조로는 결국 원하는 답을 얻기가 힘들다. indexOf 메소드가 문자열에 포함된 모든 해당사항을 찾아 주는 줄 알았는데, 처음 나온 것만 찾아 준다. 그래서 "x + x + x" 문자열에서 앞의 "+ x"는 찾지만, 뒤의 "+ x"는 찾지 않고 넘어 가 답이 "2x"가 나오는 것이다. indexOf 메소드를 조금만 사용해 보면 알 수 있는 기본적인 사항일 텐데, 놀랍게도 나는 이 사실을 몰랐다. 이제라도 알게 되어 다행이다.

 

따라서 이 방법을 깔끔하게 포기하고, 생각해 두었던 split 메소드를 이용하기로 했다.

 

 

 

 

" + "를 기준으로 분할해 변수 부분은 x를 제거한 뒤 coefficient 변수에 더하고, 상수 부분은 그대로 constant 변수에 더하는 방식이다.

 

이 방법은 훨씬 간편할 거라 생각했는데, 생각보다 쉽지 않다. NumberFormatException이 발생해 버렸다. 하나씩 점검하다가 결국 split 메소드가 제대로 작동하지 않았다는 사실을 알게 되었다.

 

해결이 안 돼 구글링을 진행해 본 결과, +를 분할하려면 앞에 \\ (escape 문자)를 붙여야 한다는 사실을 알게 되었다. +는 원래 문자열에서 escape 문자 없이 사용할 수 있기 때문에, split 메소드에서 이게 안 되리라고는 생각도 못 했다.

 

 

 

 

처음엔 원인을 몰라 아래의 answer 출력 조건식을 if-else 조건문으로 바꿔 보기도 했다. 결국 이게 원인이 아니었다는 사실을 알게 되어 다시 원래의 간결한 식으로 되돌렸다.

 

 

 

 

결국 실행시키는 데는 성공했지만, 테스트 2의 결과값이 이상하게 나왔다. 변수만 있는 경우를 따로 나누지 못한 것이다.

 

 

 

 

수정해서 테스트까지도 통과했는데, 제출하니 몇 개에서 문제가 발생했다. 원인을 찾아내기 위해 테스트 케이스를 추가했다.

 

 

 

 

운이 좋아 금방 찾을 수 있었다. 이번엔 상수만 있는 case가 따로 고려되지 않았다. 모든 case를 다 고려한 줄 알았는데 이렇게 많이 빠져 있었다. 이럴 줄 알았으면 다소 길더라도 빠짐없이 모두 고려하는 위의 if-else 식을 쓰는 편이 훨씬 나을 뻔했다.

 

 

 

 

" + " 를 따로 빼서 조건에 맞을 때만 넣어 주도록 수정해 결국 성공했다.

 

 

 

 

정답률이 낮은 문제들은 점수도 많이 퍼 준다. 오늘은 세 문제밖에 못 풀었는데도 30점이나 획득했다. 하지만 이 문제를 푸는 데 너무나 많은 시간을 소모했다. 정말 오래 걸렸다.

 

 

다른 풀이

 

 

요구하는 출력값이 까다로운 만큼 대부분의 풀이는 엄청나게 길다. 내 풀이가 오히려 짧은 편으로 보인다. 위의 풀이가 가장 짧은 풀이 같다. split 메소드와 삼항 연산자, replaceAll 메소드를 이용했다. split은 "+"가 아니라 공백을 기준으로 나누고, equals 메소드를 이용했다. 삼항 연산자의 지독한 가독성은 여전하다.