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

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

오픈채팅방

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

코딩테스트 연습 - 오픈채팅방

 

시행착오

1. 빈 log를 answer에 집어넣음

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/Solutions/Programmers/%EC%98%A4%ED%94%88%EC%B1%84%ED%8C%85%EB%B0%A9.cpp

insooneelife/AlgorithmTutorial

 

실패율

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

코딩테스트 연습 - 실패율

 

시행착오

x

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/PartialSum/Solutions/Programmers/%EC%8B%A4%ED%8C%A8%EC%9C%A8.cpp

insooneelife/AlgorithmTutorial

 

 

후보키

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

코딩테스트 연습 - 후보키

 

문제풀이

후보키의 컬럼 선택에 대한 모든 조합을 만들기 위해 bitmask를 이용한다.

1부터 2^N 까지의 값을 생성하여 bitmask로 표현한다.

bit	n
00000001	1
00000010	2
00000011	3
00000100	4
...
11111111	255

 

각 비트마스크에 대해, 후보키인지 저장하기위한 배열을 생성한다. (vector<bool> candidate_flags)

각 비트마스크에 대해, 이 비트가 1이면 컬럼을 포함하고, 0이면 컬럼을 포함하지 않는다.

모든 로우에 대해 선택된 컬럼들을 튜플로 하는 데이터를 생성한다. (vector<string>에 저장)

해당 튜플 데이터가 중복이 하나라도 있다면, 후보키가 될 수 없다.

모든 로우에 대해 중복이 없는 경우에, 해당 비트마스크를 체크한다 (candidate_flags[n] = true)

 

여기까지 수행하면, 유일성을 갖는 컬럼 조합은 candidate_flags[i]를 true로 갖게 된다.

하지만 어떤 유일성을 갖는 튜플 조합이 자신보다 적은 조합으로 유일성을 갖는다면 후보키의 조건에서 벗어나기 때문에, 그 부분에 대한 처리를 해주어야한다.

 

다음과 같이 유일성을 갖는 컬럼 조합이 있다고 가정해보자.

bit	유일성
00001010	true
00001101	true
00001011	true

 

여기서 첫번째 비트로 표현된 컬럼 조합은, 세번째 컬럼 조합에 완전히 포함되기 때문에, 세 번째 조합은 유일성을 갖더라도 후보키가 될 수는 없다.

반면 두번째 컬럼 조합에는 첫번째 컬럼 조합이 갖지 못한 컬럼이 있기 때문에 해당사항이 없다.

 

이 작업을 위해 모든 비트마스크 i에 대해,

모든 i보다 큰 비트마스크 j에 대해,

if (candidate_flags[i] && (i & j) == i) 를 만족하는 경우, 비트마스크 j는 후보에서 제외시킨다.

 

이후 후보키(candidate_flags가 true인 케이스)를 카운트해서 출력해주면 된다.

 

 

시행착오

1. 어떤 비트마스크에 대해 true이면 그 비트를 포함하는 모든 비트마스크는 false로 처리하는 부분에서 조건 누락.

if ((i & j) == i) (오류)

if (candidate_flags[i] && (i & j) == i) (수정)

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Bitmask/Solutions/Programmers/%ED%9B%84%EB%B3%B4%ED%82%A4.cpp

insooneelife/AlgorithmTutorial

 

 

무지의 먹방 라이브

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

코딩테스트 연습 - 무지의 먹방 라이브

문제풀이

다음과 같은 원소집합을 가정해보자.

15  1  150  2500  159  70000

 

사이클이 돌면 결국 가장 작은 숫자인 1이 제거될 것이다.

시간은 6만큼 지나간다.

14  0  149  2499  158  69999

6

 

또 계속 사이클이 돌면 가장 작은 숫자인 14가 제거된다.

시간은 5 * 14만큼 지나간다.

0   0   135  2485  144  69985

 

다음으로 135가 제거된다.

시간은 4 * 135만큼 지나간다.

