써니리 초보 개발자 블로그

문제 설명

풀이

이 문제를 풀이는 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번 풀이법으로 풀어보았다.

Map ?

es6에 추가된 자료형으로 Object와 비슷하지만 크게 다른점으로는

1. 순서가 있음

2 iterable 함

3. key값에 string값이 아닌 다른 타입이 들어갈 수 있음

4. 크기를 쉽게 알 수 있음

이렇게 있습니다.

그럼 위와 같은 Map이 주는 장점들로 인해 항상 Object보단 Map을 사용하는것이 좋을까요?

그렇지는 않습니다.

Object는 데이터를 저장하기 위한 굉장히 간단한 구조입니다. 그렇기 때문에 key값이 string인 간단한 데이터를 저장하기 위해서는 생성이 굉장히 쉽습니다. 또한 JSON으로 데이터를 어딘가에 전송해야 할 경우에는 Object를 사용해야합니다. Map은 아직 JSON으로 변환 되어 전달되지 않기 때문입니다.

그러나 Map은 Hash구조로 Object보다 순환이 빠르기 때문에 데이터를 추가하거나 수정하는 것이 빈번 할 경우 Map을 쓰는것이 좋습니다.

Map의 사용

map은 생성자를 이용하여 생성합니다.

const wrongMap = new Map()

set(key, value) 메서드를 이용하여 데이터를 set하고, has 메서드로 입력한 key에 해당하는 데이터 보유 유무를 확인합ㄴ디ㅏ. 또한 get 메서드를 이용하여 입력한 key에 대한 value를 얻을 수도 있습니다.

contacts.set('Jessie', {phone: "213-555-1234", address: "123 N 1st Ave"})
contacts.has('Jessie') // true
contacts.get('Hilary') // undefined

delete메서드를 이용하여 입력한 key에 해당하는 데이터를 지울수도 있으며 

size메서드로 map의 크기도 알 수 있습니다.

contacts.delete('Raymond') // false

Set과 마찬가지로 Map은 Map이외에 WeakMap이라는 자료형도 있습니다.

이 자료형은 마찬가지로 iterable 하지 않으며, 참조카운팅을 추가 하지도 않습니다.

WeakMap은 WeakSet과 달리 사용성이 좋은걸로 알고있으나.. 저는 사용해본적이 없어 사용할 일이 생긴다면 사용해보고 정리하여 따로 포스팅 하겠습니다.

Set 이란?

es6 에서 추가된 자료형으로

1. 배열의 중복을 제거 하고 싶을 때

2. 자료전체를 순회할 필요성이 있을 경우

3. 값의 유무를 판단 할 때

유용하게 쓸 수 있습니다.

1 번의 경우 Set의 중복된 값을 허용하지 않는다는 속성을 이용한 것이고

2,3 번의 경우 Set은 순회를 더 빨리 돈다는 점에서 유용하게 쓰입니다.

특히 저는 코딩테스트에서 중복제거를 위해 자주 사용하곤 합니다.

Set의 사용

set은 아래와 같이 생성 할 수 있으며, 생성자 안에는 iterable 한 객체들이 들어갈 수 있습니다. ex) Array

var mySet = new Set();

mySet2 = new Set([1, 2, 3, 4]);

set은 array의 push 처럼 add를 이용하여 값을 추가 할 수 있고, 중복을 허용하지 않습니다.

mySet.add(1); // Set { 1 }
mySet.add(5); // Set { 1, 5 }
mySet.add(5); // Set { 1, 5 }

set은 has 메서드를 이용하여 해당 값이 set에 포함되어 있는지의 여부를 확인할 수 있습니다. 

mySet.has(1); // true
mySet.has(3); // false, 3은 set에 추가되지 않았음
mySet.has(5);              // true

set의 size 메서드는 set의 크기를 반환하며, delete메서드를 이용하여 해당 요소를 제거할 수 있습니다.

mySet.size; // 5

mySet.delete(5); // set에서 5를 제거함

array를 set의 생성자 안에 넣어 set으로 변경할 수도 있지만, set을 array로 변경할 수도 있습니다.

// set을 Array로 변환하기 위해 전개 연산자 사용함.
console.log([...mySet]); // myArray와 정확히 같은 배열을 보여줌

이는 set은 iterable하기 때문에 spread연산자를 사용할 수 있어 가능합니다.

이 외로 WeakSet이라는 자료형도 존재합니다. 이는 set과 비슷하나 iterable하지 않고, 참조카운트를 증가시키기 않는 자료형입니다. iterable하지 않기때문에 안에 속성들을 순회하거나 탐색할 수 없습니다. 

WeakSet은 활용도가 미미하기 때문에 따로 다루지는 않습니다.

WeakSet의 활용도가 미미하기 때문인지 혹자들은 WeakMap과 통일성을 위해 만들어졌다고도 합니다..

문제

문제 설명

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 

문제

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의 이름을 갱신해야한다.

문제

문제 설명

문제

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

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까먹지말자!

문제 설명