자바
-
프로그래머스 Lv.2) 올바른 괄호알고리즘/프로그래머스 2020. 5. 19. 23:06
올바른 괄호 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호� programmers.co.kr 풀이 괄호가 열리고 닫히는 것에 주목했다. 괄호가 여는 것 보다 닫히는게 더 많이 나온다면, 그 시점에서 불완전한 괄호가 된다. 이에 따라 스택개념으로 괄호의 갯수를 세주었다. 1. 괄호가 열리면 count를 세준다. 2. 괄호가 닫히면 count를 빼준다. 3. count의 수가 0보다 작은 수가 된다면 탐색을 마치면서 false를 저장한다. 코드 public class AlrightBracket_12909 {..
-
프로그래머스 Lv.2) 가장 큰 정사각형 찾기알고리즘/프로그래머스 2020. 5. 19. 23:01
가장 큰 정사각형 찾기 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 DP를 이용해 이 문제를 풀었다. Top-down을 이용해서 풀었고, board를 돌면서 어떠한 점이 1이라면 그 점을 기준으로 왼쪽, 왼쪽 상단, 상단 세 점의 최소값을 찾아 1을 더해줬다. 이후에 max값을 갱신했고, 탐색이 끝난 후에는 max값의 제곱을 리턴해주었다. 1. board의 모든 점을 탐색한다. 2. board가 1이라면 해당 점을 기준으로 좌측, 좌측 상단, 상단 세 점의 최소값을 찾는다. 2.1 최소값에 +1을 해주어 해당 점에서 만들 수 있는 정사각형의 최대 크기를 저장해주었다. 3. 2번이 끝난 후 m..
-
프로그래머스 Lv.2) 단체사진 찍기알고리즘/프로그래머스 카카오 2020. 5. 19. 22:51
단체사진 찍기 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 � programmers.co.kr 풀이 우여곡절이 많았던 문제다. 시간초과가 뜰까봐 문제를 보자마자 생각난 완전탐색을 미뤄두고 여러가지 시도를 했다. 하지만, 이마저도 다 시간초과가 떠서 어떻게 풀라는 건지 막막했다. 문제를 푼 지 오랜시간이 지나고 도저히 모르겠어서 검색을 했다. 맨 위에 나온 블로그를 켜자마자 첫 줄에 완전탐색으로 풀었다는 글을 보자마자 블로그를 껐다. 그리고 한숨을 쉬었다.. 완탐이 되는 문제라니.. 수학적 공식을 활용하려고 발버둥 쳤던 내 자신을 반성..
-
프로그래머스 Lv.2) 땅따먹기알고리즘/프로그래머스 2020. 5. 19. 22:40
땅따먹기 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 풀이 나를 좌절하게 만든 문제였다... 분명 DP를 활용하는 문제임을 눈치챘고 유사한 문제도 풀어냈었는데, 검색과 자동완성 기능 없이 풀어야한다는 생각이 들어서 그랬을까 못풀었다. 그래서 프로그래머스에서 제공하는 문제의 해답 영상을 봤다. 마지막 행의 4개의 x에 대해 bottom-up 방식으로 dp를 진행하는 것이었다.. 분명 이렇게 풀었던 dp문제가 있었던게 기억났다. 생각보다 간단했다.. 로직 1. 행의 길이와 x의 개수(4..
-
프로그래머스 Lv.2) 다음 큰 숫자알고리즘/프로그래머스 2020. 5. 19. 22:30
다음 큰 숫자 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 풀이 Lv2 문제를 풀고 있는 이유는 내 생각보다 생각을 많이 해야하는 문제가 존재하고, 기본을 다시 한 번 되돌아보기 좋기 때문이다. 또한, IDE를 사용하지 않고 문제를 푸는 연습을 하고있어서, 코드가 많이 길어지지 않는 문제들로 먼저 연습하고 있기 때문이다. 아무튼 이 문제를 처음 마주했을 때는 '이건 검색을 해야 알 수 있는 문제다' 였다. 물론 코드를 검색하고 이런 것이 아니라 JAVA에서 숫자를 2진수로 ..
-
프로그래머스 Lv.2) 튜플알고리즘/프로그래머스 카카오 2020. 5. 19. 22:21
튜플 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 풀이 답의 규칙을 찾은 결과 가장 작은 크기의 부분 수열이 가진 원소의 순서대로 답의 순서가 정해진다는 것이었다. "{{1,2,3},{2,1},{1,2,4,3},{2}}" 위의 예제로 설명하면, 가장 작은 크기의 부분수열 {2}로부터 2가 정답의 맨 첫번째임을 알 수 있고, 그다음 {2,1}을 통해 2->1, {1,2,3}을 통해 2->1->3, {1,2,4,3}을 통해 2->1->3->4가 되는 것이다...
-
프로그래머스 Lv.2) 124 나라의 숫자알고리즘/프로그래머스 2020. 5. 16. 17:30
124 나라의 숫자 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 풀이 이 문제도 고민의 시간이 길었다. 문제 자체는 이해하기 쉬웠다. 모든 10진법 숫자는 1,2,4 세 개를 통해 표현해야하는 문제이고 3진법과 비슷한 느낌이라고 생각했다. 다만 다른 점?은 세가지 숫자만 이용하는데 1,2,3이 아닌 1,2,4라는 것이다.. ㅎㅎ 조금 특이하게 이 문제는 로직 자체는 쉽게 떠올랐으나, 구현이 오래걸렸다. (멀쩡한 사각형과 이 문제는 어제 푼 문젠데, 어제 컨디션이 별로였..
-
프로그래머스 Lv.2) 멀쩡한 사각형알고리즘/프로그래머스 2020. 5. 16. 17:06
멀쩡한 사각형 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 �� programmers.co.kr 풀이 평소에 레벨 3,4 혹은 카카오 문제를 풀어왔기에 레벨 2는 쉽다고 생각하며 접근했다가 큰코다쳤다. 너무너무 어려웠고 푸는데 오랜 시간이 걸렸다. 먼저, 처음에 생각했던 로직은 직선이 타일과 정수 좌표에서 만나는 구간을 구해 반복되는 만큼 수를 빼주는 것이었다. 그래서 Linear Equation(1차 방정식)을 세우고 해당 직선과의 거리를 구하면서 진행했다. 정수인 x,y 점을 돌면서 루트 2(sqrt 2)보..