[프로그래머스] 20 : 달리기 경주 | 공원 산책

서예진·2024년 2월 5일
0

목차

▸ 달리기 경주
▸ 공원 산책


💡달리기 경주 : Lv.1

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 연습문제 > 달리기 경주

▼ 내 풀이

  • 우선, players 배열의 요소들의 위치를 바꿔야하므로 쉽게 하기 위해 리스트로 변환했다.
  • callings 배열기준으로 for 반복문을 실행한다.
  • callings 배열을 돌면서 각 요소의 index를 가져오고 index-1의 요소를 temp로 저장한 후, 두 요소를 서로 바꾼다.
[시간 초과 코드]
import java.util.List;
import java.util.Arrays;

class Solution {
    public List<String> solution(String[] players, String[] callings) {

        List<String> playersList = Arrays.asList(players);
        
        for(String calling : callings){
            int indx = playersList.indexOf(calling);
            String temp = playersList.get(indx-1);
            playersList.set(indx-1, calling);
            playersList.set(indx, temp);
        }
        
        return playersList;
    }
}
  • 시간초과가 떴다. 여기서 indexOf 메서드가 리스트를 처음부터 끝까지 순회하기 때문에 최악의 경우 O(n)의 시간이 소요되는 메서드였다.
  • 따라서 인덱스를 가져올 리스트 따로 직접적으로 요소의 순서를 고려하여 저장하는 맵 따로해서 접근했다.
[수정 코드]
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;


class Solution {
    public List<String> solution(String[] players, String[] callings) {
        List<String> playersList = Arrays.asList(players);
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < players.length; i++) {
            map.put(players[i], i);
        }
        
        for(String calling : callings){
            int indx = map.get(calling);
            String temp = playersList.get(indx-1);
            playersList.set(indx-1, calling);
            playersList.set(indx, temp);
            map.put(calling, indx-1);
            map.put(temp, indx);
        }
        List<Map.Entry<String, Integer>> entrys = new ArrayList<>(map.entrySet());
        entrys.sort(Map.Entry.comparingByValue());

        List<String> answer = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : entrys) {
            answer.add(entry.getKey());
        }
        return answer;
    }
}

❗️맵의 값들을 기준으로 정렬하는 부분에서 찾아보면서 하느라 시간이 걸렸다.


💡공원 산책 : Lv.1

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 연습문제 > 공원 산책

▼ 내 풀이

  • 우선, 2차원 배열로 접근하고자 했다.
  • if-else문을 활용하여 동서남북 케이스를 나누었다.
  • 배열을 벗어나는 부분과 장애물을 만나는 부분을 if문을 걸어서 처리를 했다.
class Solution {
    public int[] solution(String[] park, String[] routes) {
        
        //초기 2차원 배열 세팅
        char[][] array = new char[park.length][];
        for (int i = 0; i < array.length; i++){
            array[i] = park[i].toCharArray();
        }
        
        //초기 위치
        int Sx = 0;
        int Sy = 0;
        for(int i = 0; i < array.length; i++){
            for(int j = 0 ; j < array[0].length; j++){
                if(array[i][j] == 'S'){
                    Sy = i;
                    Sx = j;
                    break;
                }
            }
        }
        
        //routes
        for(int i = 0; i < routes.length; i++){
            String[] route = routes[i].split(" ");
            int direct = Integer.parseInt(route[1]);
            boolean check = true;
            if(route[0].equals("E")){
                if(Sx + direct < array[0].length){
                    for(int j = Sx; j <= Sx+direct; j++){
                        if(array[Sy][j] == 'X'){
                            check = false;
                            break;
                        }
                    }
                    if(check){
                        Sx += direct;
                    }
                }
            }else if(route[0].equals("W")){
                if(Sx - direct >= 0){
                    for(int j = Sx; j >= Sx-direct; j--){
                        
                        if(array[Sy][j] == 'X'){
                            check = false;
                            break;
                        }
                    }
                    if(check){
                        Sx -= direct;
                    }
                }
            }else if(route[0].equals("N")){
                if(Sy - direct >= 0){
                    for(int j = Sy; j >= Sy-direct; j--){
                        
                        if(array[j][Sx] == 'X'){
                            check = false;
                            break;
                        }
                    }
                    if(check){
                        Sy -= direct;
                    }
                }
            }else if(route[0].equals("S")){
                if(Sy + direct < array.length){
                    for(int j = Sy; j <= Sy+direct; j++){
                        
                        if(array[j][Sx] == 'X'){
                            check = false;
                            break;
                        }
                    }
                    if(check){
                        Sy += direct;
                    }
                }
            }
        }
        
        
        int[] answer = new int[2];
        answer[0] = Sy;
        answer[1] = Sx;
        return answer;
    }
}
profile
안녕하세요

0개의 댓글