씅의 기록하는 개발노트

실무에서 아직 jdk1.6을 사용하지만 최신 자바에 대해 공부하는 중 가장 컸던 변화라 생각한 Stream에 대해 정리하고자 한다.

Stream

Stream은 자바8부터 추가된 기능으로 컬렉션, 배열과 같은 자료구조를 함수형 인터페이스(람다)를 적용하며 처리하는 기능입니다. 즉, 데이터를 담고 있는 자료구조(컬렉션)이 아닙니다.

스트림은 '데이터의 흐름'이며 적절한 operation을 통해 데이터를 가공해 원하는 타입으로 제공합니다.

자바8 이전에는 배열이나 컬렉션을 다루기 위해 for 또는 foreach를 통해 하나씩 꺼내서 다뤘습니다. 간단한 경우는 큰 문제가 없었지만 로직이 복잡해지면 코드의 양은 많아지고 향후 유지보수에도 어려움이 발생합니다.

아래 코드는 기존 for문을 사용한 방법과 stream을 사용한 방법의 예시입니다.

import java.util.*;
public class StreamExample{

     public static void main(String []args){
        List<String> names = new ArrayList<>();
        names.add("seungwoo");
        names.add("sw");
        names.add("jsw");
        names.add("java8");
        
        // 자바 8 이전 for문을 사용한 방법
        for (int i=0; i<names.size(); i++) {
            if (names.get(i).startsWith("s")) {
                System.out.println(names.get(i).toUpperCase());
            }
        }

        // stream을 사용한 방법
        names.stream().filter(name -> name.startsWith("s"))
                .map(name -> name.toUpperCase())
                .forEach(System.out::println);
     }
}

위 코드에서 stream을 이용한 방법을보면 메서드 체이닝을 통해 연산을 합니다. 이러한 오퍼레이션은 중개 오퍼레이션, 종료 오퍼레이션 2가지가 존재합니다.

중개 오퍼레이션

• Stream을 리턴함
• Lazy하다
• filter, map, limit, skip, sorted, flatmap...

여기서 lazy하다는 말은 종료 오퍼레이션이 나오기 전까지는 실행하지 않는 것을 뜻합니다. 즉 결과가 필요하기 전까지 연산의 시점을 최대한 늦추는것을 뜻합니다.

List<String> names = new ArrayList<>();
        names.add("seungwoo");
        names.add("sw");
        names.add("jsw");
        names.add("java8");
        
// list의 내용을 바꾸지 않고 단지 stream으로 가지고 있음
// 중계 operation, 종료 operation이 있음
// 중계 operation는 기본적으로 lazy한데 중계 operation은 stream을 리턴하며 종료 operation은 stream이 아닌 다른타입을 리턴함.
Stream<String> stream = names.stream()
	.map(String::toUpperCase);

이처럼 종료 오퍼레이션이 없는경우 연산을 하지 않습니다.

종료 오퍼레이션

• Stream을 리턴하지 않음
• collect, allMatch, count, forEach, min, max...

List<String> names = new ArrayList<>();
        names.add("seungwoo");
        names.add("sw");
        names.add("jsw");
        names.add("java8");

long count = names.stream()
		.filter(name -> name.startsWith("s"))
		.count();
System.out.println(count);

종료 오퍼레이션이 있는경우 연산이 실행됩니다.

 최근 코딩테스트를 진행하면서 정규표현식과 관련된 문제가 나와 다시 한번 정리해 보기로 결심했다. 

정규표현식이란 특정 규칙을 가진 문자열을 표현하기 위해 쓰이는 식입니다. 개발을 진행하면 보통 주민등록번호, 휴대폰 번호, 이메일주소와 같이 정해져 있는 규칙이 있고 사용자가 형식에 맞게 입력했는지 검증할때 주로 사용합니다.

사실 기존에 정규표현식을 사용할 일이 있으면 구글링을 통해 정규표현식을 확인하고 사용해서 규칙을 정확히 숙지하고 있지 않았습니다. 근데 코딩테스트에서 검색없이 진행하려니 많은 어려움이 있었습니다.

