본문 바로가기

코딩테스트 풀이 정리

 (10)
[코딩 테스트] 코테후기 총 5문제가 나왔고, 3번문제가 무언가 이상해서 시간이 끌렸다. 4,5 번을 못풀었는데 4번은 시간이 종료 됬고, 결국에는 나중에 시간을 들여서 풀이했다. 문제는 1, 3, 7, 26, 94, 259 그램의 무게추가 있을 때 인풋으로 290같은 숫자가 주어질때 0을 기준으로 무게가 같게하는 리스트배열을 출력하는 문제이다. 풀이 코드는 아래와 같다. 짧게 설명하면 left, right로 나누고 left에 인풋으로 주어지는 target 값을 집어 넣고 시작한다. 무게추를 큰그램부터 순회하면서 현재무게추값 + 오른쪽 과 왼쪽무게들의 합을 비교 왼쪽이 더크다면 오른쪽에 무게를 추가한다 반대의 상황이라면 왼쪽에 추가한다. 단, 왼쪽에 추가할때 왼쪽의 합이 나머지 남은 무게추들의 합 + 오른쪽의 전체 합보다 크면 ..
위메이드 코테 후기 잘하지도 못하는 재귀 구현이 필요한 문제에 시간 투자하느라 정작 풀 수 있었던 3번 문제를 풀지 못함.. n x n 크기 좌석을 첫 손님이 0,0 부터 앉고나서 k번째까지 각 앉아 있는 손님의 좌표들이 최대가 되는 거리가 되도록 앉을 때 k번째 앉는 좌표를 구하는 문제였슴... 지금은 풀었는데 불과 30분전에는 풀지못함.. ㅅㅂ... 아까워서 여기라도 올림.. import copy def kprint(arr): for a in arr: print(a) def caculdis(coordis, n): newcoordis = copy.deepcopy(coordis) arr = [[(n * n) + 1] * n for _ in range(n)] for coord in newcoordis: x, y = coord..
티맥스 코테 후기 - 3번 티맥스 2, 3번을 제대로 못풀었습니다. 안풀릴 2번에 시간을 쏟아서 괜히 3번을 못풀었네요. 3번은 시간이 종료되고 결국 풀었습니다만 같은 문제를 후기에 올리면 안되니 나름 문제를 변형해서 올립니다!! 배열이 주어집니다. 이때 0은 빌런 1은 히어로 입니다. 정의는 항상 승리하므로 히어로는 항상 이깁니다. 이럴때 현재 값의 배수 크기로 토너먼트가 배열이 주어지는 것 인데. [0, 1, 0, 1] 이렇게 주어지면 총 3번의 토너먼트가 일어납니다. 그리고 사람들은 히어로를 좋아하므로 히어로의 대전을 카운팅하려고 합니다. 주어진 배열은 히어로 대전이 3번 일어납니다. 이런 상황일때 [0, 0, 1, 0] 배열이 이렇게 주어진다면 빌런 선수를 히어로 선수로 한 번 바꿀 수 있습니다. 한 번 바꿀 수 있다고 했..
22년도 네이버 코테 후기 3번 문제가 데이터 길이 100만인걸 봐서 최적화를 어떻게 해야 하지 하다가... O(n^2)되는 문제 풀이도 제출을 못했다. 문제를 다시 생각해보니 연속전인 부분만 구하는거 같은데 실마리를 찾았다 생각해서 급하게 풀어버렸다... 물론 지금도 O(n^2)이상의 최적화 풀이는 떠오르지가 않는다. 다만, 풀긴 풀었으니까 올려보고자 한다. * 문제를 제대로 이해하지 못한 상태로 문제를 푼 코드 def solution(a, k): # write your code in Python 3.6 a.sort() left = 0 right = len(a) - 1 while True: chk = a[right] - a[left] realBreak = False if chk > k: l = a[left + 1] - a[lef..
코딩 테스트_3. 해당 단어를 원하는 단어로 변환 ( 문제 ) 입력 1. "this is {template} {template} is {state}" 입력 2. [["template", "string"], ["state", "changed"]] 입력 2에 따라 입력 1의 문자열을 template -> string, state -> changed로 바꿔서 리턴해주면 됩니다. 결과 "this is string string is changed" 여기서 해당 배열 찾아서 바꿔주면 되겠네 할 수 있습니다. 문제는..! [["template", "string"], ["state", "changed"], ["changed", "template"]] 입력 2로 이와 같은 상황이 주어질 때입니다. 유니온-파인드 알고리즘을 이용하면 비교적 쉽게 해결할 수 있습니다. 유니..
코딩 테스트_2. 가장 많이 반복되는 문자열들 제거 ( 문제 ) ex1) abcabcdefabc 위와 같은 문제가 주어질 때, abc라는 문자열이 3번 반복된다 물론 a도 3번 ab도 3번 기타 다른 집한구들도 반복된다 하지만, 가장 긴 문자열을 가지고 가장 많이 반복되는 문자열은 abc이다. 이럴 때 abc를 삭제하고 남은 문자열을 리턴한다. 결과: def ex2) "abxdeydeabz" 위와 같은 문자열이 주어질 경우, ex1의 경우로 유추해서 추려내면 ab 2번, de 2번이 나옵니다. 이렇게 조건에 의해 동률일 경우는 둘다 삭제합니다. 결과: xyz ( 문제 해설 ) (목표) 문자열 길이가 1~ 전체길이 // 2까지 획수를 구해야 합니다. 1. for문을 돌면서 문자열 길이에 따라 처음 나올 경우 해당 문자열을 키로 가지는 value를 1로 설정..
코딩 테스트_1. 방향전환 ( 문제 ) 다음과 같이 "EEESEEEEEENNNN" 방향이 주어집니다. ( E: 동 N: 북, S: 남, W: 서 ) 방향 하나당 100M이며 1의 시간이 걸립니다. 해당 예시로 들면 E방향으로 300M 후에 S로 움직이니 오른쪽으로 움직이는 겁니다 다시 한 번 E로 움직이니 왼쪽으로 움직이는 거지요. 그리고 6번 움직이는데,, 5번 이상 같은 방향으로 움직여야 된다고 판단될 시 100M씩은 내비게이션은 지시를 안 해도 됩니다 ( 문제 풀 때 이부분을 못 봐서 문제를 제대로 못 품 ) 그렇기 500M 움직인 이후에 다시 N방향으로 가니까 왼쪽으로 움직이게 되는 거죠. 결론적으로 출력 결과는 'Time 0:Go straight 300m and turn right', 'Time 3:Go straight ..
SKT_ICT_코딩테스트 #4. 대체 문제 백준_20188_등산마니아 ( 문제 ) 등산 마니아 서브 태스크 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 745 287 228 42.617% 문제 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오두막에서도 다른 모든 오두막으로 하나 이상의 오솔길을 따라 이동하는 것이 가능하다. 오두막들은 1번부터 N번까지 번호가 붙어 있으며, 1번 오두막이 산 정상에 있다. 1번 오두막에서 다른 오두막으로 가는 가장 짧은 길을 따라가면서 거치는 모든 오솔길들은 항상 산을 내려가는 방향이다. 철수는 등산 마니아이다. 철수가 한 오두막에서 다른 오두막으로 갈 때는 항상 산 정상을 거..
728x90

티스토리툴바