Java - 개인정보 수집 유효 기간, 달리기 경주, 공원 산책

Java

개인정보 수집 유효 기간

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/150370
• 고객의 약관 동의를 얻어서 수집된 1 ~ n 번으로 분류되는 개인정보 n개가 주어짐.
• 각 약관마다 개인정보 보관 유효기간이 정해져 있으며 각 개인정보가 어떤 약관으로 수집되었는지 알고싶음
• 수집된 개인정보는 유효기간 전까지만 보관 가능하며 유효기간이 지났다면 반드시 파기해야 함
  • A라는 약관의 유효기간이 12달이고 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인 정보는 2022년 1월 4일 까지 보관 가능하며 2022년 1월 5일부터 파기해야할 개인정보임
  • 모든 달은 28일까지 있다고 가정함
• 오늘 날짜가 2022.05.19일 때의 예시
  • 첫 번째 개인정보는 A약관에 의해 2021년 11월 1일까지 보관 가능하며, 유효기간이 지났으므로 파기해야 할 개인정보
  • 두 번째 개인정보는 B약관에 의해 2022년 6월 28일까지 보관 가능하며, 유효기간이 지나지 않았으므로 아직 보관 가능
  • 세 번째 개인정보는 C약관에 의해 2022년 5월 18일까지 보관 가능하며, 유효기간이 지났으므로 파기해야 할 개인정보
  • 네 번째 개인정보는 C약관에 의해 2022년 5월 19일까지 보관 가능하며, 유효기간이 지나지 않았으므로 아직 보관 가능
  • 즉 파기해야할 개인정보의 번호는 1, 3번임

• 오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms와 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies가 매개변수로 주어질 때 파기해 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 함수를 작성

제한조건

• today는 "YYYY.MM.DD" 형태로 오늘 날짜를 나타냄
• 1 <= terms 의 길이 <= 20
  • terms의 원소는 "약관 종류 유효기간" 형태로 약관 종류와 유효기간을 공백 하나로 구분한 문자열임
  • 약관 종류는 A ~ Z중 알파벳 대문자 하나이며 terms의 배열에서 약관 종류는 중복되지 않음
  • 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며 1 이상 100 이하임
• 1 <= privacies 의 길이 <= 100
  • privacies[i]는 i+1번 개인정보의 수집 일자와 약관 종류를 나타냄
  • privacies의 원소는 "날짜 약관 종류"의 형태의 날짜와 약관 종류를 공백 하나로 구분한 문자열임
  • 날짜는 "YYYY.MM.DD" 형태의 개인정보가 수집된 날짜를 나타내며, today 이전의 날짜만 주어짐
  • privacies의 약관 종류는 항상 terms에 나타난 약관 종류만 주어짐
• today와 privacies에 등장하는 날짜의 YYYY는 연도, MM은 월, DD는 일을 나타내며 점(.)하나로 구분되어있음
  • 2000 <= YYYY <= 20200
  • 1 <= MM <= 12
  • MM이 한 자릿수인 경우 앞에 0이 붙음
  • 1 <= DD <= 28
  • DD가 한 자릿수인 경우 앞에 0이 붙음
• 파기해야할 개인정보가 하나 이상 존재하는 입력만 주어짐

입출력 예시

나의 풀이

import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> solution(String today, String[] terms, String[] privacies) {
        DateTimeFormatter dateFormat = DateTimeFormatter.ofPattern("yyyy.MM.dd");
        LocalDate todayDate = LocalDate.parse(today, dateFormat);

        Map<String, Integer> termsMap = new HashMap<>();

        for (String term : terms) {
            String[] termSplit = term.split(" ");
            termsMap.put(termSplit[0], Integer.valueOf(termSplit[1]));
        }
        List<Integer> toBeDeleted = new ArrayList<>();

        for (int i = 0; i < privacies.length; i++) {

            String[] privacySplit = privacies[i].split(" ");
            LocalDate privacyInformationDate = LocalDate.parse(privacySplit[0], dateFormat);
            Integer expirationMonth = termsMap.get(privacySplit[1]);

            LocalDate destructionDate = privacyInformationDate.plusMonths(expirationMonth);

            if (!destructionDate.isAfter(todayDate)) {
                toBeDeleted.add(i + 1);
            }
        }

        return toBeDeleted;
    }
}

• 이번에 문제 접근은 날짜를 직접 계산하기에는 번거로울 수 있다는 생각에 날짜 라이브러리를 사용하고, 약관 종류와 유효기간을 Map으로 관리하여 문제를 해결해야겠다고 생각했다.
  • 사실 문제를 다 풀고 28일로 모든 월의 일자가 고정되어있다는 문구를 보아서 실제로 원하는 계산은 날짜 계산을 하는 알고리즘을 구현하라는 문제인듯 싶다.