아래는 정규표현식의 기본 작성법입니다.

자바에서는 이러한 정규표현식을 사용하기 위해 Pattern과 Matcher클래스를 사용합니다. 간단한 예제를 통해 살펴보겠습니다.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) {

        // test를 위한 임시 String 배열
        String[] names = {"seungwoo", "sw", "jsw"};

        // 소문자 sw로 시작하는 단어
        Pattern pattern = Pattern.compile("sw[a-z]*");

        for (String name : names) {

            // 정규식으로 비교할 대상을 매개변수로 Pattern 클래스의 matcher 메서드를 호출해 인스턴스를 얻음
            Matcher matcher = pattern.matcher(name);

            // 정규식에 부합한지 체크
            if (matcher.matches()) {
                System.out.println(name);
            }
        }
    }
}

결과

Pattern클래스의 compile메서드를 통해 정규표현식으로부터 패턴을 만듭니다. 이후 패턴에 맞는 Matcher 객체를 pattern.matcher 메서드를 통해 반환하고 정규식에 부합한지 체크하는 과정입니다.

Matcher클래스의 matches 메서드는 정규식에 부합하면 true, 부합하지 않으면 false를 반환합니다.

Pattern과 Matcher 클래스의 더 상세한 메서드는 API를 통해 쉽게 확인할 수 있습니다.

정규표현식의 사용법은 간단하나 정규표현식 기본규칙을 암기하고 있지 않으면 이러한 문제를 만났을때 당황할 것 같습니다.

사실 모든걸 외울 수는 없으나 기본적인 정규표현식 규칙은 암기하고 있어야 할 것 같습니다.

Jsoup을 이용한 웹 크롤링 간단 예제 입니다.

Jsoup을 사용하기 위해서는 의존성을 받아야 하는데 maven repository에서 받으면 됩니다.

https://mvnrepository.com/

저는 네이버 증권 페이지에서 진행하겠습니다. 네이버 증권 페이지를 들어가고 개발자 도구에 들어가서 코스피 지수를 확인합니다.

코스피 지수의 태그를 선택하고 개발자 도구에서 ...을 클릭하면 그림과 같이 css selector를 클립보드로 복사 할 수 있습니다.

여기서 저는 코스피 지수와 변동지수만 가져오도록 하겠습니다.

KospiCrawer

import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.jsoup.select.Elements;

public class KospiCrawer {
    private static final String CONNECT_URL ="https://finance.naver.com/";
    
    // 현재 코스피지수
    public String getKospi() throws Exception {
        Document document = Jsoup.connect(CONNECT_URL).get();
        Elements kospi = document.select("#content > div.article > div.section2 > div.section_stock_market > div.section_stock > div.kospi_area.group_quot.quot_opn > div.heading_area > a > span > span.num");
        return kospi.text();
    }

	// 코스피 변동지수
    public String getKospiChangeRate() throws Exception {
        Document document = Jsoup.connect(CONNECT_URL).get();
        Elements kospiChangedRate = document.select("#content > div.article > div.section2 > div.section_stock_market > div.section_stock > div.kospi_area.group_quot.quot_opn > div.heading_area > a > span > span.num2");
        return kospiChangedRate.text();
    }
}

copy selector로 복사한 것을 select메서드를 활용해 가져왔습니다.

Main

public class CrawlingApplication {

    public static void main(String[] args) throws Exception {
        KospiCrawer kospiCrawer = new KospiCrawer();
        String currentKospi = kospiCrawer.getKospi();
        String changeKospiRate = kospiCrawer.getKospiChangeRate();
        System.out.println("현재 코스피 : " + currentKospi + " 변동율 : " + changeKospiRate);
    }

}

결과

이처럼 Jsoup을 사용하면 간단하게 크롤링을 할 수 있다. 하지만 크롤링을 이용해 상업적으로 이용한다면 문제가 있을 수 있으니 주의하도록 하자.

문제출처

https://www.acmicpc.net/problem/1062

문제풀이

