본문 바로가기

알고리즘/프로그래머스

 (8)
프로그래머스 - 인사고과 값을 여러 쌍을 준 뒤, 특정한 인덱스가 몇 번째로 위치하는지에 대한 문제를 프로그래머스에서 몇 번 본듯한 기억이 있었다. 지금 정리해두면 나중에 유용하다 생각해 글을 쓰게 됐다. 완전 탐색 1. 태도, 동료 점수 모두 자신보다 큰 사원이 있을 경우 해당 사원을 제외한다. 2. 각 사원들의 점수 총합을 구한 뒤, 점수를 기준으로 내림차순 정렬을 해 원호가 몇 번째로 큰지 본다. 만약, 원호가 제외됐을 경우 -1을 반환한다. 시간복잡도 계산 1번의 경우 모든 사원을 봐야 하기 때문에 N^2의 시간 복잡도 발생 2번의 경우 정렬에 Nlog(N), 원호의 위치를 찾는 과정에서 N의 시간 복잡도 발생 총 시간 복잡도는 N^2 + Nlog(N) + N으로, N = 100,000이기에 시간 초과가 발생한다. 틀린 ..
프로그래머스 - [1차] 뉴스 클러스터링 들어가기 전에 문제를 해결하기 위해 어떤 생각을 했는지 기록하기 위해 쓰는 글입니다. O(10^8)의 계산을 1초라 가정했습니다. 잘못되거나 개선이 필요한 부분 지적은 언제나 환영입니다! 지문 해석 두 문자열 str1, str2을 upper나 lower를 통해 대문자나 소문자로 변환해야 한다 변환된 문자를 슬라이딩 윈도우를 통해 특수문자가 있는지 확인하고, 없다면 배열에 추가한다. 각각 시간 복잡도가 O(n)이 나온다. 그 후, 슬라이딩 윈도우의 결과를 가지고 교집합과 합집합을 구한다. 여기서 주의할 점은 교집합을 구하는 과정에서 교집합이 된 쌍은 다음 교집합 확인에서 제외해야 한다. 예를 들자면 A = {1, 1, 2, 2, 3}, B = {1, 2, 2, 4, 5} 의 교집합에서 A[0] = 1과 B..
카카오 코테 - 문자열 압축 문자열 길이로 판별하는 방식으로 풀었다. 정답 코드 더보기 def solution(s): half = len(s) // 2 answer = 1e9 if(len(s) == 1): answer = 1 for i in range(1, half + 1): base = s[0:i] count = 1 temp = 0 for j in range(i, len(s), i): current = s[j:j+i] if base == current: count += 1 else: temp += len(base) if count > 1: temp += len(str(count)) base = current count = 1 temp += len(base) if count > 1: temp += len(str(count)) ans..
프로그래머스 - 쿼드압축 후 개수 세기 분할 정복 문제 1. 정사각형을 같은 크기로 4등분(길이 / 2) 2. 루프를 4번 돌려서 4등분한 길이만큼 정사각형 분할 3. 1~2 의 작업을 길이가 1이될 떄 까지 반복 4. 길이가 1일 때 현재의 원소 반환 5. 이렇게 분할된 값들을 모아서, 0과 1이 각각 몇 번 나왔는지 셈 6. 루프를 통해 0이나 1이 4번 나오면 적절히 처리해줌 7. 6번에서 0이 4번 나오면 0반환, 1이면 1 반환, 아니라면 2 반환 8. 5~7 반복 코드 더보기 class Solution { int[] answer = new int[2]; public int[] solution(int[][] arr) { int ret; ret = divide(arr, arr.length, 0 ,0); // 모든 원소가 0이나 1인 경..
프로그래머스 - n^2 배열 자르기 예시 1번은 좌표료 표현하면 다음과 같이 표현할 수 있다. 여기서 규칙을 찾을 수 있다. 행과 열의 값중 최대 값 + 1이 해당 칸에 있는 수이다. 예를 들자면 (1, 2)에서 가장 큰 값은 2이고, 여기에 1을 더하면 3 그렇다면 공식을 다음과 같이 세울 수 있다. a = 행 / n b = 열 % n a, b 중 최대값 + 1 코드 더보기 더보기 class Solution { public int[] solution(int n, long left, long right) { int[] answer = new int[(int)(right - left + 1)]; int division = 0, remain = 0; int answerIndex = 0; while(left
프로그래머스 - 전력망을 둘로 나누기 dfs를 사용해 풀었다. 1. 1번 노드부터 dfs 실행. 방문한 노드는 다시 탐색하지 않는다. 2. 각 노드는 연결된 노드 중 방문하지 않은 노드들에 dfs 실행 3. 연결된 노드들에 대해 dfs가 끝난 노드는 자신을 포함해 dfs를 보낸 노드 수를 더한 값을 반환 ex) 예시 1번 기준 7번 노드에선 8, 9번 노드에 dfs를 실행하고 8, 9번은 각각 1을 반환 7번 노드에 대한 탐색이 끝났으면, 자기 자신을 포함해 3 반환. 4. 3번에서 반환된 값은 | (n - 반환 값) - 반환 값| 연산을 해 현재 답과 비교해 작은 것을 저장 5. 모든 노드의 탐색이 끝날 때 까지 2~4번 반복 이 결과가 끝날 때의 각 노드의 값들은 다음과 같다. (예시 1번 기준) 코드 더보기 더보기 import java..
프로그래머스 - 이진 변환 반복하기 평범한 level 2문제 replaceAll이 생각보다 빠르지 않단 것을 알았다. 풀이 순서는 다음과 같다. 1. 문자열 s에서 0의 개수를 센다. 2. 문자열 s의 길이 - 0의 개수를 이진변환 한다. 3. 1이 되면 1,2번을 반복한 횟수와 그 떄 까지 센 0의 개수를 반환 내 풀이와 결과 더보기 더보기 class Solution { public int[] solution(String s) { // 이진 변환 횟수, 제거된 모든 0 int[] answer = new int[2]; int zeroCount = 0; int round = 0; while(true) { answer[0]++; zeroCount = 0; for(int i = 0; i < s.length(); i++) { if(s.charAt..
프로그래머스 - 빛의 경로 사이클 30분 내로 풀 거를 이해 잘못해서 3시간 가량 소비한 문제 `_' 단편적인 것만 보고 거기에 맞추느라 고생했다. https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 문제에 중요한 힌트가 하나 있는데 한 격자에서 들어오고 나가는 방향은 언제나 똑같음. 이게 무슨 말이냐면 시작을 왼쪽위에서 아래서부터 하든, 오른쪽 아래에서 위에서부터 하든 도달하는 순서만 다를 뿐이지, 반드시 해당 방향..

티스토리툴바