코딩테스트 문제풀이 코드리뷰
코딩테스트를 위한 자바활용 팁.
0. 시간복잡도 제한은 1초당 약 2천만, 5초당 1억정도로 잡는다
1. 시간절약이 필요한 경우에는 Scanner보다는 BufferReader, Split보다는 Stringtokenizer을 사용한다
2. 숫자로 된 String의 조회탐색을 위해서는 toCharArray을 사용할 수 있다
- 숫자의 자릿수 분리를 위해서는 %와 /연산을 활용한다
- char은 parseint가 불가하므로 ASC code를 활용하여 int로 변환해야한다
문제접근방식
1. 연역적 탐구방식 : 수학적 논리관계를 통해서 답을 도출해낼 수 있을때
2. case by case 분석 : 어떤 solution으로 도달할 수 있는 방법들을 MECE하게 나열하고, 하나씩 고려해서 불가능하면 소거하는 방식
3. 시행착오법(trial and error) : 하나씩 test case를 대입해서 패턴을 찾고 일반화하는 방법
4. divide and conquer : 부분의 패턴을 확인하고 이를 전체로 확장해나가 전체 문제를 푸는 방법
코딩테스트 문제별 배운점
1. 백준 25556번
- 시간 제약의문제로 Sin Scanner가 아닌 BufferReader/StringTokenizer(공백이 있을때)을 사용해야 함
- Sout도 println보다는 BufferWriter로 출력한다
자바로 백준 풀 때의 팁 및 주의점 (boj java)
2. Zerobase Java 연습문제 3-1의 Practice1 , 빗물트래핑
- 한가지의 배열이라고 하더라도 복수의 index를 설정하여 그 index의 움직임 로직을 다르게 설정하여 문제를 해결함
- 이를 투포인터 (리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘)라고한다
https://www.acmicpc.net/problem/14719
3. Zerobase java 연습문제 3-1 Practidce2
- Direct Access Array에 intrinsic한 index의 내용물에 특정 표기를 하고 싶으나, 내용물이 이미 들어가있다면 (-)부호를 붙이는 것도 한가지 방법이다
-부호도 유효한 표기이다
4. 프로그래머스 Priority queue 구현
- API의 활용성때문에 가급적 Array는 쓰지말고 CollectionFramework를 사용할것. (Array는 최적화를 위한 Refactoring할때만 사용)
https://school.programmers.co.kr/learn/courses/30/lessons/42587
5. 행성 X3 - XOR비트연산
- 비트연산도 출제가 될 수 있음
- 직접적으로 계산하여 계산 값의 합계를 구하는 문제인데, 직접적으로 계산하는 방법이 불가하다면, 합계를 direct로 구할 수 있는 방법이 있을지 고민해볼것
https://www.acmicpc.net/problem/2830
제로베이스 코딩테스트 연습문제 1-2. 1번 문제
- 문제분석 : '.'가 n개가 있고 s(string)이 같이 붙어있을때, 시간초(t)의 흐름에 따라 보여주는 전광판 n개 문자가 다르게 하라.
- 나의 접근 : '.'n개와 s를 +로 하나의 string으로 병합하고 병합된 string을 chararray로 만들어 index를 조정해서 char을 추출후 새로운 string으로 만듬
- 대안풀이 : 최초에 모두 chararray로 만들어 병합하고 조회해서 새로운 chararray를 도출한 후
- 대안풀이2 : 큐를 사용해서 '.'과 s를 병합한뒤, poll을 사용해서 원하는 string 순서를 만든후 원하는 개수만큼 stringbuilder에 append하여 string으로 최종변환.
- 배운점 : 1. string은 입력과 출력에만 사용하고, 중간과정에서 조회할때는 chararray, 2. 수정할때는 stringbuilder를 사용하므로 이들의 숙련도를 높일 것
제로베이스 코딩테스트 연습문제 1-2. 2번 문제
- 문제분석 : '.' '!' '?' ' '를 구분자로 사용하여 string에서 숫자와 문자로된 단어들을 추출하고 뒤집은 후 string 배열을 출력하라
- 나의접근 : 1. 문자를 뒤집기위해서 기능을 직접구현함; string을 chararray로 변환후 순회하여 순서를 뒤집음 2. string을 chararray로 변환한 후 하나씩 조회하여 구분자가 아닌 것을 만나면 string temp에 +하였고 구분자를 만나면 temp를 arraylist에 append한 후 초기화함. 그 후 array list
- 대안풀이 : 1. stringbuilder에서 reverse method사용하여 순서 변환 2. 구분자들을 하나의 string으로 합치고 string을 chararray로 순회하여 string.indexof 혹은 character.isdigitorletter을 사용하여 구분자인지 확인 후 index값을 확인해서 substring/stringbuilder.append를 사용하여 단어를 추출함.
- 대안풀이 : 2. 여러가지 구분자들을 ' '으로 replaceall하여 split하는 방법으로 사용.
- 배운점 : 1. arraylist에서 array로 직접적으로 바꾸는 방법 2. stringbuilder에서 reverse method로 조작
제로베이스 코딩테스트 연습문제 1-2. 3번 문제
- 문제분석 : 배열 내 숫자들의 최대공약수를 구하라
- 대안풀이 : 1. 두수의 최대공약수를 구하기 위한 유클리드 호제법을 별도로 재귀함수를 사용하여 method 구현함 2. 0번과 1번을 호제법을 사용하고 그 결과를 2번과 호제법을 사용하는 식으로 최대공약수를 구함
제로베이스 코딩테스트 연습문제 1-3
- 응시후기 : 시간에 쫓기지말고 손으로 문제분석부터 기본코딩까지 완료된 후에 코딩으로 들어가는 것이 오히려 시간절약적이다. 마음을 급하게 먹지않는 방법을 연습이 필요하다.
제로베이스 코딩테스트 연습문제 1-3 4번문제
- 문제분석 : "-3+26-7"과 같은 string을 숫자와 연산으로 분리하여 각 연산들을 실행하라
- 나의 접근 : 각 문자를 순회하여 stringbuilder에 append하고 '-'와 '+'를 만날때마다 stringbuilder를 배열에 입력후 초기화함. 그후 배열을 읽어들여 계산함
- 대안풀이1 : stringbuild하지 않고 각 digit을 int로 변환하고 int가 2번나오면 기존 int*10하여 +-만나면 별도 연산함
- 대안풀이2 : string을 replace all하여 split하기 편하도록 숫자간 ' '을 입려하고 +을 제거함. 그후 split한 배열의 한칸씩 int로 변환하여 풀이함
제로베이스 코딩테스트 연습문제 1-3 4번문제
- 문제분석 : 2진수 숫자를 10진수로 변환하고 10진수 숫자간에 XOR(^)연산을 실행
- 나의 접근 : 2진수를 10진수로 메뉴얼로 변환하는 함수작성함
- 대안접근 : parseInt(string,2)를 사용하면 2진수를 10진수로 변환가능함.
제로베이스 코딩테스트 연습문제 2-1
전반적으로 평이한 난이도로 배운 점만 간략하게 작성
- 나의접근 1. reverse sort를 위해서 array를 stream을 활용해서 arraylist로 변환하여 sorting함
- 대안접근 1. array로 sort한 후 맨 뒤 index에서부터 순회함
- 나의접근 2. 배열을 순회하여 max값과 min값을 찾아내고 전체 sum에서 max와 min을 빼기함.
- 대안접근 2. 배열을 sorting하여 첫번째와 마지막 값을 제외하고 sum을 진행
- 문제분석 : 두 숫자 배열의 중복된 값을 찾아 새로운 리스트로 만드는 문제
- 나의접근 3. check 배열을 2개 만들어서 배열을 순회하여 해당하는 인덱스에 값을 ++ 하여 2가지 배열에 모두 체크된 값 list에 넣기
- 대안접근 3. hashset에 배열의 값을 넣고 contains를 통해서 값을 체크함 (set은 hashtable구조로 인해 시간복잡도가 낮음)
제로베이스 코딩테스트 연습문제 2-2
-나의접근 1. 10만이하 값의 숫자의 1개 혹은 2개인지 확인하기 위해서 int[10만]을 선언하고 하나씩 ++하여 셈
- 대안접근 1. 각 값을 hashmap의 key값으로 사용해서 하나씩 ++하여 셈
- 대안접근 2. 모든 값들을 ^(xor)연산을 해서 동일한 값이 2번 연산되면 0으로 초기화 되는 점을 활용하여 1개인 숫자를 찾아냄
제로베이스 코딩테스트 1차 총평
- 문제풀이후기 : 1. 인지하고 있는 부분이지만 충분한 문제독해와 분석이 선행된 후에 코드작성으로 들어가야한다. 그렇지 않으면 시간낭비가 상당하다. 손으로 문제를 풀지 못하는 문제는 내가 풀수없는 문제로 치부해야할 것이라. A. 문제분석 B. 풀이완성 C. 손코딩 총 3단계를 거친 후에 문제풀이에 들어가야한다. 2. 코딩 작성시에 약 20~30분 내에 풀리지 않는 문제는 바로 넘어가는 자세가 필요하다. + DFS와 순열조합문제에 좀 더 신경써야겠다.
제로베이스 코딩테스트 3번문제 (DP문제 기본)
- 문제분석 : 점화식 구조로 n항의 부분을 divide and conquer관점으로 바라보면 n항 이전의 모형이 중첩되는 것을 확인가능.
- 접근 : 블럭을 쌓을때, 어떤 블럭이든 반드시 거쳐야하는 경우의 수를 casebycase로 따져가면서 실마리를 찾는다. 점화식
제로베이스 코딩테스트 4번문제 (DFS와 bloodfill응용)
- 문제분석 : 독특한 형태의 좌표이동을 이동거리를 다르게 하여 무한하게 반복하여 프렉탈 구조를 만듬. divide and conquer로 어떻게 구혀할것인지?
- 접근 : 이동좌표를 별도로 정의하고, 이동거리를 변수로 두어, for문으로 반복한다. DFS로 막연히 구연하기 전에, for문을 통해 구조적으로 바라보자, for문 분기 개수가 주어진 이동거리에 따라 다르기 때문에 dfs를 사용하고 이동거리/2를 각 레벨마다 진행후 이동거리 1이 될때부터 bloodfill을 진행.
제로베이스 코딩테스트 5번문제 (DFS와 순열조합응용)
- 문제분석 : 교실 M개의 수용인원이 배열의 형태로 주어져 있고, 학생 N명을 배치시켜야 할때 어떻게 풀것인가? (수용인원>=N)
- 접근1 : 학생이 교실을 뽑는 형태를 생각해볼수있다. DFS로 Level N까지 탐색을 하면서, 각 탐색마다 for문으로 교실의 개수만큼(M번) 분기하고, for 변수에 따라서 수용인원을 해당 index에 -- 해주면 각 학생이 교실을 선택하는 모든 경우의 수를 셀 수 있음.
- 접근2: 교실이 학생을 뽑는형태를 생각해볼수있다. 우선 교실별 학생인원 배치 (a,b,c)가 a+b+c=N인 경우의 수 전체를 탐색해야한다. 이는 DFS로 수용인원을 감소시키면서 case by case로 따져보면 전체 경우의 수 순회가능
- 배울점 : A. DFS는 유연성이 가미된 For문으로 생각해볼 수 있으므로 for문으로 전체 경우의 수 탐색이 가능한지 확인해볼 것. (Tree도식을 활용) B. 일반 수학과 달리 터무니없이 많은 경우의 수 counting이라고 프로그램으로 counting하는 것이니 해당 방법을 폐기할 근거는 되지 않는다는 점을 기억할것. C. 순열과 조합을 for문으로 간단히 표현하는 법 배우기.
제로베이스 코딩테스트 2차 문제3(스택)
- 문제분석 : {}괄호 내의 문자열을 인식하고 그 안의 문자열을 조작한다. {}괄호가 중첩문으로 여러번 적용되기때문에, 1. 문자열의 순서가 유지되고 2. 문자열 내에서 불필요한 문자를 쉽게 제거할 수 있는 stack구조가 적합하다.
제로베이스 코딩테스트 3차 총평
1. 이제는 문제의 로직과 구현 뿐 아니라 시간 복잡도에 대해서도 계산 후에 코드로 옮길것
2. BFS,DP에 대해서 심화하여 학습할 것
3. 전부다 맞추려고 하기 보다는 3개 맞추는 것을 목표로 할 것.
4. 볼펜대신 샤프와 지우개를 사용해서 문제를 풀것
5. 코드에 반드시 주석을 다는 습관을 들일것
문제2 (greedy)
문제분석 : 100개의 숫자를 +와*로 중복조합하여 특정숫자를 만들수 있는 최소의 경우의수를 구하라, 100개의 숫자로 조합이 불가하면 -1을 반환.
나의접근 : DFS로 100개의숫자와 +*의 2가지 경우의 수를 조합하여 200가지를 모두 dfs로 level 100까지 탐색함.
대안접근 : 우선, 각 숫자들의 조합을 하나 하나 대입계산하여 결과를 보고, 거기서 아이디어와 패턴를 도출하여 문제를 해결, 이 경우 중복되는 숫자가 많아 이를 제외할 경우 경우의수가 상당히 줄어들게됨.
문제3 (DP)
- 한번 분열하면 1개는 분열을 지속하고 한개는 delay초 이후 재분열을 하는 아메바가 있을때, delay초와
- 나의 접근 : DP문제인지 인지를 하였음에도 경험부족으로 어떻게 접근해야할지 몰랐음
- 대안 접근 : case by case로 우선 성실하게 하나씩 계산 및 그려보고, divide and conquer의 관점에서 나눠서 전체를 구성하려는 마음가짐, 점화식을 구현하기 위한 패턴을 확인해야함.
- 대안 접근2 : 객체지향의 관점에서 아메바를 class로 표현하고 delay를 속성으로 표현해서 아메바의 움직임을 실제로 구현해서 풀어 내기.
문제5
- 나의 접근 : 1. DFS의 인자를 다음레벨에 건널때 변경한것이 아니라 DFS문 내부에서 변경을 하였음 2. for문의 분기를 착각함
- 대안접근1 : DFS인자는 local 범위에서 변경해서는 안되고 인자 전달 과정에서만 변경해야함.
- 대안접근2 : 최단거리문제는 BFS를 사용하여 푼다.
- 대안접근3 : DFS 중 효과정인 cut-edge방법은 set을 활용한 중복성 제거가 있음.
제로베이스 코딩텍스트 4차
문제4
- 분석 : 3가지 요소를 갖춘 데이터구조를 sorting 해야하는 문제
- 나의 접근 : list within list를 사용하여 sorting하려고 하였으나 comparator 사용 미숙으로 sorting불가
- 대안접근 : 여러가지 요소를 하나로 묶어야할 경우 list within list같은 구조보다는 custom class를 사용하여 sorting
- priority que, comparator 학습필요.
제로베이스 코딩테스트 5차
- 문제2 : comparator을 활용한 sorting을 연습할것
-