문자열을 처리하는 문제이다. 문제에서 남극언어는 "anta"로 시작되고 "tica"로 끝난다고 주어졌다. 즉 모든 언어를 읽기 위해서는 "a", "n", "t", "i", "c"는 무조건 배워야 한다는 것이다. 즉 k가 주어졌을때 이 5개는 배웠다 생각하고 처리했다. 주어진 n개의 단어에서 replaceAll 메서드를 활용해 5개 문자를 제외시켰고 문자를 배웠음을 의미하는 visit배열을 true처리해줬다.

이후 dfs를 이용해서 k개의 단어를 배울때까지 모든 방법을 전체 탐색해 k개의 단어를 배웠다면 읽을 수 있는 단어의 갯수를 카운팅해주는 방식으로 풀이했다.

지금 생각해보니 visit배열대신 비트마스크를 사용해도 될것같다. 아래글처럼 visit배열대신 비트마스크를 사용할 수 있다. 

프로그래머스 64064] - 카카오 불량 사용자

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_1062.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1062 {
    private static int n, k, ans;
    private static String[] words = new String[51];
    private static boolean[] visit = new boolean[26];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

    private static void init() throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String word = st.nextToken();

            // a n t i c 필수
            word = word.replaceAll("a" , "");
            word = word.replaceAll("n" , "");
            word = word.replaceAll("t" , "");
            word = word.replaceAll("i" , "");
            word = word.replaceAll("c" , "");
            words[i] = word;
        }
        visit['a'-'a'] = true;
        visit['n'-'a'] = true;
        visit['t'-'a'] = true;
        visit['i'-'a'] = true;
        visit['c'-'a'] = true;

    }
    private static void checkString() {
        int count = 0;

        for (int i=0; i<n; i++) {
            boolean isRead = true;
            for (int j=0; j<words[i].length(); j++) {
                if (!visit[words[i].charAt(j) - 'a']) {
                    isRead = false;
                    break;
                }
            }

            if (isRead) {
                count++;
            }
        }
        ans = Math.max(ans, count);
    }

    private static void dfs(int index, int depth) {
        if (depth == k) {
            checkString();
            return;
        }

        for (int i=index; i<26; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            dfs(i, depth+1);
            visit[i] = false;
        }
    }

    public static void main(String[] args) throws Exception {
        init();
        // a n t i c 필수
        if (k < 5) {
            System.out.println(0);
            return;
        } else if (k == 26) {
            System.out.println(n);
            return;
        }
        k -= 5;
        dfs(0, 0);
        System.out.println(ans);
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/1829

문제풀이

삼성 역량테스트를 준비할때 많이 풀어본 유형이다. 기본적인 BFS문제로 완전탐색을 했다. BFS탐색을 할때마다 영역의 개수가 1개씩 증가하고 각 영역의 크기를 구하면 되는 문제다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%B9%B4%EC%B9%B4%EC%98%A4%ED%94%84%EB%A0%8C%EC%A6%88%20%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81.cpp

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { 1, 0, -1, 0 };
bool visit[100][100] = { 0, };
int bfs(int sy, int sx, int m, int n, vector<vector<int>> picture) {
    int color = picture[sy][sx];
    int size = 1;
    queue<pair<int, int> > q;
    q.push(make_pair(sy, sx));
    visit[sy][sx] = 1;
    
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny<0 || nx<0 || ny>=m || nx>=n || visit[ny][nx] || picture[ny][nx] != color) continue;
            visit[ny][nx] = 1;
            q.push(make_pair(ny, nx));
            size++;
        }
    }
    return size;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            visit[y][x] = 0;
        }
    }
    int areaCount = 0;
    int maxAreaCount = 0;
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            if (visit[y][x] || picture[y][x] == 0) continue;
            maxAreaCount = max(maxAreaCount, bfs(y, x, m, n, picture));
            areaCount++;
        }
    }
    vector<int> answer(2);
    answer[0] = areaCount;
    answer[1] = maxAreaCount;   
    return answer;
}

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/49994

문제 풀이

문제가 엄청 직관적이라 금방 풀었다. 방향문자열을 1개씩 받아와 동,서,남,북 방향을 결정하고 위치를 이동하면 됩니다.