• 우선 나는 termsMap을 채우기 위해 terms를 반복문으로 요소를 꺼내서 split(" ") 으로 구분한 다음 key는 분리된 첫 번째 요소를, value는 분리된 두 번째 요소를 Integer로 변환한 값으로 Map에 저장시켰다.
• 그 다음 보관된 개인정보 배열에서 똑같이 반복문과 split(" ")으로 구분해주어서 날짜와 약관 종류를 구분지었다
• 여기서 날짜 라이브러리를 사용했기 때문에 String으로 구분된 날짜를 LocalDate로 바꿔야 했는데 DateTimeFormatter.ofPattern() 메서드를 통해 문자열 형식으로 구성된 날짜를 포맷팅하는 포맷터를 만들고 LocalDate.parse(문자열 날짜, 형식)을 통해서 날짜를 변환시켰다.
• split(" ")으로 구분한 첫 번째 요소는 개인정보가 수집된 날짜이므로 위의 로직을 활용하여 LocalDate로 변환시키고, 두 번째 요소는 약관 종류이기 때문에 termsMap.get()을 통해 약관 종류의 보관 기간을 꺼낸다.
• 그 다음 변환된 개인정보의 날짜의 월과 termsMap.get()으로 꺼낸 보관 기간을 더해서 개인정보를 파기해야할 날짜를 구한다음, 해당 날짜가 오늘 날짜보다 크지 않다면(오늘 날짜가 파기해야할 날짜와 같거나 크다면) 파기해야할 데이터로 분류한다.
• 미리 파기해야할 개인정보의 번호를 담아야할 List<Integer> toBeDeleted = new ArrayList<>()에 i + 1을 추가하여 파기해야할 개인정보를 담고 반환시킨다
  • 여기에서도 사실 int[]로 반환하라고 했는데 프로그래머스에서는 반환타입을 바꿔도 통과가 된다.
  • 만약 실제 문제였다면 toBeDeleted.stream().mapToInt(Integer.intValue).toArray()를 통해서 int[]로 반환하는것이 맞다고 생각한다.

최적화  풀이

문제에서 제시된 요구사항을 모두 반영하고 최적화한 풀이

import java.util.*;

class Solution {
    public int[] solution(String today, String[] terms, String[] privacies) {
        Map<String, Integer> termMap = new HashMap<>();
        for (String term : terms) {
            String[] split = term.split(" ");
            termMap.put(split[0], Integer.parseInt(split[1]));
        }

        int todayDays = convertToDays(today);
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < privacies.length; i++) {
            String[] split = privacies[i].split(" ");
            String date = split[0];
            String termType = split[1];

            int startDays = convertToDays(date);
            int expireDays = startDays + termMap.get(termType) * 28;

            if (expireDays <= todayDays) {
                result.add(i + 1);
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    private int convertToDays(String date) {
        String[] split = date.split("\\.");
        int year = Integer.parseInt(split[0]);
        int month = Integer.parseInt(split[1]);
        int day = Integer.parseInt(split[2]);

        return year * 12 * 28 + month * 28 + day;
    }
}

• Map을 활용하여 약관 종류와 기간을 관리하는 방식은 같지만 날짜를 구하는 방식을 별도의 메서드로 추출하여 구한다.
• convertToDays() 메서드를 보면 문자열인 date를 입력 받아서 이를 .으로 구분하여 년,월,일로 모두 구분해주고, 요구사항에 모든 일자가 28일로 가정했기 때문에 일자를 구한다
  • year * 12 * 28 = 주어진 날짜의 년도를 일로 환산
  • month * 28 = 주어진 월을 일로 환산
• 이 메서드를 통해 오늘 날짜을 일로 환산한 todayDays와 개인정보를 수집한일자인 startDays + 맵에서 꺼낸 기간을 일로 환산한 값을 비교하여 오늘 일짜가 크거나 같으면 똑같이 개인정보의 번호를 List에 추가한다.
• 이후 int[]로 반환하라는 요구사항을 지키기 위해 stream().mapToInt().toArray()를 활용하여 반환하면 된다.

---

달리기 경주

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/178871
• 달리기 경주에서 해설진들이 선수들이 본인 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부름
• 예를 들어 1등 부터 3등 까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월하여 "soe" 선수가 1등 "mumu" 선수가 2등으로 바뀜
• 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 담아 return 하는 함수를 완성

제한조건

• 5 <= players의 길이 <= 50,000
  • players[i]는 i번째 선수의 이름을 의미함
  • players의 원소들은 알파벳 소문자로만 이루어져있으며 중복된 값이 들어있지 않음
  • 3 <= players[i]의 길이 <= 10
• 2 <= callings 의 길이 <= 1,000,000
  • callings는 players의 원소들로만 이루어져 있으며 경주 진행중인 1등인 선수의 이름을 불리지 않음

입출력 예시

나의 풀이

import java.util.Map;
import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        
        Map<String, Integer> nameToIndex = new HashMap<>();
        
        for (int i = 0; i < players.length; i++) {     
            nameToIndex.put(players[i], i);
        }
        
        for (int i = 0; i < callings.length; i++) {
            int callRank = nameToIndex.get(callings[i]);
            String frontPlayer = players[callRank - 1];
            
            players[callRank - 1] = callings[i];
            players[callRank] = frontPlayer;
            
            nameToIndex.put(callings[i], callRank - 1);
            nameToIndex.put(frontPlayer, callRank);
        
        }
        
        return players;
    }
}

