TIL
- 택배 배달과 수거하기
- String 초기화 : 리터럴과 new의 차이
- StringBuffer vs StringBuilder
1. 택배 배달과 수거하기
트럭 하나가 담을 수 있는 택배 개수인 cap에 대해 인덱스 i번째 집에 대해서 deliveries[i]만큼의 택배를 배달하고, pickups[i]만큼의 택배를 수거해야한다. 이 상황에서 트럭의 최소 이동거리를 구해야 한다.
'최소' 이동 거리이므로 그리디 알고리즘, 혹은 dp를 이용해야 한다. 나의 경우 굳이 구분하자면 최대 힙을 이용한 그리디 알고리즘으로 풀었다. 이동거리를 최소로 하기 위해선 물류창고와 가장 멀리 떨어진 집부터 고려해야한다. 정렬을
- 트럭이 물류창고를 출발할 때, 배달을 위한 택배상자를 최대로 챙기도록 했다.
- 가장 멀리 있는 집에서부터 배달할 상자를 상한선
cap까지 챙긴다. 배달을 완료할 수 있으면deliveries에서 삭제하고, 배달할 상자가 남았다면 남은 상자로 값을 업데이트했다. - 트럭이 현재 배달하려는 가장 먼 집까지 도달하면
cap만큼의 택배 상자를 수거할 수 있는 상태가 된다.
- 가장 멀리 있는 집에서부터 배달할 상자를 상한선
- 1번 과정을 끝내고, 돌아오면서 수거를 위해 과정은 똑같다.
- 이때, 만약 상자를 수거해야하는 집이 배달해야하는 집의 거리보다 더 멀다면 해당 라운드에 이동 거리를 업데이트한다.
- 그러나 이때도 따로
cap을 신경쓸 필요는 없다. 수거할 집까지 트럭이 향하는 동안 배달할 집에 상자를 다 배달했다고 생각하면 되기 때문이다.
- 한 번의 왕복 라운드에 이동 거리는 1,2번 과정중 더 멀리 있는 집의 번호에 2를 곱한 값이다.
max()함수를 이용해 구해주었다.
deque을 제외한 다른 라이브러리 없이 최대한 직관적으로 코드를 구성했다.
from collections import deque
def solution(cap, n, deliveries, pickups):
answer = 0
deliveries, pickups = # (거리, 상자)
deque((i+1,deliveries[i]) for i in range(n) if deliveries[i]!=0),
deque((i+1,pickups[i]) for i in range(n) if pickups[i]!=0)
# 배달할 곳에 쭉 배달한 다음 수거하는 전략
while (deliveries or pickups):
cur_dis = 0
# 1. 배달가야지
remain = cap
while (deliveries and remain>0):
dis,box = deliveries.pop()
cur_dis = max(cur_dis,dis)
if (remain < box):
# 더 못담아
deliveries.append((dis,box-remain))
break
else:
remain -= box
# 2. 수거해야지
remain = cap
while (pickups and remain>0):
dis,box = pickups.pop()
cur_dis = max(cur_dis,dis)
if (remain < box):
pickups.append((dis,box-remain))
break
else:
remain -= box
answer += cur_dis * 2
return answer- for 반복문으로 왕복 라운드를 구성했다.
remain에 현재 트럭에 더 담을 수 있는 상자 갯수를 구성했다.remain < box부분이 핵심이다! 더 담을 수는 있지만, 해당 집에 완전히 배달/수거를 하지 못했을 때, 다시deliveries와pickups에 append해주었다.
작년 카카오 기출이었다. 이 문제를 실제 코테 환경에서 풀 수 있을까? 잘 모르겠다..
2. Java 스트링 특징?
1) array of char
대부분의 프로그래밍 언어에서 String은 char 타입의 배열로 이루어져있다. char은 유니코드에서 지원하는 charset을 지원하기 위한 2byte의 primitive type 변수이며, 특이하게 양의 타입만을 갖는 unsigned 정수 자료형이다. 이는 자바 역시 마찬가지이다.
문자열 객체의 toCharArray() 메소드를 통해 문자열의 char 하나하나를 뽑아낼 수 있다.
public class StringBasic {
public static void main(String[] args) {
String string = "string";
for (Character c : string.toCharArray()) {
System.out.print(c); // string
}
}
}2) Immutable
문자열 클래스는 한 번 선언된 후에 내부 필드값이 바뀌지 않는 immutable 객체이다. 이뮤터블이 무엇인지, 그 장점이 무엇인지는 immutable에 대해 설명한 글 참고.
문자열 객체의 subString(), toUpperCase()등의 메소드를 보면, 결국 기존의 String이 아닌 새로운 String 객체를 만들어 return하는 부분을 확인할 수 있다.
3. String 초기화
자바에서 문자열을 초기화하는 방법엔 두 가지가 있다.
String string1 = "리터럴로 초기화";
String string2 = new String("new로 초기화");- 리터럴로 초기화된 string1 문자열 객체는 힙에 존재하는 String Constant Pool에 존재한다.
- new 키워드를 이용해 초기화된 string2 문자열 객체는 힙에 새로 생성된다.
따라서 리터럴로 생성된 문자열과 new를 통해 생성된 문자열은 문자열 내용이 같더라도 다른 객체 주소를 참조한다.
참조 변수가 가리키는 문자열 객체를 그림으로 표현하면 위와 같다. 따라서 같은 참조변수 string1, string2를 "=="연산자를 통해 비교하면 false를 return한다.
// false
System.out.println(string1 == string2);그렇다면, 리터럴로 초기화된 서로 다른 두 참조변수는 어떻게될까?
String string1 = "문자열";
String string2 = "문자열";
// true
System.out.println(string1 == string2);이 경우, string1과 string2는 String Constant Pool의 같은 부분을 참조하기 때문에 true를 return한다. 그림으로 나타내면 아래와 같다.
string3, string4를 new 키워드로 추가하자.
String string3 = new String("문자열");
String string4 = new String("문자열");리터럴과 new 키워드의 차이를 알았다면, 다음 결과가 모두 false로 출력되는 것을 어렵지않게 유추할 수 있다.
// false
System.out.println(string2==string3);
// false
System.out.println(string3==string4);정리할겸, heap 메모리의 상황도 간단하게 그려보자.
intern()
리터럴을 이용해 초기화한 string1과 string2가 같은 주소공간을 바라볼 수 있는 이유는 String 내부의 intern() 메소드 덕분이다. String docs의 intern() 메소드 설명의 일부분이다.
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
String Constant Pool에서 equals() 메소드의 결과가 true가 되는 문자열이 있을 때, 해당 문자열을 반환해준다는 것이다. 만약 없다면 pool에 새로운 문자열을 생성한 뒤 그를 반환한다. 이 경우 문자열을 리터럴로 생성한 것과 같은 효과일 것이다.
예제 코드를 보자!
public class InternExample {
public static void main(String[] args) {
String string1 = "문자열";
String string2 = new String("문자열");
// false
System.out.println(string1 == string2);
string2 = string2.intern();
// true
System.out.println(string1 == string2);
}
}- string1과 string2는 최초에 상수 풀, heap 영역에 따로 존재했다. 따라서 string1 == string2는 false이다.
- string2의 intern() 메소드를 호출했다. "문자열" 문자열은 상수 풀에 존재하므로, 기존에 존재하는 상수 풀 문자열이 string2에 새로 할당될 것이다.
intern()의 결과가 string2에 할당된 후, 메모리 상황을 간단하게 그려보면 아래와 같다. 무슨 일이 일어났는지 쉽게 이해가 갈 것이다.
4. StringBuffer vs StringBuilder
String은 immutable이기 때문에, 문자열 객체에 한 번 저장된 문자열은 바꿀 수 없다. 기존 참조변수가 가리키는 문자열의 내용을 바꾸고 싶다면 새로운 String 객체를 만들고 참조 주소를 바꾸는 수밖에 없다. 하지만 문자열의 변화가 있을 때마다 새로운 String 객체를 만드는 것은 비효율적이다. 이를 위해 mutable한 String 지원 클래스의 등장하는데, 이것이 StringBuffer와 StringBuilder이다.
두 클래스는 문자열의 수정을 지원한다. append(), delete(), replace() 등의 메소드를 통해 기존에 객체가 담고있던 문자열에 문자열을 더하거나 지우거나 대체할 수 있다.
String은 + 연산을 지원하는데, 자바에선 String의 +연산에서 내부적으로 StringBuilder을 이용한다.
String string1 = "a" + "b" + "c" + "d" + "e";
String string2 = (new StringBuilder()).append("a").append("b").append("c").append("d").append("e").toString();javac의 컴파일 타임에 String 관련 최적화를 진행할 때, string1과 string2의 계산은 똑같은 과정을 통해 일어난다.
StringBuffer와 StringBuilder의 전반적인 기능은 동일하지만, 동기화 지원 여부라는 결정적인 차이점이 있다.
// StringBuffer
@Override
@IntrinsicCandidate
public synchronized StringBuffer append(int i) {
toStringCache = null;
super.append(i);
return this;
}
// StringBuilder
@Override
@IntrinsicCandidate
public StringBuilder append(int i) {
super.append(i);
return this;
}StringBuffer에는 "synchronized"가 있는 반면, StringBuilder엔 없다.
따라서 별다른 동기화 작업이 필요없거나, 싱글스레드의 상황이라면 StringBuilder의 성능이 더 좋다. 이곳에서 append() 메소드를 수십만 단위로 호출하며 StringBuilder와 StringBuffer의 성능을 비교한 그래프가 있는데 유용하고 흥미로웠다.
REFERENCE
https://madplay.github.io/post/difference-between-string-stringbuilder-and-stringbuffer-in-java
https://madplay.github.io/post/java-string-literal-vs-string-object
https://ifuwanna.tistory.com/221
