프로그래머스 코딩테스트 연습

LV1. 나머지가 1이 되는 수 찾기

짝수와 홀수

평균 구하기

x만큼 간격이 있는 n개의 숫자

자릿수 더하기

약수의 합

문자열을 정수로 바꾸기

자연수 뒤집어 배열로 만들기

문자열 내 p와 y의 개수

정수 제곱근 판별

정수 내림차순으로 배치하기

하샤드 수

두 정수 사이의 합

음양 더하기

서울에서 김서방 찾기

콜라츠 추측

없는 숫자 더하기

나누어 떨어지는 숫자 배열

핸드폰 번호 가리기

제일 작은 수 제거하기

내적

가운데 글자 가져오기

수박수박수박수박수박수?

약수의 개수와 덧셈

문자열 내림차순으로 배치하기

부족한 금액 계산하기

문자열 다루기 기본

행렬의 덧셈

직사각형 별찍기

최대공약수와 최소공배수

같은 숫자는 싫어

3진법 뒤집기

예산

이상한 문자 만들기

크기가 작은 부분문자열

최소직사각형

시저 암호

가장 가까운 같은 글자

푸드 파이트 대회

두 개 뽑아서 더하기

[1차] 비밀지도

콜라 문제

추억 점수

카드 뭉치

2016년

폰켓몬

모의고사

과일 장수

소수 만들기

소수 찾기

프로그래머스의 경우 자동완성이 지원되지 않는다. C++은 자동완성 없어도 어느정도 가능하지만 Java는 아직 부족하니까 좀더 연습해본다.이번 코드에서는 Vector와 함께 Collections.min() 메서드를 사용해 보았다.

프로그래머스 체육복 : Greedy algorithm

기사단원의 무기 : 약수 구하기

if 조건문을 너무 많이 넣어서 수행시간이 늘어진거 같은데...

오래 전에 풀이하다가 포기하고 다시 시도했는데, 그때는 문제 요구조건 그대로 완전탐색으로 시도했다. 요구조건을 조금 무시하더라도(예 : 최대 범위를 일부 넘기더라도) 풀이 알고리즘의 방향을 알면 빠르게 접근할 수 있다.

알고리즘 자체는 쉬운데, 최고 등수를 저장할 때 예외를 생각하지 못했다.처음 저장한 방식은 내가 1개를 맞추면 6등, 0개를 맞추면 7등으로 저장되게 잘못 작성했다.

StringBuilder와 String의 차이 확인Set 자료구조를 사용한 효율성 증가 / contains() 메서드 사용contains()와 indexOf()의 차이 확인

시간 효율이 내 풀이와 크게 차이가 난다.

실패율

공백 포함 문자열을 정수의 집합으로 파싱하는 법을 연습한다.sstream을 사용해 문자열을 파싱한다.

스택을 사용해서 햄버거가 지정된 순서대로 만들었는지 확인한다.지정된 순서가 맞다면 해당 햄버거를 pop하고, 다음 햄버거를 만들고, 아니라면 햄버거 확인을 위해 잠시 pop한 재료들을 다시 push한다.

정렬과 greedy 알고리즘을 사용했다.

permutation을 사용해 모든 순열을 구한 풀이도 존재하지만 완전탐색과 큰 차이가 없는것 같다.

코드가 너무 유치하다...

K번째 수

문자열 내 마음대로 정렬하기

[PCCE 기출문제] 9번 / 지폐 접기

JadenCase

좀 더 모듈화를 많이 해야 가독성이 더 좋아질 거 같다.

[1차] 다트 게임

올바른 괄호