0   0   0   2350   9    69850

 

즉, 사이클이 돌 때마다 elapse = (min(현재원소집합) - min(이전원소집합)) * (원소집합의 크기) 만큼씩 시간이 지나간다.

k = k - elapse;

 

여기서 k가 충분히 크다면, 원소집합이 비어버릴때까지 계속 수행하게 될 것이다.

하지만 k가 충분히 크지 않은 경우, 원소집합의 중간에서 k가 음수가 될 것이다.

이 경우 사이클을 멈추고 다음 작업을 수행한다.

 

남은 원소들을 번호순서대로 나열한 후,

k가 음수가 되기 이전의 k값을 가져와서,

그 값이 0이 될 때까지 위 원소들을 순회하며 번호를 찾아준다.

(사실 이 부분에서 순회할 필요 없이 모듈러 연산 후 인덱스를 통해 번호를 찾아주면 된다.)

 

 

시행착오

1. prev_k - 1 (오류)   prev_k (수정)

2. k가 음수가 되며 중간에 루프가 중단되는 경우, pq의 원소들을 나열하여 k의 위치를 찾아주는 추가 코드가 필요함.

코드에서는 모듈러 연산을 이용함 

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Greedy/Solutions/Programmers/%EB%AC%B4%EC%A7%80%EC%9D%98%20%EB%A8%B9%EB%B0%A9%20%EB%9D%BC%EC%9D%B4%EB%B8%8C.cpp

insooneelife/AlgorithmTutorial

 

 

길 찾기 게임

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

코딩테스트 연습 - 길 찾기 게임

문제풀이

기본적으로 BinarySearchTree를 구현하면 해결할 수 있는 문제이다.

다만 트리에 원소를 삽입하는 순서에 따라 요구사항에 맞는 트리가 만들어지지 않을 수 있다.

삽입 순서는 트리의 y값을 기준으로 내림차순 정렬하여 루트부터 리프까지 레벨 단위로 삽입되도록 하고,

각 레벨에서는 x값을 기준으로 오름차순 정렬하여 왼쪽부터 오른쪽으로 삽입되도록 한다.

 

시행착오

1. 트리 삽입순서를 만들기 위한 정렬 정책을 잘 생각해야한다.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/Solutions/Programmers/%EA%B8%B8%20%EC%B0%BE%EA%B8%B0%20%EA%B2%8C%EC%9E%84.cpp

insooneelife/AlgorithmTutorial

 

 

매칭 점수

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

코딩테스트 연습 - 매칭 점수

 

시행착오

1. "/>" 문자열로 탐색 시, 앞에 공백이 있는 경우가 있으므로 "\"" 문자열로 탐색해야함

int to = page.find("/>", from); (오류)

int to = page.find("\"", from + 1) + 1; (수정)

 

2. 문자열 탐색 위치 버그 (탐색 시작위치를 누락함)

int end = body.find(">"); (오류)

int end = body.find(">", start); (수정)

 

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/String/Solutions/Programmers/%EB%A7%A4%EC%B9%AD%20%EC%A0%90%EC%88%98.cpp

insooneelife/AlgorithmTutorial

 

 

블록 게임

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

코딩테스트 연습 - 블록 게임

 

 

문제풀이

1. 탑다운 Black 블록을 내린다 (두 번 수행)

2. 직사각형 검사 및 직사각형 제거

3. Black 블록 복구

4. 위 과정을 N번 반복한다.

 

 

시행착오

1. 기역자 모양이 세워져 있는 경우까지 해결하기 위해 2개 라인을 Black으로 채운 후,

직사각형으로 테스트해볼 필요가 있다.

2. 직사각형 테스트 중, 직사각형 모양이 나오더라도 Black의 개수가 더 많은 케이스는 유효하지 않은 케이스이다.

 

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Extra/Solutions/Programmers/%EB%B8%94%EB%A1%9D%20%EA%B2%8C%EC%9E%84.cpp

insooneelife/AlgorithmTutorial