[코딩 테스트 합격자 되기]이중반복문, while문, enumerate() 활용

고래강이 2024. 12. 29. 17:29

☄️ 문제 접근 및 내 생각

1. 서로 다른 두 인덱스를 구해서 더해야하는 문제이기에 O(N^2)의 시간복잡도를 가진 이중반복문을 떠올렸으며, 이후 중복제거 및 정렬을 위해서 set()이용해서 중복을 제거하였다.
2. 이중반복문을 통해서 원하는 값을 뽑아내서 더하여 배열에 없을 때는 추가하고 아닐 때에는 아무것도 하지 않도록 구상하였다.

소요시간: 30분

🌈 파이썬 코드

# 초기 완성 코드
def solution(numbers):
    result = []
    new_numbers = list(set(numbers))
    for i in range(len(new_numbers)):
        for j in range(i + 1, len(new_numbers)):
            sum = new_numbers[i] + new_numbers[j]
            if sum not in result:
                result.append(sum)
    return result
print(solution([1, 2, 3, 4, 5]))

# 오름차순 보장 후 변경된 코드
def solution(numbers):
    result = []
    new_numbers = sorted(set(numbers))
    for i in range(len(new_numbers)):
        for j in range(i + 1, len(new_numbers)):
            sum = new_numbers[i] + new_numbers[j]
            if sum not in result:
                result.append(sum)
    return result
print(solution([1, 2, 3, 4, 5]))

기본적으로 O(n^2)의 시간복잡도를 나타내는 데 줄일 수는 없나? - ChatGPT 답변으로 안된단다.
sorted()를 사용하는 부분도 없는데 왜 정렬이 되서 나올까?
- 우연히 오름차순으로 정렬되는 것이지 보장되지 않는다고 한다. - ChatGPT 답변
- sorted()를 통해서 list() 사용하지 않아도 반환되는 값이 리스트이다. - ChatGPT 답변

🌈 자바스크립트 코드

// 초기 답안
function solution(lst) {
  let result = [];
  const new_list = [...new Set(lst)].sort((a, b) => a - b); // Set으로 중복 제거 및 오름차순
  const length = new_list.length;
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      const sum = new_list[i] + new_list[j];
      if (!result.includes(sum)) {
        result.push(sum);
      }
    }
  }
  return result;
}

console.log(solution([1, 2, 3, 4, 5, 1, 2, 3, 4]));

sort()의 경우 문자열시 사용되므로 오름차순으로 숫자를 이용한 경우에는 비교 구문을 추가로 넣어줘야 함
includes를 in과 같이 사용할 수 있다.
- 흠.. in이 좀 더 편하군

☄️ 문제 접근 및 내 생각

1. 각 수포자별 어떤 패턴을 해결하는 지 각각의 함수로 만들어서 각각의 결과를 비교해보자고 생각을 하다 2, 3번 패턴에 대해서 수식을 만들기 힘들다 생각되어 각자 가진 패턴을 문자열로 뽑아서 이를 통해서 정답 배열과 비교하는 방식으로 변경
2. 정답 배열이 최대 10,000 문제이므로 range를 통해서 반복시키는 것보다 while을 사용해보자고 생각이 들었다. 또한 정답이 항상 패턴의 length 크기와 일정하게 떨어지지 않으므로 이에 대해서 while을 사용해서 구현해보자 생각이 들었음
3. 각 index별 비교 후 pop을 해서 배열의 크기를 줄이면 pop자체가 무겁다는 생각이 들어서 index, count를 통해서 배열을 조회하는 식으로만 구현하고자 함

소요시간: 1시간
비교하는 구문을 작성하고 while문이 제때 멈추게끔 하는 부분에서 시간이 좀 걸렸다.

🌈 파이썬 코드

mock_answer = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
patterns = ['12345', '21232425', '3311224455']
def solution(answer, str):
    str_lst = [int(x) for x in str]
    str_len = len(str_lst)
    index = 0
    count = 0
    result = 0
    while len(answer) > (str_len * count) + index:
        if (index + 1 > len(str_lst)):
            index = 0
            count += 1
        if str_lst[index] == answer[(str_len * count) + index]:
            result += 1
        index += 1
    return result

results = [solution(mock_answer, x) for x in patterns]
max = max(results)
indices = [index + 1 for index, value in enumerate(results) if value == max]
print(indices)

기본적으로 O(N)의 시간복잡도를 나타내므로 개선할 필요는 없어보임
리스트 컴프리헨션을 통해 좀 더 단축된 코드 구현
indices 이부분은 컴프리헨션과 enumerate()를 활용해서 좀 더 복잡해진 코드지만 그래도 이해할 수 있어서 다행이다.

# 더 나은 답변
answers = [1, 2, 3, 4, 5]
patterns = [
    [1, 2, 3, 4, 5],
    [1, 2, 1, 2,]
]
scores = [0] * 3
for i, answer in enumerate(answers):
    for j, pattern in enumerate(patterns):
        if answer == pattern[i % len(pattern)]:
            scores[j] += 1

좀 더 간단하게 enumerate()를 활용해서 답을 구할 수 있는 방법
이중반복문이지만 사실상 내 정답과 다를 바 없는 시간복잡도

🌈 자바스크립트 코드

function solution() {
  const mock_answer = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5];
  const patterns = ["12345", "21232425", "3311224455"];
  let scores = new Array(3).fill(0);
  mock_answer.forEach((answer, i) => {
    patterns.forEach((str, j) => {
      const pattern = [...str];
      if (answer === parseInt(pattern[i % pattern.length])) {
        scores[j] += 1;
      }
    });
  });
  return scores;
}

console.log(solution());

max와 아래부분은 생략