코딩테스트 문제후기

제로베이스 코딩테스트 연습문제 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로 조작

 

 

 

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-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을 연습할것

-