visit배열이 4차원배열인 이유는 방향성그래프가 아니기 때문입니다. 즉 (y, x) -> (ny, nx)로 이동했다면 (ny, nx) -> (y, x)의 길을 걸었기 때문에 이를 체크하기 위함입니다.

삼성 역량테스트 기출과 유형이 비슷한 문제

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EB%B0%A9%EB%AC%B8%20%EA%B8%B8%EC%9D%B4.java

class Solution {
    private static int dy[] = { 0, 1, 0, -1 };
    private static int dx[] = { 1, 0, -1, 0 };
    private static boolean visit[][][][] = new boolean[11][11][11][11];
    
    public int solution(String dirs) {
        int answer = 0;
        int y = 5;
        int x = 5;
        
        int dirIndex = 0;
        for (int i=0; i<dirs.length(); i++) {
            char dir = dirs.charAt(i);
            if (dir == 'U') {
                dirIndex = 3;
            } else if (dir == 'D') {
                dirIndex = 1;
            } else if (dir == 'R') {
                dirIndex = 0;
            } else if (dir == 'L') {
                dirIndex = 2;
            }
            
            int ny = y + dy[dirIndex];
            int nx = x + dx[dirIndex];
            
            // 지도를 벗어난 경우는 제외
            if (ny<0 || nx<0 || ny>=11 || nx>=11) continue;
            
            // (y,x) => (ny, nx)로 가는 길을 처음 걸을때
            if (!visit[y][x][ny][nx] == true && !visit[ny][nx][y][x] == true) {
                visit[y][x][ny][nx] = true;
                visit[ny][nx][y][x] = true;   
                answer++;            
            }
            
            // 현재 좌표 갱신
            y = ny;
            x = nx;
        }
        return answer;
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/64064

문제풀이

정규표현식과 완전탐색으로 풀이하면 되는 문제입니다. DFS시 저는 bitmask를 visit배열 대신 사용해서 풀이했습니다. 

문제를 풀이할때 제가 생각한 알고리즘은 다음과 같습니다.

1. *문자를 정규표현식에 맞게 .로 치환

2. pattern과 matcher를 사용해 응모자 아이디와 매칭되는지 판단

3. 매칭이 된다면 길이가 같은지 판단

4. 이미처리한 사항(방문한 사항)이라면 건너뛰고 처리하지 않았다면 dfs함수를 호출

5. banned_id와 지금까지 찾아낸 제제된 아이디의 사이즈(bannedIdSize)가 같다면 set에 추가

6. 중복없는 set의 사이즈를 반환

비트마스크가 익숙하지 않은 분이면 아래 포스팅을 참고하시면 도움이 되실겁니다.

2019/01/28 - [Algorithm 이론] - [Bitmask] 비트마스크 기초

레벨3문제인데 개인적으로 어렵게 풀이한 문제였습니다. 정규표현식과 비트마스크 개념을 다시 확인할 수 있던 문제

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EB%B6%88%EB%9F%89%20%EC%82%AC%EC%9A%A9%EC%9E%90.java

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

// * 문자 . 로 치환
// Pattern matcher를 사용해 해당되는 문자인지 판단
// 해당된다면 길이도 같은지 확인하고 이미 추가한 아이디가 아니라면 set에 추가
class Solution {
    private static HashSet<Integer> set;
    public int solution(String[] user_id, String[] banned_id) {
        set = new HashSet<>();
        dfs(user_id, banned_id, 0, 0, 0);
        return set.size();
    }
    
    private static void dfs(String[] user_id, String[] banned_id, int index, int bannedIdSize, int visitBit) {
        if (bannedIdSize == banned_id.length) {
            set.add(visitBit);
            return;
        }
        
        for (int i=0; i<user_id.length; i++) {
            String changeBannedId = banned_id[index].replace("*", ".");
            Pattern pattern = Pattern.compile(changeBannedId);
            Matcher matcher = pattern.matcher(user_id[i]);
            
            // 정규 표현식에 매칭되고 길이가 같으면
            if (matcher.find() && user_id[i].length() == banned_id[index].length()) {
                
                // 이미 방문한 것은 건너뜀
                if ((visitBit & (1<<i)) == 1<<i) continue;
                dfs(user_id, banned_id, index+1, bannedIdSize+1, (visitBit | (1<<i)));
            }
        }
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/64062

문제풀이

문제를 풀기 이전에 이분탐색에 대해 익숙하지 않다면 이글을 먼저 읽는게 이해가 빠르실 겁니다.

[Algorithm] - [프로그래머스 43238] - 입국심사

입국심사 문제와 같이 이분탐색을 이용한 문제입니다. 

한번에 건너뛸 수 있는 칸수 = k
stones = 징검다리 값

lowCount = 최소 인원수

highCount = 최대 인원수

averageCount = 건널 수 있는 인원수

문제의 핵심은 이분탐색 문제로 재해석 하는 것이다. 건넌 사람이 3명인경우 stone[i] - 3의 값이 양수여야 다리가 남아있는 경우이다. 이외의 경우 징검다리가 사라진 경우여서 건너뛰어야 하며 건너뛰는 징검다리 수를 저장하는 jumpCount변수에 저장한다.

jumpCount 변수는 최대 점프 횟수인 k를 넘을 수 없으며 k이상인 경우 최대 건너뛸 수 있는 사람의 제한을 줄여 재 탐색한다.

n = 건넌 사람

stones[i] = 징검다리 값

문제를 푸는데 입국심사 문제가 큰 도움이 되었다. 이해가 잘 되지 않는다면 위에있는 입국심사 포스팅을 읽고 문제를 풀어보면 더 쉬울거라 생각된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.java

class Solution {
   
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        // 건너뛰는 최소 인원수
        int lowCount = 1;   
        
        // 건너뛰는 최대 인원수
        int highCount = Integer.MAX_VALUE;  
        
        // 이분탐색에서 이용할 중간값
        int averageCount = (lowCount + highCount) / 2;  
        
        while (lowCount <= highCount) {
            averageCount = (lowCount + highCount) / 2;
            
            // 건너뛴 징검다리 수
            int jumpCount = 0;
            for (int i=0; i<stones.length; i++) {
                if (stones[i] - averageCount <= 0) {
                    jumpCount++;
                } else {
                    jumpCount = 0;
                }
                
                // k개 이상 건너뛰어야 하는경우 건너뛰는 인원수를 반으로 줄인다
                if (jumpCount >= k) {    
                    highCount = averageCount - 1;
                    break;
                }
            }
            
            // 건너뛴 징검다리 개수가 k개 미만인 경우 인원수를 늘린다.
            if (jumpCount < k) {
                lowCount = averageCount + 1;
                answer = lowCount;
            }  
        }

        return answer;
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/43238

문제풀이

이분탐색을 응용한 문제입니다. 처음에 왜 이문제가 이분탐색인지 몰랐는데 다른 블로그를 보면서 이해할 수 있었습니다. 이 문제는 times배열에 각 심사관이 한명을 심사하는데 걸리는 시간 정보가 주어지고 n명을 모두 심사할 때 심사시간의 최소값을 구하는 문제입니다.

n의 최대값은 10억이며 times의 최대 크기는 10만입니다. n의 값이 크기 때문에 일반적인 풀이로는 풀수 없고 시간복잡도를 줄일 수 있는 답안을 생각해야 합니다.

입출력 예시로 주어진 대로 6명을 심사하고 각각 7분, 10분이 걸리는 2명의 심사관이 있는 경우를 생각해보겠습니다.

걸리는 시간을 기준으로 이분탐색을 할 예정이며 최소시간은 1분 최대시간은 n X 가장 오래걸리는 심사관의 시간 으로 시작했습니다. 이 문제에서 이분탐색을 할 때 핵심은 mid시간 이내에 심사가능한 인원의 수는 sum(mid / times[i])라는 것입니다.

최소시간을 left, 최대시간을 right변수에 담아 평균 시간을 mid에 저장합니다. 즉 1 // 30 // 60 으로 이분탐색을 시작합니다.

mid = 30

30분 이내에 심사가능한 인원은 (30 / 7) + (30 / 10) 으로  4 + 3 = 7명입니다.

7은 6보다 크므로 6명을 심사하기 위해서는 30분보다 더 적은 시간에도 가능한 것을 유추할 수 있습니다. 즉 rigth 변수값을 mid - 1을 해 29로 저장한뒤 재탐색 합니다. 이때 29분에는 6명을 심사할 수 없을 수도 있기 때문에 answer에 mid값을 저장합니다.

mid = (1 + 29) / 2 = 15

1 // 30 // 60 에서 1 // 15 // 30 으로 탐색범위가 반으로 줄었습니다. 15분 이내에 심사가능한 인원은 (15 / 7) + (15 / 10) = 2 + 1 = 3명입니다. 3은 6보다 작으므로 6명을 심사하기 위해서는 15분보다는 더 시간이 필요한 것을 알 수 있습니다. 이분탐색을 위해 left 값을 1에서 16으로 바꾼 후 탐색을 다시 시작합니다.

mid = (16 + 30) / 2 = 22

1 // 15 // 30 에서 16 // 22 // 30 으로 탐색범위가 또 반으로 줄었습니다. 22분 이내에 심사가능한 인원은 (22 / 7) + (22 / 10) = 3 + 2 = 5명입니다. 5는 6보다 작으므로 6명을 심사하기 위해서는 22분보다 시간이 더 필요합니다. left 값을 16에서 23으로 바꾼 뒤 탐색을 다시 시작합니다.

반복해서 나아가면

mid = (23 + 30) / 2 = 26

....

mid =  (26 + 30) / 2 = 28

(28 / 7) + (28 / 10) = 4 + 2 = 6명이므로 28이 정답임을 알 수 있습니다.

각각의 탐색과정에서 범위가 반으로 줄고 있으므로 시간복잡도는 O(logN)입니다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.java

import java.util.Arrays;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        
        long left = 1;
        long right = (long)n * times[times.length - 1];
        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
            
            // 심사 가능한 인원 = 시간 / 심사하는데 걸리는 시간
            for (int i=0; i<times.length; i++) {
                count += mid / times[i];
            }
            
            // mid 시간동안 심사한 인원이 n명보다 적은 경우 시간이 더 필요
            if (count < n) {
                left = mid + 1;
            } else { // 심사한 인원이 n명 이상인 경우 시간을 줄여도 됨
                right = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/12981

문제풀이

이 문제도 역시 중복을 검사하는 문제다. 중복을 검사하길래 바로 set자료구조를 떠올려서 풀었다. 사실 set 자료구조보다 사람순서와 언제 틀렸는지 구하는 규칙을 찾아내는게 주요 목적이다. 중복검사는 set이 아니여도 충분히 가능하기 때문이다.

전에 말했던 마지막글자와 첫글자가 다르거나 중복된경우 순서를 저장하고 retrun하면 되기 때문에 같은 if문에 묶어 처리했다.

같은 level2문제여도 카카오 level2가 더 어렵게 느껴진다 ㅠ 생각할 것도 많고... 이 문제는 level1정도로 생각된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%98%81%EC%96%B4%20%EB%81%9D%EB%A7%90%EC%9E%87%EA%B8%B0.java

import java.util.*;
class Solution {
    // n명 
    // i % n 값에 +1 한게 사람순서
    // i / n 값에 +1 한게 차례
    // 끝글자랑 다음의 처음글자 확인
    public int[] solution(int n, String[] words) {
        int[] answer = {0, 0};
        Set<String> historySet = new HashSet<>();
        historySet.add(words[0]);
        char prevCharacter = words[0].charAt(words[0].length() - 1);
        
        for (int i=1; i<words.length; i++) {
            historySet.add(words[i]);
            if (!words[i].startsWith(Character.toString(prevCharacter)) || historySet.size() != i+1) {
                answer[0] = (i%n)+1;
                answer[1] = (i/n)+1;
                break;
            }
            prevCharacter = words[i].charAt(words[i].length() - 1);
        }
        return answer;
    }
}