[Algorithm] 프로그래머스 - 2020 KAKAO BLIND RECRUITMENT 풀이

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT

문자열 압축

programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

 

시행착오

시행착오
1. 문자열을 무조건 제일 앞부터 잘라야 한다는 조건을 제대로 읽지 않았음.
2. 한번 자른 문자열이 계속 나타나는지 확인하는것이 아니라, 고정된 크기로 자른 문자열이 연속적으로 같은지 판단해야하는데 이 부분을 잘못 이해함
3. 탐색 범위 오류 (i < s.size() / 2) -> (i <= s.size() / 2)
4. 아무런 답도 얻지 못하는 경우 input의 길이를 반환해야함 (한 글자 예외처리 중 발견)

 

소스코드

 

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/String/Solutions/Programmers/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%95%EC%B6%95.cpp

insooneelife/AlgorithmTutorial

 

 

괄호 변환

programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

 

시행착오

string cut = u.substr(1, u.size() - 2); 에서 u.size를 str.size로 잘못 작성함

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp

insooneelife/AlgorithmTutorial

 

 

자물쇠와 열쇠

programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

문제풀이

[모든 회전(0, 90, 180, 270)] *

[모든 가능한 포지션(키가 자물쇠의 왼쪽위에 걸치는 위치부터 오른쪽 아래에 걸치는 위치까지)] *

[모든 키 홈 위치]

위 경우로 만들어진 (키 홈 위치 리스트 == 자물쇠 홈 위치 리스트) 인 경우가 단 하나라도 존재하면 true, 아니면 false

 

시행착오

1. moves의 조합을 만들기 위해 조금 복잡하게 생각함 (단순 iterate으로 가능했는데, 괜히 실제 조합을 구현할까 고민함)

2. moves의 범위를 LockNum으로 이용하여야 했는데 KeyNum을 이용함

3. rotate 후 move를 해야 정상동작함. move 후 rotate을 하면 이상한 값이 만들어질 수 있음

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BruteForce/Solutions/Programmers/%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80%20%EC%97%B4%EC%87%A0.cpp

insooneelife/AlgorithmTutorial

 

 

가사 검색

programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

 

문제풀이

1. 문자열 trie와 역방향 문자열 trie를 만든다.

2. trie에 insert 하는 과정에서, 그 경로에 있는 노드들에 현재까지 거쳐간 문자열들의 길이를 카운팅하는 맵을 만든다.

3. Suffix가 ?인 query가 들어오면 일반 trie에서 prefix를 탐색하고, 마지막 노드에서 카운팅맵을 통해,

(?길이 + Prefix길이)인 문자열의 개수 반환

4. Prefix가 ?인 query가 들어오면 역방향 trie에서 prefix를 탐색하고, 마지막 노드에서 카운팅맵을 통해,

(?길이 + Prefix길이)인 문자열의 개수 반환

 

 

시행착오

1. 동적할당에 대한 메모리 초과 이슈

2. 재귀함수로 인한 스택오버플로우 이슈

3. ????? 예외처리

4. 카운트맵을 미리 만들어서 wildcard 탐색비용 최적화

5. 인덱스 범위초과 (segmentation fault), 정방향, 역방향 트라이를 만들었기 때문에 trie_pool 사이즈도 2배로 해야 함.

6. ????? 예외처리가 시간초과가 되는 케이스, 모든 query가 ????.. 로만 이루어진 경우,

이부분도 따로 사이즈맵을 생성하여 해결

 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Trie/Solutions/Programmers/%EA%B0%80%EC%82%AC%20%EA%B2%80%EC%83%89.cpp

insooneelife/AlgorithmTutorial

 

 

 

기둥과 보 설치

programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

 

시행착오

1. xy 좌표계와 2차원 배열 인덱스의 차이로 인한 예외 발생

2. Get, Set으로 변환과정중 실수 발생

3. 구조물 파괴 시, x, y 위치의 구조물에 대한 테스트를 진행함 -> 그 건물이 아닌 그 주변 구조물에 대해 테스트 해야 함

4. 구조물 파괴 시에 x, y 의 범위값 검사가 유효하지 않다면, 검사 자체를 하지 않아야 함

5. 구조물 파괴 시에 x, y 위치에 파괴대상 구조물이 없다면, 검사 자체를 하지 않아야 함

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Extra/Solutions/Programmers/%EA%B8%B0%EB%91%A5%EA%B3%BC%20%EB%B3%B4%20%EC%84%A4%EC%B9%98.cpp

insooneelife/AlgorithmTutorial

 

외벽 점검

programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

 

문제풀이

[모든 원형 외벽을 기준으로] * [dist의 모든 순열] 

위 모든 경우에 대해 순서대로 채울 수 있는만큼 채우면 됨.

 

환형 자료구조로 효율성이 좋은 queue를 활용하였고,

환형 문제에서 N-1 -> 0 으로 넘어가는 부분에서 생기는 예외를 피하기 위해, weak[i] 위치를 weak[i + 1] - weak[i] = 거리로 변환하여 활용함.

 

시행착오

1. cmath (pow 함수) 프로그래머스 런타임 에러 (이게 컴파일타임 에러지 왜 런타임 에러인가?)

2. 선택여부에 대한 조합은 필요가 없었음 (오히려 예외가 생김)

3. 모든 외벽을 기준으로 시도해야 함

4. 회전방향은 고려할 필요가 없었음 (CW 방향으로 가능한 케이스는 CCW 방향으로도 항상 가능하기 때문에 탐색공간을 축소시킬 수 있음)

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BruteForce/Solutions/Programmers/%EC%99%B8%EB%B2%BD%20%EC%A0%90%EA%B2%80.cpp

insooneelife/AlgorithmTutorial

 

 

블록 이동하기

programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

 

 

문제풀이

1. 정수 2D 벡터 구현

2. Robot의 상태 정의 (벡터 left, right)

3. Robot 위치 이동, 위치 검사 기능 구현

4. Robot 회전 이동, 회전 검사 기능 구현

5. BFS 구현

BFS의 상태는 로봇의 상태를 이용하고, 상태 방문여부는 set을 이용함

(상태공간의 크기는 left[100* 100] * right[100 * 100] = 100000000 으로 아슬아슬함)

선택가능한 행동은,

이동 [상, 하, 좌, 우]

회전 [왼쪽기준 CCW, 왼쪽기준 CW, 오른쪽기준 CCW, 오른쪽기준 CW]

 

 

시행착오

1. DirectionsCCW 에 잘못된 값이 들어가 있었음

2. Move에서 특정 방향일 때 선별적으로 SetBoard를 해줄 필요가 없었음 (시간 조금 낭비)

3. IsParallel과 IsOpposite은 만들어놓고 사용된적이 없음

4. GetState()에서 sort를 해주는 것은 상태를 파괴하는 일이었음 (원래는 상태의 정규화를 목표로 했지만, left와 right의 순서도 상태에 영향을 주는 것을 간과함)

5. robot의 미래 State을 갖고 visited에서 검사 후 움직여야하는데, 그러려면 로봇을 직접 움직인 후 검사해야함.

그리고 로봇이 움직이려면 먼저 CanMove로 체크를 해야함.

문제는 CanMove와 visited 검사를 동시에 하려고 해서 발생함.

6. 사실 로봇에서 SetBoard는 필요가 없음. 만들어뒀지만 쓰이지 않음 (디버깅 외에는 의미가 없음)

7. 종합적으로 오버엔지니어링이 많았던 문제였음

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/Solutions/Programmers/%EB%B8%94%EB%A1%9D%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial