레벨업 일지

문제 https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Number of Islands - Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may ass leetcode.com 주어진 2차원 배열에서 '1' 부분의 집합들의 개수를 리턴하는 문제 알아야 할 개념 ..

문제 https://leetcode.com/problems/single-number/description/ Single Number - LeetCode Single Number - Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space. Example 1: Input: nums = [2 leetcode.com 한 번만 등장하는 원소를 추출하자 필요한 개념 set 자료구조 XOR 연산 풀이 처음에 S..

문제 Restore IP Addresses - LeetCode 12)return ans; helper(s, "", 0, 0); return ans; } public void helper(String s, String cur_str,int level,int idx){ if(level == 4){ if(idx == s.length()) ans.add(cur_str.substring(0, cur_str.length()-1)); return; } for(int i =1 ;i 1 && temp_str.charAt(0) == '0' ) || getN(temp_str)..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 큰 수를 만드는 문제 풀이 스택을 사용하여 풀이하였다.로직은 다음과 같다. 1. 주어진 길이가 백만이니 선형 탐색 O(N) 으로 풀어야 한다. 2. 스택의 top 숫자가 현재 숫자 number.charAt(i) 보다 작으면 크거나 같은 숫자가 나올때까지 pop 을 한다. 3. k만큼 제거 한 이후는 스택의 숫자를 합쳐서 리턴한다. 4. 모든 숫자가 내림차순이라서 한번..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 수학 문제를 풀 때 1 부터 n 까지의 수를 for문을 돌리면서 누적합을 하고 싶은가? 아님 n까지의 수의 합 n*(n+1)/2 으로 한 번에 도출 하겠는가? 당연히 후자일 것이다. public int getSum(int n){ int sum = 0 ; for(int i = 1; i < n+1 ;i++) sum += i; return sum; } publi..

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 자 단순하게 O(N) 탐색으로 풀수있다. 쭈루룩 훑어가면서 현재 min 보다 낮은게 나오면 min을 업데이트 해주고 거리 x min 누적합을 구해주면 OK. 참고 자바의 long type을 명시 안하면 int overflow 발생함으로 주의 코드 import java.io.*; import java.util.*; public class Main { int n, k; int..

문제 11501번: 주식 (acmicpc.net) 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 우선순위 큐를 이용하여 풀이한 로직은 다음과 같다. O ( N^2) 1. 우선순위 큐에 배열값을 다 담는다. 2. 방문 해시맵을 만들어 아직 남아있는 개수이면, 해당 key 방문처리하고 꺼낸다. 3. 현재 값이 max Number 보다 작으면 합을 더한다. 4. 현재 인덱스가 maxIdx보다 크면, 최댓값을 for문으로 구한다. 5. 배열 끝까지 2..4 로직을 반복하고 답을 구한다. 그런데 이 ..

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 최대한 적게 멀티플러그를 빼는 문제. 게시판 반례 참고해서 코드 수정 하였다. 풀이는 다음과 같다. 1. 현재 멀티탭이 구멍보다 작을 때 플러그를 꽃는다. 2. 멀티탭 남는 구멍이 없어 플러그를 빼야 하면, 다음 등장하는 인덱스가 가장 큰 것을 플러그에서 제거한다. 3. 이미 멀티탭에 있는 번호가 나왔으면, 다음 등장 인덱스를 업데이트 해준다. 먼저 해시맵을 사용해서 현재 기준 cur ..