Algorithm
Coding Test Meeting #3
이번에 다룬 문제는 다음과 같다. 2023.03.07 - [Algorithm/LeetCode] - 12. Integer to Roman 2023.03.07 - [Algorithm/LeetCode] - 2319. Check if Matrix Is X-Matrix Integer to Roman 숫자가 주어지면 로마자로 변경하는 문제 -> Place Value / Face Value -> 작은 수 부터 if else -> switch case -> 최적화 여부로 binary add의 성능이 달라지는 말씀을 하심 Check if Matrix Is X-Matrix 정사각형이 x자로 숫자가 채워져있는지 여부 확인하는 문제 -> 쿼드 트리 압축 -> DP 정사각형을 다시 4등분하여 쪼개서 계산하는 방법 시간 복잡도 ..
2319. Check if Matrix Is X-Matrix
문제파악 및 재정의 X-Matrix 조건을 만족하면 True 아니면 False를 반환하라. 다음 조건이 모두 충족되는 경우 정사각형 행렬을 X-행렬이라고 합니다. 행렬의 대각선에 있는 모든 요소는 0이 아닙니다. 다른 모든 요소는 0입니다. 정사각형 행렬을 나타내는 n x n 크기의 2D 정수 배열 그리드가 주어지면 그리드가 X-매트릭스이면 true를 반환합니다. 그렇지 않으면 false를 반환합니다. 자료구조 및 알고리즘 선택 i j i j i j i j [0][0] 2 | [1][0] 0 | [2][0] 0 | [3][0] 4 [0][1] 0 | [1][1] 3 | [2][1] 5 | [3][1] 0 [0][2] 0 | [1][2] 1 | [2][2] 2 | [3][2] 0 [0][3] 1 | [1]..
12. Integer to Roman
문제 파악 및 재정의 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 로마 숫자를 정수로 변환시켜라 예를 들어, 2는 로마 숫자에서 II로 표기되며, 단지 두 개의 1을 더한 것입니다. 12는 XII로 표기되며, 간단히 X + II입니다. 숫자 27은 XXVII로 표기되며, 이는 XX + V + II입니다. 로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 큰 순서로 씁니다. 그러나 4의 숫자는 IIII가 아닙니다. 대신 숫자 4는 IV로 씁니다. 1이 5보다 앞에 있기 때문에 빼면 4가 됩니다. 같은 원리가 IX로 쓰여진 숫자 9에도 적용됩니다. 빼기가 사용되는 경우는 6가지입니다. V(5)와 X(10) 앞에 I를 배치하여 4와 9를 만들 수 있습니다. X는 L(50)과 C(100) 앞에 배..
278. First Bad Version
문제 파악 및 재정의 n개의 버전이 주어지고 isBadVersion API가 제공된다. 첫 번째 불량 버전을 찾는 기능을 구현하며, API의 사용 횟수를 최소화 하라. 자료구조 및 알고리즘 선택 BinarySearch -> start와 end를 옮겨가며 mid의 위치를 조정하여 찾는 방식 구현 public class Solution extends VersionControl { public int firstBadVersion(int n) { int answer = 0; int start = 0; int mid = n/2; int end = n; if(n == 1) return 1; // 탈출 조건 while(true) { if(end == start) { answer = start; break; } if(..
푸드 파이트 대회
문제 파악 및 재정의 푸파 -> 1 : 1 -> 음식 종류와 양이 바뀜 | -> [물] 0) { String tempIdx = idx+""; stringBuilder.append(tempIdx.repeat(food[idx])); } } temp = stringBuilder.toString(); reverse = stringBuilder.reverse().toString(); answer = temp + "0" + reverse; return answer; } } 회고 class Solution { public String solution(int[] food) { String answer = "0"; for (int i = food.length - 1; i > 0; i--) { for (int j = 0;..
가장 가까운 같은 글자
문제 파악 및 재정의 문자열 s가 주어졌을때 s의 각 위치마다 자신보다 앞에 나왔으며, 자신과 가장 가까운 곳에 있는 같은 글자의 위치를 int[]로 반환하라. 자료구조 및 알고리즘 선택 Counter Sorting(계수정렬) 문자열의 길이만큼의 정수형 배열과 알파벳에 해당하는 정수 배열을 선언 알파벳에 미리 -1값을 채워두고 주어진 문자열을 순회 아스키코드를 활용하여 해당 순번이 초기값인지 아닌지를 판별 후 반환할 배열에 대입 대입후 index를 넣어둠 구현 import java.util.Arrays; class Solution { public static int[] solution(String s) { int[] location = new int[s.length()]; int[] alpha = new..