• 사실 이 문제를 처음 접근했을 때에는 단순하게 2중 반복문으로 문제를 푼 다음, callings의 요소를 꺼내서 players의 인덱스 위치를 한칸씩 당기는 방식으로 문제를 접근했었다.
• 그러나 문제는 풀리지만 일부 케이스에서 시간초과가 발생하여 이 문제는 단순하게 푸는게아니라 자료구조를 활용해야하는 문제라는 직감이 들었다.
• 그래서 자료구조 중에서 특정 대상을 바로 접근할 수 있는 Map을 활용해야하는 것이 포인트이지 않을까 생각하여 접근을 시도해봤는데, 처음 시도는 callings의 값들을 Map으로 만들어서 해당 요소가 몇번 불렸는지를 저장하고 이를 통해 players의 index위치를 바꾸려고했었다.
• 그러나 이렇게 하게 되면 배열인 players에서 Map의 값만큼 당기고 다른 요소를 자리를 바꾸는 등의 더 불필요한 작업이 점점 증가되어 뭔가 잘못 접근했다는 것을 깨달았다.
• 결국 고민하다가 시간 초과를 하여 풀이를 찾아본 결과 callings가 아니라 현재 players의 순위를 Map으로 기록하고 callings의 요소로 순위를 변경하는 방식이 있어 풀이를 가져왔다.
• 먼저 Map을 선언해준 다음 반복문으로 palyers의 요소를 Map의 키로, index(순위)를 값으로 저장해준다.
• 그 다음 반복문을 통해 callings의 요소를 하나씩 꺼내서 Map.get()으로 값을 꺼내 callings의 요소가 현재 몇등인지 index를 꺼내고, 해당 플레이어의 바로 앞선수가 누구인지 players[callRank - 1]로 찾아낸다
• 그 다음 이 두 선수의 위치를 바꾸고, Map에도 현재 등수를 갱신하여 callings의 요소를 꺼낼 때 마다 순위를 갱신할 수 있다.
• 이렇게 하게 되면 2중 반복문을 사용하지 않기 때문에 요소가 많아질 수록 시간이 제곱으로 늘어나는 문제도 방지할 수 있게 되고 Map으로 변환하는 반복문과 순위를 갱신하는 반복문 이렇게 단일 반복문 2개로 문제를 해결할 수 있게된다
• 특히 Map을 활용했기 때문에 특정 대상의 요소를 꺼내고 다시 삽입하는데 O(1)의 성능을 보여 배열과 순차 리스트의 단점을 해결할 수 있게 된다

---

공원 산책

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/172928
• 지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 미리 입력된 명령에 따라 산책을 하려고 함
• 명령은 아래와 같은 형식으로 주어짐
  • ["방향 거리", "방향 거리" ,... ]
• 예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미로 로봇강아지는 명령을 수행하기 전에 아래 두 가지를 먼저 확인함
  
  • 주어진 방향으로 이동할 때 공원을 벗어나는지 확인함
  • 주어진 방향으로 이동 중 장애물을 만나는지 확인한
• 위 두 가지중 어느 하나라도 해당된다면 로봇 강아지는 해당 명려을 무시하고 다음 명령을 수행함
• 공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H-1, W-1)임
• 공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하는 함수를 완성

제한조건

• 3 <= park의 길이 <= 50
  • 3 <= park[i]의 길이 <= 50
  • park는 직사각형의 모양이며 park[i]는 아래의 문자들로 이루어져 있으며 시작지점은 하나만 주어짐
    • S: 시작 지점
    • O: 이동 가능한 통로
    • X: 장애물
• 1 <= routes의 길이 <= 50
  • routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타내며 routes의 첫 번째 원소부터 순서대로 명령을 수행함
  • routes는 "op n"과 같은 구조로 이루어져 있으며 op는 이동할 방향, n은 이동할 칸의 수를 의미함
  • 1 <= n <= 9
  • op의 종류
    • N: 북쪽으로 주어진 칸 만큼 이동
    • S: 남쪽으로 주어진 칸 만큼 이동
    • W: 서쪽으로 주어진 칸 만큼 이동
    • E: 동쪽으로 주어진 칸 만큼 이동

