2020 카카오 인턴 기출 풀이

오늘 다 풀어볼줄 알았는데 5문제중에 3문제만 풀었네요 내일 마저 풀겠습니다.

 

1. 키패드 누르기

키패드를 좌표 평면으로 생각해보면 쉽게 해결 할 수 있습니다.

다만 왼손, 오른손, 눌러야할 버튼 이 3가지를 좌표 평면에 옮겨야해서 별것도 없는 문제인데 길이가 90줄 가까이 됩니다.

구현의 팁은 거리를 구할때 굳이 루트 연산을 하지 않는 부분입니다.

 

2. 수식 최대화

제가 취약한 문제 유형(구현, 문자열) 중 하나입니다.

문자열 문제라 바로 파이썬으로 바꿔 풀었습니다.

문제에서 친절하게도 경우의 수가 3!뿐이라고 알려줍니다.

6가지 각각의 경우에 대해서 계산을 해주면 됩니다.

 

다만 내용에 비해 역시 구현해야할 코드가 많습니다. 나름 줄인건데 70줄이네요

계산하는 부분을 따로 함수로 작성하고 6가지 경우에대해 함수를 한번씩 호출하면 그나마 구현을 줄일 수 있습니다.

저는 파이썬 초보라 메소드 사용하는데 좀 많이 삽질했습니다.

 

3. 보석 쇼핑

투포인터 문제입니다.

무슨 의도인지는 모르겠지만 입력이 일반적이지 않게 주어집니다.

보통 이런문제들은 보석의 종류를 그냥 1번 2번 이런식으로 주는데, 진짜 문자로 다이아, 루비 이렇게 보석을 줍니다.

따라서 문제 풀이와 상관없이 map을 이용해서 보석의 종류를 숫자로 표현해주는 과정이 한번 필요합니다.

 

이제 end를 하나씩 증가시키면서, 이때 가능한 start의 시작점으로부터 가장 먼 위치를 찾아주면 됩니다.

start의 가능한 가장 먼 위치 : start~end 구간에서 모든 보석을 적어도 하나 포함 시키는 위치

이렇게 반복문을 돌면서 구한 구간이 정말 모든 보석을 적어도 하나 포함시키는지 확인하고 가장 짧은 구간을 찾아주면 됩니다.

 

구간에 보석이 포함되는지에 대한 구현이 $O(N)$으로도 가능하지만, 효율성에서 TLE를 받습니다.

cnt 변수를 하나 잡아서 새로운 보석이 들어올때마다 증가시키고, 이 값이 보석의 갯수와 같은지 확인하는 방법으로 상수 시간안에 확인 가능합니다.

40줄이 안되는 길이로 구현 가능합니다.

 

추가예정 

 

4. 

 

5.