자바

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131127# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 map 자료구조를 활용하여 쉽게 풀 수 있었다. 우선 내가 원하는 값들을 [제품, 개수] 형식으로 초기화 해준다. 다음에는 할인 현황을 담을 map 을 계속 갱신해준다. 하루가 지남에 따라 가장 앞의 값을 제거해주고, 새로운 제품을 추가해준다. 그리고 할인중인 목록에 내 제품이 있으면서, 개수도 다 만족한다면 정답에 값을 추가해주면 된다. (단, 할인 현황 map에 개수가 10개가 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제의 핵심은, 수열합을 구할때 이미 구한 부분을 어떻게 다시 계산하지 않고 구할 수 있느냐이다. (만약 수열때마다 모든 합을 구하면 1000 (원소의 개수) * 1000 (수열의 최대 길이) * 1000 (수열합 구하기) 의 시간 복잡도가 나오게 될 것이다..) [1, 2, 3, 4] 배열이 있을때 수열 2인 값을 구할때 [1, 2] 의 합을 구하게 될 것이다. 그리고 수열3인 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 dp로 풀이했다. 1칸 또는 2칸만 움직일 수 있다는걸 반대로 생각하면 -> 내가 있는 현재 위치 - 1 에서 오는 방법, 내가 있는 현재 위치 -2 에서 오는 방법 두가지가 있다. 따라서 점화식은 d[i] = d[i-1] + d[i-2] 로 정의할 수 있다. 그리고 값 오버 플로우를 대비해서 dp 배열에 저장할때부터 % 연산하는걸 주의해야 한다. 마지막에 return할때 처리할려면 이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 나무위키로 최소 공배수의 특징을 확인하였다. 세개 이상의 수의 최소 공배수를 구하기 위해서는, 두 수의 최소공배수와 새로운 수의 최소 공배수를 구하면 된다. 두 수의 최소 공배수 같은 경우에는 최대 공약수(gcd)를 통해서 구할 수 있는데, 최대공약수는 유명한 "유클리드 호제법" 으로 구할 수 있다. 따라서, 두 수의 최대 공약수를 구한 후에 이 값을 활용하여 최대 공배수를 구하는 과정..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 사실 이 문제는 하라는대로 구현만 하면 슉슉 풀리는 문제이다. 단 지문이.. 이해하기 조금 난해하다는게 문제다. 슈도 코드를 작성하면 조금 더 쉽지 않을까 생각한다. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수..

기존 프로젝트를 리팩토링 하다가 제네릭 문법을 만났다. 어떤 의미로 사용하는지는 알지만, 제대로 알고 사용한게 아니라서 다시 보는데도 너무 헷갈렸다. 생각해보니 제네릭을 책으로 제대로 공부한 적이 없어서.. 책장에 있는 책을 참고해서 제네릭 클래스와 메소드 정도를 가볍게 정리해보려 한다. 제네릭의 의미와 필요성 제네릭의 뜻은 '일반화' 이다. 그리고 자바에서 말하는 일반화의 대상은 자료형을 의미한다. 간단히 말하면 특정 클래스나 메소드를 사용하는데에 있어서 자료형의 구속에서 벗어날 수 있는 것이다. 자바는 객체지향 언어이니 클래스를 기준으로 설명해보겠다. 클래스가 총3개가 있다고 해보자, '사과' , '오렌지' , '박스' 이다. 이 때 현실적으로 박스에는 사과나 오렌지, 어떤게 들어가도 큰 상관이 없어..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에는 기준이 되는 수에서 +1, +2를 한 값과 xor를 하고, 1의 개수를 세는 방식으로 접근했다. 그러나 이 방법은 시간복잡도 면에서 통과할수가 없었다. 1의 개수를 세기위해 비트를 모두 체크해야하는데 범위가 너무 컸을뿐더러, +1 , +2 씩 하면 언제 비트가 2개 이하로 다른 숫자가 나올지도 모르기 때문이다. 한참을 고민해봤으나 이 접근방법은 틀렸다고만 생각이 들었지 뾰족한 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12980 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 처음봤을땐 DP인가 싶었다, 그러나 10억개의 배열을 선언하면 메모리가 터져버린다. 또 다르게는 1칸을 가거나 2배를 가거나 하는 완전탐색을 생각했는데 이건 시간초과를 벗어날 수 없었다. 곰곰히 생각해보다가 n에서부터 0을 찾아가면 쉽겠다고 생각이 들었다. 무조건 2배를 해주는게 좋으니 나눌수 있을땐 나누고, 그게 아니라면 -1을 해주고 카운트를 1늘려주면 된다. 이 과정을 n이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 정확성만 본다면 단순히 브루트포스로 풀 수 있는 문제이나, 시간을 따졌을때 그렇게 풀 수 없는 문제이다. 이 문제의 핵심은 '누적합' 인데, 나도 전혀 감을 못잡아서 풀이를 보고 알게 되었다. 개인적으로는 이런 문제를 접해보지 않고, 관련 테크닉을 모른다면 못푸는 문제가 아닐까 생각했다. (구현보다는 스킬, 테크닉 의존적인 문제 아닐까..) 이 누적합 테크닉은 1차원 배열을 먼저 예시로..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1835 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 어떻게 풀면 좋을까 생각하다 완탐 (순열) 밖에 없는거 같아서 그렇게 풀었다. 우선 8명이 설 수 있는 모든 경우를 모두 구한다. 파이썬은 itertools 로 순열을 굉장히 쉽게 구할 수 있는 반면, 자바는 없다고 하더라. 그래서 perm이라는 순열을 만드는 함수를 만들었고 특정 순열이 한개 만들어지면 (8명이 모두 자리를 잡고 서있다면) 조건에 부합하는지 검사하도록 했다. 해당 배치가..