time
long currentTime = System.currentTimeMillis();
표준입출력처리
leetcode
2
leet code
아래 예시는 위 인풋을 처리할 수 있다.
import java.util.*
public class coupang1 {
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine(); // 문자열 s 입력
int n = Integer.parseInt(scanner.nextLine()); // 사전 단어의 개수 입력
String[] wordDictArray = scanner.nextLine().split(" "); // 공백으로 구분된 사전 단어 입력
List<String> wordDict = Arrays.asList(wordDictArray); // 배열을 리스트로 변환
}
}
Scanner로 속도가 느릴때
인풋개수가 클때는 Scanner가 느릴 수 있다. 이때 bufferedReader를 쓰면 몇 배 빠르게 할 수 있다.
// before
Scanner sc = new Scanner(System.in);
int n = sc.nextInt()
List<Integer> arr = new ArrayList<>();
for(int i=0;i<n;i++) arr.add(sc.nextInt());
// after
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Integer> arr = new ArrayList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) arr.add(Integer.parseInt(st.nextToken()));
자료구조 관련
LinkedList 사용하기
헷갈리는 linkedList사용법을 정리한다.
예시문제:
두 개의 정렬된 연결 리스트로부터 중앙값을 계산하십시오.
예시 1:
L1 = 1 -> 3
L2 = 2
중앙값은 2.0입니다.
예시 2:
L1 = 1->2
L2 = 3->4
중앙값은 (2+3)/2 = 2.5입니다.
input1:
2
1 2
1
3
output1:
2.0
input2:
3
1 3 5
3
2 4 6
output2:
3.5
솔루션
import java.util.*;
public class Main {
public static void main(String args[]){
LinkedList<Integer> list1 = new LinkedList<>();
LinkedList<Integer> list2 = new LinkedList<>();
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
for(int i=0;i<n1;i++) list1.add(sc.nextInt()); // 추가는 add()
int n2 = sc.nextInt();
for(int i=0;i<n2;i++) list2.add(sc.nextInt());
int N = n1+n2;
//합친 리스트의 개수가 홀수개이면 n/2 번째인덱스
//짝수개이면 n/2-1, n/2번째 인덱스의 평균이 답
int mid_six = N%2==1?N/2:N/2-1;
int mid_eix = N%2==1?N/2:N/2;
ListIterator<Integer> it1 = list1.listIterator(); // next()하려면 Iterator필요
ListIterator<Integer> it2 = list2.listIterator();
int median1 = 0, median2 = 0;
for (int i = 0; i <= mid_eix; i++) {
int v1 = it1.hasNext() ? it1.next() : Integer.MAX_VALUE; // hasNext()눈여겨 보자
int v2 = it2.hasNext() ? it2.next() : Integer.MAX_VALUE;
int value;
if (v1 < v2) {
value = v1;
if (v2 < Integer.MAX_VALUE) it2.previous(); // previous()도 가능
} else {
value = v2;
if (v1 < Integer.MAX_VALUE) it1.previous();
}
if (i == mid_six) median1 = value;
if (i == mid_eix) median2 = value;
}
System.out.println((double)(median1 + median2) / 2.0);
sc.close();
}
}
LinkedList 선언부, ListIterator, next()/previous() 처리 등을 눈여겨 보자.
근데 사실 이 문제의 경우에는 꼭 LinkedList를 쓸필요는 없다. ArrayList로도 충분.
ArrayList
c++ vector에 해당하며 다음과 같이 쓸 수 있다.
ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
int value = list.get(1); // 20을 가져옵니다.
c++과 다르게 list[1]등으로 배열인덱스는 쓰지 못함에 주의
HashMap
c++ map에 해당하며 다음과 같이 쓸 수 있다.
HashMap<Integer, String> map = new HashMap<>();
HashMap<Integer, List<Integer>> map2 = new HashMap<>();
for (int i = 0; i < N; i++) {
String a = map.getOrDefault(C[i],"");
List<Integer> b = map2.getOrDefault(C[i],new ArrayList<>());
a+=S[i];map.put(C[i],a);
b.add(i);map2.put(C[i],b);
}
getOrDefault()에 주목해보자. 이걸안쓰고 get()을 쓰면 항상null체크를 해줘야 한다.
(C++의 std::map에서는 요청한 키가 존재하지 않으면 해당 키를 자동으로 생성하고 해당 값 타입의 기본 생성자를 호출하여 값을 초기화)
containKey(key)를 쓰면 put()했는지 체크할 수 있다. (c++에서 map.count()와 같은 기능)
iteration하기
다음 4가지 정도 방법이 있다.
//방법1. 전통적인 방법.. Entry개념때문에 복잡하다.
int total_anagrams = 0;
Iterator<Map.Entry<String,Integer>> iterator = ana_map.entrySet().iterator();
int total_anagrams = 0;
while(iterator.hasNext()){
Map.Entry<String, Integer> entry = iterator.next();
total_anagrams += entry.getValue();
}
//방법2. key나 value한쪽만 필요한 경우 다음처럼 간략화 가능
int total_anagrams = 0;
for (Integer value : ana_map.values()) {
total_anagrams += value;
}
//방법3. key나 value 둘다 필요하면서 약간 더 간단한 방법
for (Map.Entry<String, Integer> entry : ana_map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
// key와 value를 사용한 작업
}
//방법4. 조금 더 간단한 방법(람다 표현식)
ana_map.forEach((key, value) -> {
// key와 value를 사용한 작업
});
Queue
이 문제에 대한 솔루션인데, 단순한 BFS로 풀린다.
queue사용법을 눈여겨보자(add, poll, size)
class Solution {
private void check(Queue<Integer> q, int[][] mat, int[][] dist, int py, int px, int y, int x){
int h = mat.length;
int w = mat[0].length;
if(y<0||y>=h) return;
if(x<0||x>=w) return;
if(dist[y][x]>dist[py][px] + 1) {
dist[y][x] = dist[py][px]+1;
q.add(y);
q.add(x);
}
}
public int[][] updateMatrix(int[][] mat) {
int h = mat.length;
int w = mat[0].length;
int[][] dist = new int[h][w];
Queue<Integer> q = new ArrayDeque<>();
for(int y=0;y<h;y++)for(int x=0;x<w;x++)dist[y][x]=Integer.MAX_VALUE;
for(int y=0;y<h;y++)for(int x=0;x<w;x++){
if(mat[y][x]==0) {
dist[y][x]=0;
q.add(y);q.add(x);
}
}
while(q.size()>0){
int cy = q.poll();
int cx = q.poll();
check(q,mat,dist,cy,cx,cy-1, cx);
check(q,mat,dist,cy,cx,cy+1, cx);
check(q,mat,dist,cy,cx,cy, cx-1);
check(q,mat,dist,cy,cx,cy, cx+1);
}
return dist;
}
}
Stack
c++과 비슷하게 push(), pop()인데 pop()이 top()+pop()이라고 보면된다. (값을 리턴하면서 즉시 pop도 하는..)
top()만 하려면 peek()를 쓰면된다.(아래 샘플엔 없다)
아래 샘플참조..
import java.util.*;
public class StackStringDecoder {
public static String decodeString(String s) {
Stack<Integer> stack_repeat = new Stack<>();
Stack<String> stack_str = new Stack<>();
String ret_str = new String("");
int repeat = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
repeat *= 10;
repeat += c-'0';
}else if(c=='['){
stack_repeat.push(repeat); // push하는 부분
stack_str.push(ret_str);
ret_str = "";
repeat = 0;
}else if(c==']'){
String pop_str = stack_str.pop(); // pop하는 부분
repeat = stack_repeat.pop();
for(int j=0;j<repeat;j++)
pop_str += ret_str;
ret_str = pop_str;
//repeat = 0;
}else{
assert(Character.isAlphabetic(c));
ret_str+=c;
}
}
return ret_str;
}
public static void main(String[] args) {
System.out.println(decodeString("3[a2[c]]")); // "accaccacc"
System.out.println(decodeString("3[a]2[bc]")); // "aaabcbc"
System.out.println(decodeString("2[abc]3[cd]ef")); // "abcabccdcdcdef"
System.out.println(decodeString("2[a3[b]]")); // "abbbabbb"
System.out.println(decodeString("1[ab2[c]]")); // "abcc"
}
}
char[]
String은 immutable이라 글자단위로 수정하려면 char[]로 변환해주어야 한다.
char[] chars = myString.toCharArray(); //String에서 char[]로 변환
String myString = new String(chars); //char[]에서 String으로 변환
한번 println의 경우는 다음과 같이 String으로 변환해주지 않으면 주소가 출력된다.
char[] result = {'H', 'e', 'l', 'l', 'o'};
System.out.println(new String(result)); // "Hello"를 출력합니다.
리턴값이 2개 필요할때
아래처럼 int[] r = func(); 해서 r[0], r[1]을 쓰면된다.
static int[] parseNumber(String s, int ix) {
int number = 0;
while (ix < s.length() && Character.isDigit(s.charAt(ix))) {
number = number * 10 + (s.charAt(ix) - '0');
ix++;
}
return new int[] {number, ix};
}
public static void main(String[] args) {
String expression = "12345+6789";
int ix = 0;
int[] result = parseNumber(expression, ix);
int parsedNumber = result[0];
int nextIndex = result[1];
System.out.println("Parsed number: " + parsedNumber); // 출력: Parsed number: 12345
System.out.println("Next index: " + nextIndex); // 출력: Next index: 5
}
String 핸들링
시간과 같이 특정 글자로 split할때는 아래코드 참조하자(아래는 12포맷을 AM, PM글자 떼버리고 24포맷으로 바꾸는 코드이다)
자바는 아예 split()함수가 있어서 오히려 c++보다 수월하다.
public class Main {
public static void main(String[] args) {
String inputTime = "07:05:45PM";
String outputTime = timeConversion(inputTime);
System.out.println(outputTime); // 출력: 19:05:45
}
public static String timeConversion(String s) {
String[] timeParts = s.substring(0, 8).split(":");
int hour = Integer.parseInt(timeParts[0]);
if (s.endsWith("PM") && hour != 12) {
hour += 12;
} else if (s.endsWith("AM") && hour == 12) {
hour = 0;
}
return String.format("%02d:%s:%s", hour, timeParts[1], timeParts[2]);
}
}
참고삼아 c++버전도 기록해둔다.
#include <iostream>
#include <sstream>
#include <iomanip>
std::string timeConversion(const std::string& s) {
int hour, minute, second;
char colon, am_pm;
std::istringstream ss(s.substr(0, 8));
ss >> hour >> colon >> minute >> colon >> second;
if (s.find("PM") != std::string::npos && hour != 12) {
hour += 12;
} else if (s.find("AM") != std::string::npos && hour == 12) {
hour = 0;
}
std::ostringstream result;
result << std::setw(2) << std::setfill('0') << hour << ":"
<< std::setw(2) << std::setfill('0') << minute << ":"
<< std::setw(2) << std::setfill('0') << second;
return result.str();
}
int main() {
std::string inputTime = "07:05:45PM";
std::string outputTime = timeConversion(inputTime);
std::cout << outputTime; // 출력: 19:05:45
return 0;
}
sort
기본적인 sorting법
Array의 경우 다음과 같이 Arrays.sort() 또는 Collections.sort()를 쓴다.
import java.util.Arrays;
public class SortArrayExample {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 3, 7};
// 배열 정렬
Arrays.sort(numbers); // 이경우는 Collections.sort()는 못쓴다.
// 정렬된 배열 출력
System.out.println("Sorted array: " + Arrays.toString(numbers));
}
}
역순으로 정렬하려면 다음과 같이 한다.
// 기본 배열은 Collections를 지원하지 않고 reverseOrder()도 사용할 수 없다.
// 따라서 List<Integer>로 변환후 수행한다.
Integer[] numbers = {5, 2, 8, 1, 3, 7};
List<Integer> number_list = Arrays.asList(numbers);
Collections.sort(number_list, Collections.reverseOrder()); // 이경우는 Collections.sort()는 못쓴다.
System.out.println("Sorted array: " + Arrays.toString(numbers));
구조체 정렬시 특정 필드에 대해 정렬하기
class Tweet {
Long time;
int tweetId;
}
List<Tweet> feed;
...
//time필드에 대해 정렬
feed.sort((t1, t2) -> t1.time.compareTo(t2.time));
//time필드에 대해 역순정렬
feed.sort((t1, t2) -> t2.time.compareTo(t1.time));
//아래처럼 전통적인 compare함수를 쓸 수도 있다.
Collections.sort(feed, new Comparator<Tweet>() {
@Override
public int compare(Tweet t1, Tweet t2) {
return t1.time.compareTo(t2.time);
}
});
//먼저 time에 대해 역순정렬하고, tweetId에 대해서 정방향정렬하기
feed.sort(Comparator.comparing((Tweet t) -> -t.time)
.thenComparing(t -> t.tweetId));
//방법2
feed.sort(Comparator.comparing((Tweet t) -> t.time)
.thenComparing(Comparator.comparing((Tweet t) -> t.tweetId).reversed()));
//방법3
feed.sort(Comparator.comparing((Tweet t) -> t.time)
.thenComparing((t1, t2) -> t2.tweetId - t1.tweetId));
//올드스쿨
feed.sort(new Comparator<Tweet>() {
@Override
public int compare(Tweet o1, Tweet o2) {
if (o1.time != o2.time) {
return o2.time - o1.time; // time에 대해 역순 정렬
}
return o1.tweetId - o2.tweetId; // tweetId에 대해 정방향 정렬
}
});
