기록공간

해결 방법 우선 record에 들어있는 문자열 형태의 원소를 행위, ID, 닉네임 이 세가지로 쪼개줘야 한다. 이때 sstream을 사용하면 편하게 쪼개줄 수 있다. 닉네임은 중복이 되어도 상관없고 ID를 기준으로 구분한다. 때문에 해쉬 테이블 특성을 이용하여 key값으로 id를 사용한다. 해쉬 테이블의 value값은 구조체로 string 타입의 닉네임과 들어왔는지 나갔는지를 검사하는 bool 타입 멤버변수를 가지고 있다. (나간 id는 닉네임 변경이 불가능하기 때문에 들어왔는지 나갔는지를 검사하는 bool값이 필요하다) 찾은 id값이 Enter하는 경우 해쉬 테이블의 특성을 이용하여 그 id를 key값으로 하는 value 구조체에 닉네임을 부여하고 들어왔다는 체크를 한다. 이제 최종적인 닉네임 변경 적..

문제 사각형의 넓이 N이 주어진다. 이 넓이를 만족하는 사각형의 가로, 세로 길이 A, B 길이에서 2 * (A + B)의 값을 perimeter라고 한다. 이 perimeter중 가장 최솟값을 반환하라. 만약 N이 30인 경우 이를 만족하는 사각형의 길이 A, B는 (1, 30), (2, 15), (3, 10), (5, 6)가 있다. 이 중 perimeter가 가장 작은 값음 (5, 6)으로 2 * (5 + 6) = 22이다. 해결 방법 1부터 N까지 N을 나눌때 나누어지는 경우는 넓이를 만족하는 A, B를 구해놓는다. 이 중 perimeter가 가장 최소인 값을 구하면 된다. 하지만 이렇게 하는 경우 O(N) 시간복잡도로 타임아웃이 될것이다. 그러면 제한시간을 만족하는 방법은 무엇이 있을까? 1 ~ ..

문제 정수 N이 주어진다. 이 N의 약수들의 갯수를 출력하라. N = 24인 경우 24의 약수는 1, 2, 3, 4, 6, 7, 12, 24 이므로 총 8개 이므로, 답은 8이다. 해결 방법 1부터 N까지 나눠지는 값은 약수이다. 이 방법으로 카운트를 세서 출력하면 정답이다. 하지만 이 방법은 시간 복잡도 O(N)으로 만약 N이 int의 최대값(약 21억)으로 주어진다면 시간초과가 난다. 여기서 약수의 갯수를 간단하게 구하는 중요한 사실이 있다. "만약 √(N)이 정수라면 √(N)은 N의 약수이며, 나머지 약수들은 √(N)를 기준으로 앞 뒤로 짝을 이루고 있다."는 것이다. 예를 들어 100의 약수의 갯수를 구한다고 해보자. 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100이다. ..

문제 비어있지 않은 배열 N개의 정수를 담는 A가 주어진다. 0

문제 N개의 정수를 담는 배열 A가 주어진다. 0

문제 N개의 숫자를 원소로 가지고 배열 A가 주어진다. 여기서 (X, Y, Z) 인덱스 위치가 주어진다. (0 1일 경우 max(0, M[1 - 1]) + max(0, N[1 + 1]) Y -> 2일 경우 max(0, M[2 - 1]) + max(0, N[2 + 1]) ... Y -> 6일 경우 max(0, M[6 - 1]) + max(0, N[6 + 1]) 이 값들중 가장 큰 값이 정답이 된다. 코드는 다음과 같다. for문을 중첩하여 사용하지 않았기 때문에 시간 복잡도는 O(N)이 된다. class Info{ int sum_from_front = 0; int sum_from_back = 0; } class MaxDoubleSliceSum { public int solution(int[] A) { if..

문제 N개의 숫자가 들어있는 배열 A가 주어진다. 우선 여기서 Leader 숫자를 먼저 찾는다. Leader 숫자가 되기 위해서는 두 가지 조건 중 하나가 필요하다. 배열에서 가장 많이 중복되는 값 배열 길이의 절반 값보다 더 많이 나오는 값 이제 A를 둘로 쪼갠다. (0 = limitEquiLeft) && (RightCount >= limitEquiRight)) { ++result; } } return result; } }

문제 정수값을 담는 N개의 배열 A가 주어진다. A에 존재하는 정수값이 중복으로 배열 사이즈의 절반 이상 존재하는 경우 그 정수값은 Dominator가 된다. 이 Dominator를 찾고, 이 Dominator 값인 인덱스 위치 중 하나를 출력하는 문제이다. 해결 방법 중복되는 값으로 몇 개가 존재하는지 효과적으로 알 수 있도록 해시 테이블을 사용한다. 해시의 Key값에는 인덱스에 존재하는 값이 들어가고, Value값은 그 값이 존재하는 인덱스들을 담는 Vector 컨테이너가 들어간다. 배열 A를 순회돌며 해시 테이블에 Key값과 Value값을 넣어준다. 그 작업이 끝나면 해시 테이블에 들어간 값(Iterator)를 순회돌며 배열 A 사이즈의 절반이 넘어가는 Dominator가 존재하는지 찾는다. 만약 ..