써니리 초보 개발자 블로그

문제 설명

풀이

이 문제를 풀이는 2개의 방법이 있다

1. 비교하는 문자를 앞뒤로 바꿔서 더 큰수를 만들 수 있는 순서대로 분류 시키는 방법 

ex) 6, 2 ,10에서 62 26를 비교, 210 102 비교, 더 큰 수를 만들 수 있는 순서대로 sorting

2. 각각의 요소를 4자리 수로 만들고, 이를 내림차순으로 sorting 

ex) 6,2,10에서 6666, 2222, 1010 을 만들고 이 수의 크기를 비교해 각각의 요소를 내림차순으로 sorting

여기서 주의할 점은 모든 요소가 0일때 0을 요소갯수만큼 붙인 문자열이 아닌 "0"으로 리턴해야 한다는 점이다.

나는 1번 풀이법으로 풀어보았다.

문제

문제 설명

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

---

입출력 예시rowscolumnsqueriesresult

6	6	[[2,2,5,4],[3,3,6,6],[5,1,6,3]]	[8, 10, 25]
3	3	[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]	[1, 1, 5, 3]
100	97	[[1,1,100,97]]	[1]

---

입출력 예 설명

입출력 예 #1

• 회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

• 

입출력 예 #2

• 회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

• 

입출력 예 #3

• 이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.

풀이

function solution(rows, columns, queries) {
    var answer = [];
    let graph = [];
    let temp = [];
    for(let i = 0; i < rows * columns; i++){
        temp.push(i+1)
        if(temp.length == columns){
            graph.push(temp)
            temp = []; //초기화
        }
    }
    
   
    queries.forEach((item) =>{
        let [x1,y1,x2,y2] = item.map((value) => { return value - 1})
        
        let newGraph = [] //빈배열
        
        //1. 일단 1차원으로 해당 숫자들을 펴보자
        for(let i = y1; i < y2; i++){  
            newGraph.push(graph[x1][i])
        }
        for(let i = x1; i < x2; i++){
            newGraph.push(graph[i][y2])
        }
        
        for(let i = y2;  i > y1; i--){
            newGraph.push(graph[x2][i])
        }
        for(let i = x2; i > x1; i--){
            newGraph.push(graph[i][y1])
        }
        
        //2. 한칸씩 이동시키려면 맨뒤에 숫자를 맨 앞으로 보내면 된다.
        newGraph.unshift(newGraph.pop())
        
        //3. 그중에서 가장 작은 값을 배열에 넣어보자
        let min = Math.min(...newGraph)
        answer.push(min)
        //3. 그 배열들을 다시 graph에 넣어주자
        for(let i = y1; i < y2; i++){
            graph[x1][i] = newGraph.shift()
        }
        
        for(let i = x1; i < x2; i++){
            graph[i][y2] = newGraph.shift()
        }
        
        for(let i = y2; i > y1; i--){
            graph[x2][i] = newGraph.shift()
        }
        
        for(let i = x2; i > x1; i--){
            graph[i][y1] = newGraph.shift()
        }
        
        
    }) 
   
    
    return answer
}

2차원 배열을 직접 하나씩 옮기는 방식으로 풀려니 도저히 안풀렸는데,

1차원 배열로 맨 뒤 값을 맨 앞으로 옮겨주는 것 만으로 시계방향으로 이동이 가능하다는걸 알고나서

그 점이 완전 유레카였다는 것을.. 깨달음

잊지말자 **

그리고 array.map, array.filter 등 메서드 사용법 헷갈리지않기.

탐색 이란?

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.

스택 자료구조

먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.

입구와 출구가 동일한 형태로 스택을 시각화 할 수 있고, 박스를 아래에서부터 위로 차례대로 쌓고 위부터 아래로 내려놓는 방식의 박스쌓기를 생각하면 이해하기 쉽다.

DFS알고리즘에서 자주 쓰인다.

큐 자료구조

먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.

양끝이 입구와 출구로 나뉘어져있다.

BFS알고리즘에서 자주 쓰인다.

재귀함수

자기자신을 다시 호출하는 함수를 의미한다.

재귀함수를 무한히 호출하면 컴퓨터 메모리를 초과하기때문에 종료조건을 반드시 명시해야한다.

DFS, BFS알고리즘에서 자주 쓰이는 방식이다.

DFS

깊이우선탐색 알고리즘으로 주로 스택을 이용하여 구현한다.

트리나 그래프에서 한 루트에서 최대한 깊숙히 들어가서 탐색하다가 인접 노드가 모두 방문되었으면 다시 돌아가 다른 루트로 탐색한다.

컴퓨터는 기본적으로 stack구조를 취하기 때문에 재귀함수로 dfs를 실행할 경우 제일 나중에 실행된 재귀함수가 가장 먼저 종료된다. 그리고 가장 처음에 호출 되었던 함수가 가장 나중에 종료되고 재귀를 최종으로 마치게된다.

BFS

넓이우선탐색 알고리즘으로 큐 자료구조를 이용하여 구현하는게 일반적이다.

그래프나 트리에서 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.

더이상 그 과정을 수행할 수 없을 때까지 반복한다.

BFS는 최단 거리를 구하는 문제에서 자주 쓰인다.

그림 출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

DFS/BFS 무료 강의 

https://www.youtube.com/watch?v=7C9RgOcvkvo 

