[Algorithm] 프로그래머스 - 2019 카카오 개발자 겨울 인턴십 풀이

코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십

 

크레인 인형뽑기 게임

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

코딩테스트 연습 - 크레인 인형뽑기 게임

 

시행착오

x

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Extra/Solutions/Programmers/%ED%81%AC%EB%A0%88%EC%9D%B8%20%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0%20%EA%B2%8C%EC%9E%84.cpp

insooneelife/AlgorithmTutorial

 

 

 

튜플

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

코딩테스트 연습 - 튜플

 

문제풀이

튜플 원소의 순서를 알기 위해서는 적은 원소를 갖는 집합부터 포함시키면 된다.

{{1,2,3},{2,1},{1,2,4,3},{2}}

다음과 같은 인풋이 들어오는 경우, 각 집합들을 개수 기준으로 정렬시킨다.

{{2},{2,1},{1,2,3},{1,2,4,3}}

그 후 적은 원소 집합부터 두 집합씩 선택하며 순회한다.

순회 과정에서 두번째 집합에서 첫번째 집합을 제거하면, 튜플의 원소를 순서대로 알아낼 수 있다.

(첫번째 원소도 이 과정에 자연스럽게 포함시키기 위해, 공집합을 이용할 수 있다.)

0 : {}, {2}                  -> {2}

1 : {2}, {2, 1}              -> {1}

2 : {2, 1}, {1, 2, 3}        -> {3}

3 : {1, 2, 3}, {1, 2, 4, 3}  -> {4}

순서대로 answer에 넣으면 된다.

 

 

시행착오

1. 문자열의 원소집합들이 개수 순서대로 정렬되어 있어야 현재집합 - 이전집합 연산이 가능하다.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/String/Solutions/Programmers/%ED%8A%9C%ED%94%8C.cpp

insooneelife/AlgorithmTutorial

 

 

 

불량 사용자

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

코딩테스트 연습 - 불량 사용자

 

문제풀이

완전탐색을 이용하여 해결 가능하다.

먼저 가능한 모든 경우의 수를 생각해보자.

응모자 아이디에서 불량 사용자에 대응시켜볼 후보군을 선택한다.

응모자 아이디 집합에서 불량 사용자 개수만큼 선택하는 모든 조합만큼의 경우가 존재한다.

A = { Combination(응모자 아이디, 불량 사용자 개수) }

 

어떤 선택된 응모자 아이디 조합에 대하여,

불량 사용자 집합의 모든 순서와 대응시켜본다.

이 때 한번이라도 모든 조합이 매칭이 되면 해당 조합은 정답 후보군이 된다. (answer ++)

모든 순서의 대한 경우의 수는 순열로 표현할 수 있다.

B = { Permutation(불량 사용자 개수) }

 

데카르트 곱으로 표현된 모든 경우의 수는 다음과 같다.

{ Combination(응모자 아이디, 불량 사용자 개수) } x { Permutation(불량 사용자 개수) }

 

 

시행착오

1. 순열로 만들어진 모든 순서들 중, 최소 하나의 순서는 모든 조합에 대해 만족해야한다.

 

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BruteForce/Solutions/Programmers/%EB%B6%88%EB%9F%89%20%EC%82%AC%EC%9A%A9%EC%9E%90.cpp

insooneelife/AlgorithmTutorial

 

 

호텔 방 배정

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

코딩테스트 연습 - 호텔 방 배정

 

분할정복을 이용한 방법

문제풀이

모든 방 요청에 대해,

요청된 방 번호와, 실제로 배정받은 방 번호를 매칭시켜 관리한다.

(요청된적이 없다면 해당 방 번호는 자료구조에서 찾을 수 없을 것이다.)

// 요청된 방 번호, 배정받은 방 번호
map<ll, ll> room;

 

어떤 방 번호에 대해 요청을 받으면, 실제로 배정된 방 번호를 반환하는 함수를 생각해보자.

방 번호에 request 대해 요청을 수행하는 경우,

해당 방이 배정된적이 없다면 바로 배정시킨다.

이 경우 요청된 방이 실제 배정된 방이므로 그 값을 그대로 반환한다.

if (room.find(request) == room.end())
        return room[request] = request; 

 

해당 방이 이미 배정되었다면 그 방을 요청한 사람이 최종적으로 배정받은 방을 찾고,

그 다음 방에 대해 다시 요청을 시도한다.

그리고 재귀적으로 요청하여 최종적으로 배정된 방을 다시 갱신한다.

(배정된적이 없다면 이전 코드에서 return되었을 것이므로, 이 지점에 온다는 것은 이미 배정된 경우만 가능하다.)

// 최종적으로 배정된 방을 찾고, 그 다음 방을 선택
ll next_req = room[request] + 1;

// 재귀적으로 다시 요청하고, 최종적으로 배정된 방을 갱신한다.
return room[request] = Find(room, next_req); 

 

 

시행착오

1. 너무 어렵게 접근함

2. 값 오버플로우

// 문제 있는 코드
int next_req = room[request] + 1;

// 통과된 코드
ll next_req = room[request] + 1;

 

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%ED%98%B8%ED%85%94%20%EB%B0%A9%20%EB%B0%B0%EC%A0%95.cpp

insooneelife/AlgorithmTutorial

 

 

Union-Find를 이용한 방법

문제풀이

방이 배정 요청이 다음과 같이 들어온다고 생각해보자.

1, 1, 1, 5, 5, 4, 7000, 7000, 5000, 5000

 

실제 배정되는 방은 다음과 같아야 할 것이다.

1, 2, 3, 5, 6, 4, 7000, 7001, 5000, 5001

 