입출력 예시

풀이

배열만 활용

class Solution {
    public int[] solution(String[] park, String[] routes) {
        int[] robotIndex = new int[2];
        for (int i = 0; i < park.length; i++) {
            if (park[i].contains("S")) {
                int index = park[i].indexOf("S");
                robotIndex[0] = i;
                robotIndex[1] = index;
                break;
            }
        }
        for (int j = 0; j < routes.length; j++) {
            String[] splitRoute = routes[j].split(" ");
            String direction = splitRoute[0];
            int move = Integer.valueOf(splitRoute[1]);

            int dx = 0;
            int dy = 0;

            switch (direction) {
                case "E": dx = 1; break;
                case "W": dx = -1; break;
                case "S": dy = 1; break;
                case "N": dy = -1; break;    
            }

            int ny = robotIndex[0];
            int nx = robotIndex[1];
            boolean isBlocked = false;

            for (int step = 0; step < move; step++) {
                ny += dy;
                nx += dx;

                if (ny < 0 || ny >= park.length || nx < 0 || nx >= park[0].length()) {
                    isBlocked = true;
                    break;
                }

                if (park[ny].charAt(nx) == 'X') {
                    isBlocked = true;
                    break;
                }
            }
            if (!isBlocked) {
                robotIndex[0] = ny;
                robotIndex[1] = nx;
            }
        }
        return robotIndex;
    }
}

 

로봇 위치 구하기

• 먼저 로봇의 시작 위치를 구하기 위해 park를 반복문으로 각 요소에대해 "S"가 있는지 검사하여 반복한 값은 x좌표값, indexOf("S")의 값은 y좌표값으로 꺼내서 int[] robotIndex에 저장했다
• 이때 로봇 위치가 정해지면 불필요한 연산은 하지않도록 break;로 반복을 빠져나온다

이동하기

• 그 다음 구해진 위치의 로봇을 routes에 입력된 명령어로 이동시키기 위해서는 어떤 방향으로 몇 칸을 가야하는지 확인해야 하므로 반반복문으로 routes의 요소를 split(" ")으로 분해한다
• split한 요소의 첫 번째는 방향, 두 번째는 이동할 칸으로 각각 저장하고 switch 문으로 각 지시한 방향에 따라 로봇이 이동해야할 방향으로 연산이 되도록 작성해둔다
• 지도를 벗어나거나 벽을 만났을 경우 나타내주는 isBlocked를 false로 선언하여 로봇을 이동시킬 준비를 한다
• 이제 한 번더 반복문으로 이동할 칸 만큼 반복할 때마다 로봇의 좌표에 switch 문을 거친 값이 누적 연산되도록 하여 로봇이 이동하도록 한다
• 이 때 조건문으로 맵을 벗어나거나 'X'를 만나게 된다면 위치를 저장하지 않고 반복문을 종료하여 해당 명령은 무시하고 다음 routes의 요소를 꺼내서 반복한다
• 이렇게 'X'를 만나지 않거나 맵 밖으로 벗어나지 않는 명령만 수행하여 최종적으로 로봇이 이동한 좌표의 위치를 갱신하여 문제를 해결한다

풀이

map 활용

import java.util.*;

class Solution {
    public int[] solution(String[] park, String[] routes) {
        int height = park.length;
        int width = park[0].length();

        int y = 0, x = 0;

        for (int i = 0; i < height; i++) {
            int idx = park[i].indexOf('S');
            if (idx != -1) {
                y = i;
                x = idx;
                break;
            }
        }

        Map<String, int[]> directions = Map.of(
            "N", new int[]{-1, 0},
            "S", new int[]{1, 0},
            "W", new int[]{0, -1},
            "E", new int[]{0, 1}
        );

        for (String route : routes) {
            String[] parts = route.split(" ");
            String dir = parts[0];
            int dist = Integer.parseInt(parts[1]);

            int[] d = directions.get(dir);
            int ny = y;
            int nx = x;

            boolean isBlocked = false;

            for (int i = 0; i < dist; i++) {
                ny += d[0];
                nx += d[1];

                if (ny < 0 || ny >= height || nx < 0 || nx >= width || park[ny].charAt(nx) == 'X') {
                    isBlocked = true;
                    break;
                }
            }

            if (!isBlocked) {
                y = ny;
                x = nx;
            }
        }

        return new int[]{y, x};
    }
}

• map 자료 구조를 활용한 풀이도 있어서 가져와보았다
• 접근 방식은 똑같지만 switch문을 map 자료구조로 표현하면서 가독성과 확장성을 높이는 방법이라고 보면 될 것같다.