문제

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progressesspeedsreturn

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다. 

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

※ 공지 - 2020년 7월 14일 테스트케이스가 추가되었습니다.

풀이

function solution(progresses, speeds) {
    var answer = [];
    //1. 남은 작업량 구하기
    //2. 며칠 걸리는지 계산해서 배열에 넣기
    let leftDays = progresses.reduce(function(acc, item, index ,arr){
         // return acc.concat(100 - item)
        return acc.concat(Math.ceil((100 - item)/speeds[index]))
    }, []);
    
    
    let count = 1;
    let max = 0;
    while(leftDays.length > 0){
       max = Math.max(leftDays.shift(), max) //하나씩 꺼내서 비교함.
        if(max >= leftDays[0]){
            count++;
        }else{
            answer.push(count)
            count = 1;
        }
    }
    
    return answer;
}

문제

function solution(n) {
    let answer = ""
    let numObj = [4, 1, 2]
    
    while(n){ //n이 0 이상일때 까지
        answer = numObj[n % 3] + answer
        n = Math.floor((n-1) /3)
    }

   
    return answer.toString();
}

n-1이 중요한 키포인트이다.

쭉 숫자를 적어보고 규칙을 찾아보면 3의배수의 +1 값마다 앞자리 숫자가 변한다. 

문제

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

"[닉네임]님이 들어왔습니다."

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

"[닉네임]님이 나갔습니다."

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

• 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
• 채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 "Muzi"와 "Prodo"라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

"Muzi님이 들어왔습니다."
"Prodo님이 들어왔습니다."

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

"Muzi님이 들어왔습니다."
"Prodo님이 들어왔습니다."
"Muzi님이 나갔습니다."

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."
"Prodo님이 들어왔습니다."
"Prodo님이 나갔습니다."
"Prodo님이 들어왔습니다."

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."
"Ryan님이 들어왔습니다."
"Prodo님이 나갔습니다."
"Prodo님이 들어왔습니다."

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

• record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
• 다음은 record에 담긴 문자열에 대한 설명이다.
  • 모든 유저는 [유저 아이디]로 구분한다.
  • [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - "Enter [유저 아이디] [닉네임]" (ex. "Enter uid1234 Muzi")
  • [유저 아이디] 사용자가 채팅방에서 퇴장 - "Leave [유저 아이디]" (ex. "Leave uid1234")
  • [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - "Change [유저 아이디] [닉네임]" (ex. "Change uid1234 Muzi")
  • 첫 단어는 Enter, Leave, Change 중 하나이다.
  • 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
  • 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
  • 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
  • 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

입출력 예

recordresult

입출력 예 설명

입출력 예 #1
문제의 설명과 같다.

풀이

function solution(record) {
    let tempList = [];
    let answer = [];
    let userInfo = {}
    record.forEach((item) =>{
       let list = item.split(" ")
        tempList.push(list)
        if(list[2]){
            userInfo[list[1]] = list[2]
        }
    })

    
    tempList.forEach((item) => {
        if(item[0] === "Enter"){
            answer.push(`${userInfo[item[1]]}님이 들어왔습니다.`)
        }else if(item[0] === "Leave"){
            answer.push(`${userInfo[item[1]]}님이 나갔습니다.`)
        }
    })
    
    
    return answer
}

uuid로 유저를 저장하기 위해서 userInfo 라는 객체를 생성하고, for문 안에서 uuid에 해당하는 이름을 갱신하는게 포인트다.

처음엔 Leave 일시, split으로 나눴던 배열 안의 index 2번 값이 비어있는걸 고려하지 않아 오류가 났다.

if문으로 비어있는지 아닌지 체크를 해야한다. 비어있지 않을때 userInfo의 uuid의 이름을 갱신해야한다.

문제

문제 설명

문제

풀이

function solution(s) {
    var answer = '';
    
    if((s.length % 2) == 1){
        //2로 나누면 1이 생김
        answer = s[((s.length + 1)/2) - 1]
    }else{
        //나누어 떨어짐
        answer = s[s.length/2 - 1] + s[s.length / 2]
        console.log(s[s.length - 1] )
    }
    return answer;
}

문제

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

매개변수값

매개변수값

풀이

function solution(n, arr1, arr2) {
    var answer = [];
    var firstList = makeList(n,arr1);
    var secondList = makeList(n,arr2);
    
    for(let i = 0 ; i < n ; i++){
        let tempList = "";
        for(let j = 0; j < n; j++) {
            if((firstList[i][j] + secondList[i][j]) >= 1){
                tempList += '#'
            }else{
                tempList += ' '
            }
        }
         answer.push(tempList)
    }
    return answer;
}

function makeList(n, arr){
    var list = []; 
    for(let i = 0; i < arr.length; i++){
            var innerList = [];
            var num = arr[i]
            
            while(num > 0){
                innerList.unshift(num % 2)
                num = parseInt(num / 2)
            }
     
        while(innerList.length < n){
            innerList.unshift(0)
        }   
        list.push(innerList)
        
    }
    return list
}

makeList 라는 메서드를 사용하여 각각 이진법 리스트를 생성하여 해결하였다.

이중에서 눈여겨 봐야할 것은 push 대신에 unshift를 사용해야 한다는 점이다! (push는 나중에 계산된 값이 array 끝으로 가기 때문에) **

unshift까먹지말자!

문제 설명