귀찮은 이진법 변환을 쉽게 하는 라이브러리 함수를 배웠다.\`이때 비트수는 int의 경우 32비트지만 넉넉하게 64로 하는게 일반적이다.이진 변환 결과는 0000....101010 이런식으로 앞에 0이 붙는데 문자열이 아니고 bitset이라는 타입이다. 이를 to_st

DFS 알고리즘인데 시작점의 사방만 확인한다.문제를 대충읽고 전체 DFS 구현으로 작성해서 풀이에 실패했다.이전에 DFS를 풀이할때는 주로 재귀로 했는데 스택을 사용한 풀이가 큐를 사용한 BFS와 유사해서 개인적으로 더 편하다.

정답이긴 한데 일부 예시에서 너무 과도한 풀이시간이 발생했다. 예시 11~15번에서 다른 사람들의 10~40배 더 되는 시간이 걸렸다.반복문을 하나로 줄여 시간을 크게 줄일 수 있다.이때 최종 결과 확인 부분에서 answer에 =로 단순 재할당하는 것과 clear()로

어려운 문제는 아닌데 쓸데없이 출력문을 안 지워서 계속 시간초과가 발생했다.내일은 키패드 누르기 문제를 반드시 성공하겠다.

최단거리라길래 BFS로 박치기 했는데 그게 아니었다. 최단거리로 가능 경로를 구하는게 아니고 단순 맨해튼 거리(x와 y 길이 절댓값의 합)로 더 가까운 위치를 구하기만 하면 되는 것이다. 아직 level1이니 너무 복잡하게 생각할 필요 없다.

현대자동차 모빌리티 SW 개발자 데뷔과정 알고리즘 테스트 3번 문제와 유사한 문제다. 그때는 풀이에 실패했는데, compare 함수 방식과 람다 함수 방식으로 구현할 수 있다.람다 함수 작성법에 대해 정리한다.sort(벡터.begin(), 벡터.end(), \[&매개변

상 : height하 : 0좌 : width우 : 0처럼 각 인덱스의 최대 반대에 위치한 좌표로부터 갱신해서 답을 구한다. 이때, 오른쪽 아래 좌표인 rdx, rdy의 경우 인덱스 가장자리 값을 가져야 하므로 +1을 해 답을 구한다.

스택과 함께 배열의 수직 접근을 연습한다. level 1 완결까지 얼마 안 남았다.

피보나치 수

아니나 다를까 너무 정직한 풀이라서 시간이 오래 걸린다.다른 사람 풀이를 보니 bitCount()라는 메소드가 있다.Integer.bitCount(int x) : 입력된 32비트 정수의 1의 개수를 계산합니다.Long.bitCount(long x) : 입력된 64비트

스택을 사용해서 풀어봤는데 원래 이렇게 시간이 오래 걸리는게 맞는지 모르겠다.다른 사람들 풀이를 봐도 거의 동일한 알고리즘이라 비슷한 시간이 나올거 같다...

Map 자료구조에 대해 복습한다. C++에서의 map은 키값의 사전순으로 정렬이 되어 있던걸로 기억하는데 java는 그렇진 않은거 같다.

String 타입으로 대입을 하거나 += 연산을 수행하니 비효율성이 굉장히 높다.StringBuilder 타입으로 전환하니 시간이 크게 줄었다. 근데 다른 사람들 풀이를 보니 객체 메서드로 바꿔서 푸는게 더 멋있어 보인다.

카펫

구명보트

파싱이랑 맵, 리스트 자료구조를 원없이 썼다...

맵을 저장하는 과정까지는 맞았는데, 순서를 바꾸기 위해 탐색을 하는 과정을 너무 비효율적이게 작성했었다. 인덱스 값에 집중한다.

기하학에 배열, 반복문, 조건문, 파싱 등 모든 활용을 합친 거 같은 문제다.

int \[] DP = new intn + 1;로 하면 런타임 에러 발생 -> n이 1이면 DP는 크기 2인 배열이 만들어지는데, DP2 = 2; 문장을 수행할 수 없다.

점프와 순간 이동

2차원 배열을 반복 순회할때 인덱스를 활용하는 방법에 대해서 연습할 수 있다. 근데 문제를 너무 곧이곧대로 풀이해서 시간이 오래 걸린다. 창의적인 방법을 찾아야 한다.

N개의 정수의 최소공배수를 얻으려면 arr0과 arr1의 최소공배수를 구해 LCM을 얻고, 그 LCM과 arr2의 최소공배수를 구하고.... 해서 전체 정수의 최소공배수를 구해야 한다.

처음에는 map으로 저장하려 했는데 set을 사용하면 중복여부를 파악하기가 더 쉽다.

구현 자체는 쉬운 단순한 알고리즘이다. 대신 조건문이 많다.

돗자리를 둘 자리가 0일 수도 있다. 완전 탐색으로토 풀이할 수 있지만 for문이 5개 정도 만들어져서 시간 초과가 날 거 같아서 포기했다.

귤 고르기 DP 라고 생각했는데 그리디 알고리즘으로 훨씬 쉽게 풀이 할 수 있다.

예상 대진표

문자열 형태의 mm:ss를 계산하기 편하게 전부 int형의 초 단위로 바꾼 후 조건문을 통과시켰다.마지막 int형 결과를 다시 mm:ss로 변환하는 과정에서 두 가지 방법을 사용해 보았다.처음에는 기초적인 string 문법을 사용했고, 두번째는 전에 써본적 있는 str

대부분은 단순 vector로 구현했고, 또 while문 하나로 완성한 풀이도 있었다...문제를 좀 더 수학적으로 접근해서 짧고 최적화된 풀이를 하겠다.

연속 부분 수열 합의 개수

스택을 활용하는 올바른 괄호 찾기 문제이다.그런데 어제 프로그래머스에서 풀이한 연속 부분 수열 합의 개수 문제에서 처럼 회전하는 벡터를 활용하는 부분이 있다.https://velog.io/@magicdrill/%EC%97%B0%EC%86%8D-%EB%B6%80

할인 행사

사실 한번이라도 지각을 하면 break로 더 이상 계산을 안해도 될거 같다.

행렬의 곱셈

처음 시도에서는 이중 반복문으로 O(N^2)으로 수행시간 초과가 발생했다. 필요없는 반복순회도 있었고, 조건문도 포함되어 있었다.좀 더 수식으로 접근하면 불필요한 조건과 반복을 피할 수 있다.

문제 이해에 오래 걸렸고, 반복도 불필요하게 많이 들어갔을 수도 있다. 어쨌건, map과 vector을 활용한 정답 찾기 연습이 되었다.

숫자 야구 게임과 비슷한 방식이라고 생각한다.백준 2503 숫자야구 : https://velog.io/@magicdrill/%EB%B0%B1%EC%A4%80-2503-java-%EA%B5%AC%ED%98%84정수 5개의 조합을 구하고 이 조합이 질문과 답변 값

백준 9375 "패션왕 신해빈"과 동일한 문제이다. https://velog.io/@magicdrill/%EB%B0%B1%EC%A4%80-9375-java-Map처음에 map<string, vector<string>> assortment;의 자료구조

H-Index

기능개발

priortyqueu만 사용해서 해보려 했는데, priority queue는 값을 기준으로 자동 정렬을 해 주지만, 그로 인해 저장순서 또한 자동으로 정렬되어 문제를 풀이하기 위해 queue를 함께 사용한다.아니면 내가 못한 걸 수도 있고.

게임 맵 최단거리

피로도

스택을 사용해 DFS로 풀었다. 근데 이렇게 하면 어떤 방식으로 값이 나왔는지는 알 수가 없다. 도착했는지 여부만 확인할 수 있다.1번 방법을 최적화를 좀 하고, 경로를 확인 할 수 있도록 수정함

LRU 알고리즘을 구현하는 기회였는데 너무 주먹구구식으로 구현한거 같다.또 저장 방식을 pair<string, int> 로 해서 마지막으로 호출된 이후로 얼마나 시간이 지났는지 저장했는데, 다른 풀이를 보면 <string>만 저장해서도 풀이했다.위 코드의 경

문제를 이해하는데 너무 오랜 시간이 걸렸다.ssstream을 사용한 파싱법 말고 string을 사용한 좀 쉬운 파싱을 공부하고, compare()문, find()함수 등을 다시 복습했다.string과 isdigit()사용한 파싱find()함수 : \` \`\`\`fo

문자열 정렬은 사전순으로 정렬됨을 까먹고, compare 함수를 만들어서 길이순으로 정렬했다. 사실 사전순으로 정렬하면 길이 상관 없이 바로 다음 문자열이 현재 문자열을 접두어로 포함하는지 확인만 하면 되서 효율성을 올릴 수 있다.또한 첫 풀이에서 substr()를 사

map과 set 함수를 사용해 중복 요소를 처리하면서 두 자료구조의 차이를 비교한다.처음에는 두 개의 set을 사용했는데 이중for문때문에 시간 초과가 너무 크게 발생했다.

ArrayList, Map, Set 자료구조를 다양하게 사용한다.Character.isLetter(temp.charAt(i)) : 해당 문자가 알파벳인지 판단 해서 boolean 값으로 반환map1.getOrDefault(str, 0) : map에 str이라는 key값

이게 이렇게 오래 걸리면 안되는 문제인데...DFS로도 다시 도전해보겠다.

주식가격

처음 2차원 배열로 구현한 것은 방문을 체크하면, 도착점을 true로 바꾸니까 도착점이 같고, 경로가 다른 경우에도 방문한 것으로 확인하게 되는 문제가 있다.4차원 배열로 (cx, cy) <-> (nx, ny)의 배열 값을 true로 저장하면 빠르게 방문여부를 확

스택에 인덱스 값을 삽입하고 하나씩 뽑아 원래 배열의 요소 값을 찾아 비교하는 방식이 같은 레벨의 주식가격 문제와 유사하다.

문제는 HEAP으로 풀이하라 했는데, 우선순위 큐로 풀었다. -> 힙은 트리 기반의 완전 이진 트리를 이용한 우선순위 큐 구현에 사용된다.힙 HEAP힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간의 값의 관계를 이용하

처음에는 이런 식으로 for(k = 0; k < m && k != j; k++)라고 작성하면 k == j인 상황에서 continue로 패스할 거라고 생각했는데, 실행을 하고 보니 break로 동작했다.

택배상자

숫자 변환하기 왜 queue를 사용했는지? 왜 틀렸는지? 왜 DP를 사용했는지?

가장 처음에 나오는 수가 클 수록 모든 수를 문자열로 이어 붙였을 때 가장 커진다.예를 들어 9, 10, 3이 있으면, 9310이 가장 크다.두 문자열을 비교해서 앞자리 수가 동일한 경우, 미리 합쳐서 사전순으로 비교한다.예를 들어 3, 30을 비교할 때, 미리 두 경

타일 한 개의 길이는 2x1이다.그래서 n이 1일때, 타일을 놓는 방법은 1개이고, n이 2일때, 타일을 놓는 방법은 2개이다. 4개까지 직접 그려서 세어 보면, n이 3일때 3개, n이 4일때 5개이다. 규칙을 보면 DP4 = DP3 + DP2로 추정해 볼 수 있다.

오늘 풀이한 순열 생성 문제와 동일한 알고리즘으로 구현했다.https://velog.io/@magicdrill/%EB%B0%B1%EC%A4%80-16922-java-%EA%B5%AC%ED%98%84-DFS-%EC%9E%AC%EA%B7%80재귀를 싫어하긴 하지만

풀고 나니까 time을 1씩 더해서 증가하다 보니 시간 효율성이 떨어진다고 생각한다.1번 테스트케이스에서 결과가 8이 아니라 10이 나왔는데, 다리 위 트럭의 움직임을 잘못 이해했다. 다리 위 트럭은 나가고 들어오고가 동시에 진행된다. 그러므로 두 트럭 무게의 합이 다

큰 수 만들기 그리디 알고리즘

연속된 부분 수열의 합 투포인터란?

예시인 2554를 보면2554는 1의 자리가 4니까 2550으로 만들고 answer += 4 수행해 255로 마무리255는 1의 자리가 5인데, 10의 자리가 5 이상이니까, 255로 만들고 answer += (10 - 5) 수행해 26으로 마무리26은 1의 자리가 6

시소 짝꿍