위 인풋과 같이 1번 방에 대한 요청이 지속적으로 들어오게 되면, 1번 오른쪽으로 어떤 연결된 덩어리가 생기게 된다.

이 덩어리들을 하나의 집합으로 생각해보자.

또한 어떤 요청 하나하나가 다 원소가 하나인 집합이라고 생각해보자.

그렇다면 어떤 요청이 들어왔을 때 다음과 같이 상황을 나눌 수 있다.

 

해당 요청이 들어오지 않은 경우,

요청 방 번호를 하나의 집합으로 만들고, 방을 배정한다.

그리고 번호 - 1, 번호 + 1 위치의 방들이 배정되어 있다면, 해당 집합들과 합친다.

 

해당 요청이 이미 들어온 경우,

요청 번호에 위치한 집합에서 최종적으로 배정된 방 번호 + 1을 추천번호라고 부르자.

집합의 추천 번호를 가져와서,

추천 방 번호를 하나의 집합으로 만들고, 방을 배정한다.

그리고 번호 - 1, 번호 + 1 위치의 방들이 배정되어 있다면, 해당 집합들과 합친다.

 

집합을 찾고 합치는 연산을 수행하기 위해 Union-Find 자료구조를 이용한다.

그리고 이 경우, 집합의 key로 사용되는 값이 굉장히 커질수도 있는 값이기 때문에,

Union-Find의 parent를 비롯한 자료구조들을 배열이 아닌 map으로 대체하여 사용한다.

그리고 모든 가능한 key에 대해 미리 초기화를 할 수 없기 때문에,

사용될 방에 대해 그때그때 동적으로 초기화를 하도록 개조한다.

 

Union-Find에서는 다음과 같은 기능들을 지원해주어야 한다.

1. 어떤 방 번호에 대해 동적으로 초기화를 해주는 기능

2. 어떤 방 번호에 대해 그 방이 속한 집합을 찾고, 그 집합의 추천번호를 알아올 수 있는 기능

 

어떤 방 번호에 대한 집합의 추천번호는 다음과 같은 과정으로 구할 수 있다.

추천번호(recommend) = 최종적으로 배정된 방 번호(last) + 1

 

최종 갱신 방 번호는 다음과 같은 과정으로 갱신시킨다.

초기화 시, last = 요청된 방 번호로 세팅

합치기 시, 두 집합의 last 중 더 큰 값으로 양쪽 last를 갱신

 

 

시행착오

1. 호텔 방 번호가 Union-Find의 key가 되기 때문에, Union-Find의 parent와 같은 정보들을 map으로 저장해야 한다.

2. 방 번호와 같은 값이 key로 사용되는 상황에 Union-Find의 초기화를 미리 수행해둘 수 없기 때문에, 동적으로 초기화가 가능한 기능이 필요하다.

3. 값 오버플로우

// 문제 있는 코드
int recommend = uf.GetRecommend(room);

// 통과된 코드
ll recommend = uf.GetRecommend(room);

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/UnionFind/Solutions/Programmers/%ED%98%B8%ED%85%94%20%EB%B0%A9%20%EB%B0%B0%EC%A0%95.cpp

insooneelife/AlgorithmTutorial

 

 

징검다리 건너기

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

코딩테스트 연습 - 징검다리 건너기

 

이분탐색을 이용한 방법

문제풀이

어느 한명이 징검다리를 건널 때마다 모든 돌의 값이 1씩 낮아진다.

어느 N명이 징검다리를 건너면 모든 돌의 값은 N만큼 낮아질 것이다.

탐색 대상을 이 N의 값으로 바라보면, 이분탐색이 가능하다.

N값의 최소범위 0부터 N값의 최대범위 200000000에 대해 탐색을 수행한다.

 

다음과 같이 mid값을 구한다.

//100000000 = (0 + 200000000) / 2
mid = start + end / 2;  

해당 값에 대하여, 반복문을 돌며 stones[i] - mid <= 0 인 경우가 연속 k번 반복된다면 실패.

아닌 경우 성공.

실패인 경우 start, mid 구간에서 다시 수행한다.

성공인 경우 mid + 1, end 구간에서 다시 수행한다.

start와 end가 같아지는 순간의 그 값이 징검다리를 건널 수 있는 최대 사람 수가 된다.

 

 

시행착오

x

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial

 

Union-Find를 이용한 방법

문제풀이

한 명씩 건널 때마다 돌의 높이는 낮아진다.

계속 낮아지다 보면 높이가 낮은 돌부터 하나씩 0이 되게 된다.

그러므로 값이 낮은 돌부터 순서대로 0이 되게 될 것이다.

 

값이 낮은 돌부터 하나씩 방문한다고 가정해보자.

2, 4, 5, 3, 2, 1, 4, 2, 5, 1

이 값은 다음 순서로 방문될 것이다.

1, 1, 2, 2, 2, 3, 4, 4, 5, 5

 

방문된 돌의 위치는 물에 잠겼다는 표시를 해 둔다. (여기서는 cnts를 이용함)

여기서 물에 잠긴 돌을 하나의 집합으로 취급한다.

그리고 방문이 반복되며 어떤 돌이 물에 잠겼을 때, 이 돌 집합을 좌, 우 위치의 집합들과 합친다.

집합을 합치는 과정에서 현재 집합의 원소 개수를 갱신시켜준다.

이 과정을 수행하다가, 집합의 크기가 k보다 커지는 경우, 마지막 돌의 높이를 정답으로 저장한다.

 

 

시행착오

1. 인풋이 1개인 케이스

2. 카운트를 체크하고 laststone을 갱신하는 순간은 Union 이후에만 가능한것은 아니다. (AddCount 이후에도 가능)

 

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/UnionFind/Solutions/Programmers/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial