목적
스터디를 하면서 코딩테스트를 준비해야할것같아서 블로그에 같이 쓰면 좋을것같아서 글을 쓴다.
문제1
신고 결과 받기
문제 설명
신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
- 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
- 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
- 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.
- k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
- 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.
다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.
제한사항
2 ≤ id_list의 길이 ≤ 1,000
1 ≤ id_list의 원소 길이 ≤ 10
id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.
id_list에는 같은 아이디가 중복해서 들어있지 않습니다.
1 ≤ report의 길이 ≤ 200,000
3 ≤ report의 원소 길이 ≤ 21
report의 원소는 "이용자id 신고한id"형태의 문자열입니다.
예를 들어 "muzi frodo"의 경우 "muzi"가 "frodo"를 신고했다는 의미입니다.
id는 알파벳 소문자로만 이루어져 있습니다.
이용자id와 신고한id는 공백(스페이스)하나로 구분되어 있습니다.
자기 자신을 신고하는 경우는 없습니다.
1 ≤ k ≤ 200, k는 자연수입니다.
return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
"ryan"이 "con"을 4번 신고했으나, 주어진 조건에 따라 한 유저가 같은 유저를 여러 번 신고한 경우는 신고 횟수 1회로 처리합니다. 따라서 "con"은 1회 신고당했습니다. 3번 이상 신고당한 이용자는 없으며, "con"과 "ryan"은 결과 메일을 받지 않습니다. 따라서 [0, 0]을 return 합니다.
제한시간 안내
정확성 테스트 : 10초
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
// HashMap과 HashSet을 사용 key값의 타입은 String, value(Set) 타입은 String 그리고 set은 중복을 허용하지않는다.
HashMap<String, HashSet<String>> report1 = new HashMap<>(); // 신고 리포트
HashMap<String, HashSet<String>> result = new HashMap<>(); // 결과
// 그리고 리포트를 하나씩 하나씩 처리한다.
// report1안에는 신고한 유저와 신고당한 유저(불량유저)가있다.
for (String r : report) {
String[] str = r.split(" "); // 공백으로 분리한다. ex "muzi frodo" report에서 보면 muzi와 frodo 사이에 공백
// 0번 index에 신고한 유저id가 들어가고 1번 index에 신고당한 유저(불량유저) id 가 들어간다.
// 리포트 안에 넣어야한다. 근데 최초에는 비어있기 때문에 리포트안에 키가있는지 확인해서 최초에 없을거서 false 이다.
if (report1.containsKey(str[0]) == false)
report1.put(str[0], new HashSet<>()); // Set 객체를 생성한후에 넣어줘야한다.
// 최초건 아니건 str[0] 이 key로 get를하면 방금 만든 Set이 나온다.
report1.get(str[0]).add(str[1]); // 여기에 신고한 불량 유저를 추가한다. empty 빈 집합에 추가해준다. 아에 덮어쓰는게 아니라 Set 가져와서 Set안에서 하나하나 추가해준다.
// report.get(str[0].add(str[1]))는 처음에 신고한 str[0] 이 유저가 str[1] 불량유저를 신고했다고 넣어준거다.
// result에도 넣어준다.
if (result.containsKey(str[1]) == false)
result.put(str[1], new HashSet<>()); // 이 key에대해서 hashSet 객체를 생성해서 넣어줘야한다.
result.get(str[1]).add(str[0]); // result.get(str[1].add(str[0]))는 str[1] 불량 유저가 str[0] 이유저에게 신고당했다고 넣어준거다.
}
// str[0] 개수를 가지고 k번째 이상이면 정지당했다고 확인할 수 있다.
// for이 끝나고 나면 report와 result값이 전부다 찰거다.
// 그런다음에 answer에 값을 하나씩 채워야한다.
int[] answer = new int[id_list.length]; // answer를 유저의 개수만큼 생성해야한다.
for (int i = 0; i < answer.length; ++i) { // 각각의 유저에 대해서 메일을 몇개 받게 되는지 확인을 한다.
String user = id_list[i]; // 0부터 하나씩 가져와서 확인한다.
// 유저가 report를 전혀 안했을 수도 있다. report가 먼저있는지 확인한다.
// 만약에 신고한 불량 유저가 하나도없다면 false이다.
// 이경우에는 신고를 하나도 안했기 때문에 받을 메일도 없다. 그래서 아무것도 안하면된다.
// 최초에 answer는 0으로 차있을거다.
// 신고한 불량유저가 없는경우에는 continue에서 0으로 남겨둔다.
if (report1.containsKey(user) == false) continue;
// 누구가를 신고해서 집합을 가져와서 신고한 모든 불량유저에 대해서 정지가 됐는지 확인해야한다.
// .get(user)을 하면 user가 신고한 불량 유저에 집합이 나온다. 집합 원소에 하나하나에 대해서 확인한다.
// result.get에서 불량 유저에 id를 key로해서 get하면 집합이 나오게 돼고 bad 유저를 신고한 유저에 목록에 갯수가 k개 이상이면 정지당한다.
// 이경우에는 메일을 받게 되는거니깐 answer에 값이 증가한다.
for (String bad : report1.get(user)) {
if (result.get(bad).size() >= k)
answer[i]++;
}
}
return answer;
}
}
Hash를 이용하고 Hash value로 set을 이용했다. set은 중복을 허용하지 않는다.
Hash는 시간의 복잡도가 O(1)이기 때문에 제한시간에 통과할 수 있었다.
이번에 문제이외에 디자인 패턴을 심도있게 공부해서 발표해보자라는 의견이 나와서 준비하게 됐습니다.
생성 패턴(Creational Pattern)
디자인 패턴은 크게 생성 패턴, 구조 패턴, 행동 패턴으로 나눠진다. 이 중에서 생성 패턴은 객체를 생성하는 방법에 중점을 두는 디자인 패턴을 말한다. 생성 패턴에 속한 디자인 패턴들은 객체 생성에 관련된 로직을 캡슐화하여 코드의 재사용성을 향상시켜준다.
싱글톤 패턴(Singleton Pattern)
싱글톤 패턴(Singleton Pattern)은 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴이다. 하나의 클래스를 기반으로 여러 개의 개별적인 인스턴스를 만들 수 있지만 그렇게 하지 않고 하나의 클래스를 기반으로 단 하나의 인스턴스를 만들어 이를 기반으로 로직을 만드는데 쓰이며 보통 데이터베이스 연결 모듈에 많이 사용한다.
장점
하나의 인스턴스를 기반으로 해당 인스턴스를 다른 모듈들이 공유하여 사용하기 때문에 인스턴스를 생성할때 드는 비용이 줄어든다. 그렇기 때문에 인스턴스생성에 많은 비용이 드는 I/O 바운드 작업에 많이 사용한다.
단점
의존성이 높아지며 TDD(Test Driven Development)를 할때 걸림돌이 된다. TDD를 할때 단위 테스트를 주로 하는데, 단위 테스트는 테스트가 서로 독립적이어야 하며 테스트를 어떤 순서로든 실행할 수 있어야 한다. 하지만 싱글톤 패턴은 미리 생성된 하나의 인스턴스를 기반으로 구현하는 패턴이므로 각 테스트마다 독립적인 인스턴스를 만들기가 어렵다.
- I/O 바운드: 디스크 연결, 네트워크 통신, 데이터베이스 연결
- 의존성 이란 종속성이라고도 하며 A가 B에 의존성이 있다는 것은 B의 변경 사항에 대해 A 또한 변해야 된다는 것을 의미한다.
class Singleton {
private static class singleInstanceHolder {
private static final Singleton INSTANCE = new Singleton();
}
public static synchronized Singleton getInstance() {
return singleInstanceHolder.INSTANCE;
}
}
public class HelloWorld {
public static void main(String[] args) {
Singleton a = Singleton.getInstance();
Singleton b = Singleton.getInstance();
System.out.println(a.hashCode());
System.out.println(b.hashCode());
if(a == b) {
System.out.println(true);
}
}
}싱글톤 패턴을 구현하는 7가지 방법
1. 단순한 메서드 호출
싱글톤 패턴 생성 여부를 확인하고 싱글톤이 없으면 새로 만들고 있다면 만들어진 인스턴스를 반환한다. 그러나 이 코드는 메서드의 원자성이 결여되었다. 멀티스레드 환경에서는 싱글톤 인스턴스를 2개 이상 만들 수 있다.
public class Singleton {
private static Singleton instance;
private Singleton() {
}
public static Singleton getInstance() {
if(instance == null) {
instance = new Singleton();
}
return instance;
}
}public class Sync {
private static String yeongjun = "오르트구름";
public static void main(String[] args) {
Sync a = new Sync();
new Thread(() -> {
for(int i = 0; i < 10; i++) {
a.say("사건의 지평선");
}
}).start();
new Thread(() -> {
for(int i = 0; i < 10; i++) {
a.say("오르트 구름");
}
}).start();
}
public void say(String song) {
yeongjun = song;
try {
long sleep = (long)(Math.random() * 100);
Thread.sleep(sleep);
} catch (InterruptedException e) {
e.prinStackTrace();
}
if(!yeongjun.equals(song)) {
System.out.println(song + " | " + yeongjun);
}
}
}2. synchronized
인스턴스를 반환하기 전까지 격리 공간에 놓기 위해 synchronized 키워드로 잠금을 할 수 있다. 최초로 접근한 스레드가 해당 메서드 호출시 다른 스레드가 접근하지 못하도록 잠금(lock)을 걸어준다.
이때 getInstance() 메서드를 호출할 때마다 lock이 걸려 성능 저하된다. 또한 인스턴스가 만들어졌는데도 getInstacne()는 호출이 가능하다.
public class Singleton {
private static Singleton instance;
private Singleton() {
}
public static synchronized Singleton getInstance() {
if(instance == null) {
instance = new Singleton();
}
return instance;
}
}public class Sync {
private static String yeongjun = "오르트구름";
public static void main(String[] args) {
Sync a = new Sync();
new Thread(() -> {
for(int i = 0; i < 10; i++) {
a.say("사건의 지평선");
}
}).start();
new Thread(() -> {
for(int i = 0; i < 10; i++) {
a.say("오르트 구름");
}
}).start();
}
public synchronized void say(String song) {
yeongjun = song;
try {
long sleep = (long)(Math.random() * 100);
Thread.sleep(sleep);
} catch (InterruptedException e) {
e.prinStackTrace();
}
if(!yeongjun.equals(song)) {
System.out.println(song + " | " + yeongjun);
}
}
}3. 정적 멤버
정적(static) 멤버나 블록은 런타임이 아니라 최초에 JVM이 클래스 로딩때 모든 클래스들을 로드할때 미리 인스턴스를 생성하는데 이를 이용한 방법이다.
클래스 로딩과 동시에 싱글톤 인스턴스를 만든다. 그렇기 때문에 모듈들이 싱글톤 인스턴스를 요청할 때 그냥 만들어진 인스턴스를 반환하면 되는것이다.
이는 불필요한 자원낭비라는 문제점이 있다. 싱글톤 인스톤스가 필요없는 경우도 무조건 싱글톤 클래스를 호출해 인스턴스를 만들어야 하기 때문이다.
public class Singleton {
private final static Singleton instance = new Singleton();
private Singleton() {
}
public static Singleton getInstance() {
return instance;
}
}4. 정적 블록
정적(static) 블록을 사용해도 된다.
public class Singleton {
private final static Singleton instance = null;
static {
instance = new Singleton();
}
private Singleton() {
}
public static Singleton getInstance() {
return instance;
}
}5. 정적 멤버와 Lazy Holder(중첩 클래스)
singleInstanceHolder라는 내부클래스 하나 더 만듬으로써 Singleton클래스가 최초에 로딩되더라도 함께 초기화가 되지 않고 getInstance()가 호출될때 singleInstanceHolder 클래스가 로딩되어 인스턴스를 생성하게 된다.
class Singleton {
private static class singleInstanceHolder {
private static final Singleton INSTANCE = new Singleton();
}
public static synchronized Singleton getInstance() {
return singleInstanceHolder.INSTANCE;
}
}6. 이중 확인 잠금(DCL)
이중 확인 잠금(DCL, Double Checked Locking)도 있다. 인스턴스 생성 여부를 싱글톤 패턴 잠금 전에 한번, 객체를 생성하기 전에 한 번 2번 체크하면 인스턴스가 존재하지 않을때만 잠금을 걸 수 있기 때문에 앞서 생겼던 문제점을 해결할 수 있다.
public class Singleton {
private volatile Singleton instance;
private Singleton() {
}
public Singleton getInstance() {
if(instance == null) {
synchronized(Singleton.class) { // 이부분이 잠금을 거는부분
if(instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
}volatile
여기사 instance라는 변수에 volatile 키워드를 건 것을 볼 수 있다.
메모리 구조는 다음과 같다. 메인 메모리 위에 CPU 캐시메모리라고 불리는 L3, L2, L1 캐시가 있다.(L4도 드물긴 하지만 L4까지 CPU 캐시 메모리라고 부른다.)
Java에서는 스레드 2개가 열리면 메인 메모리(RAM)으로부터 가져오는 것이 아니라 캐시메모리에서 각각의 캐시메모리를 기반으로 가져오게 된다.
public class Test {
boolean flag = true;
public void test() {
new Thread(()-> {
int cnt = 0;
while (flag) {
cnt++;
}
System.out.println("Thread1 finished\n");
}
).start();
new Thread(()-> {
try {
Thread.sleep(100);
} catch (InterruptedException ignored) {
}
System.out.println("flag to false");
flag = false;
}
).static();
}
public static void main(String[] args) {
new Test().test();
}
}그렇기 때문에 앞의 코드와 같은 변수 값 불일치 문제가 발생할 수 있다.
근데 여기서 volatile 키워드를 추가하게 되면 Main Memory를 기반으로 저장하고 읽어오기 때문에 이문제를 해결할 수 있다.
public class Test {
volatile boolean flag = true;
public void test() {
new Thread(()-> {
int cnt = 0;
while (flag) {
cnt++;
}
System.out.println("Thread1 finished\n");
}
).start();
new Thread(()-> {
try {
Thread.sleep(100);
} catch (InterruptedException ignored) {
}
System.out.println("flag to false");
flag = false;
}
).static();
}
public static void main(String[] args) {
new Test().test();
}
}7. Enum
enum의 인스턴스는 기본적으로 스레드세이프(thread safe)한 점이 보장되기 때문에 이를 통해 생성할 수 있다.
public enum SingletonEunm {
INSTANCE;
public void oortCloud() {
}
}그래서 최고의 방법은 5번과 7번이라고 생각한다. 5번은 가장 많이 쓰인다고 알려져있고 7번은 이펙티브 자바를 쓴 조슈아 블로그가 추천한 방법이다.
Joshua Bloch, Effective Java 2nd Edition p.18
A single-element enum type is the best way to implement as singleton
의존성 주입
싱글톤 패턴은 사용하기가 쉽고 괴장히 싱용적이지만 모듈 간의 결합을 강하게 만들 수 있다는 단점이 있다. 이때 의존성 주입(DI, Dependency Injection)을 통해 모듈 간의 조금 더 느슨하게 만들어 해결할 수 있다.
의존성 주입의 장점
모듈들을 쉽게 교체할 수 있는 구조가 되어 테스팅하기 쉽고 마이그레이션하기도 수월하다. 구현할 때 추상화 레이어를 넣고 이를 기반으로 구현체를 넣어 주기 때문에 애플리케이션 의존성 방향이 일관되고, 애플리케이션을 쉽게 추론할 수 있으며, 모듈 간의 관계들이 조금더 명확해진다.
의존성 주입의 단점
모듈들이 더욱더 분리되므로 클래스 수가 늘어나 복잡성이 증가될 수 있으며 약간의 런타임 페널티가 생기기도 한다.
의존성 주입 원칙
상위 모듈은 하위 모듈에서 어떠한 것도 가져오지 않아야 한다. 둘다 추상화에 의존해야 하며 이때 추상화는 세부 사항에 의존하지 말아야 한다.
마무리
몇일 동안 코딩테스트랑 디자인 패턴을 정리하면서 내가 그동안 몰랐던 부분을 알 수 있게 된것같아서 조금 뿌듯하고 개발자로써 성장하는것같은 느낌이 든다.
